op数组用来存储处理后输入的表达式，经过处理，不带空格，viisit数组为1的时候，对应的op数组位置是运算符，否则是整数。然后就是比较运算符的优先级了，opnd是数字栈，optr是运算符栈。optr栈底先存一个‘#’，用数组存储一下运算符的优先级。具体代码：
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <math.h> #include <stack> #include <cctype> #include <iostream> using namespace std; int visit[1000]; char op[1000];//操作符 char s[1000]; stack<int>opnd; stack<char>optr; int cnt; void oprate() { int res; int b = opnd.top(); opnd.pop(); int a = opnd.top(); opnd.pop(); char t = optr.top(); optr.pop(); if(t == '+') res = a+b; else if(t == '-') res = a-b; else if(t == '*') res = a*b; else if(t == '/') res = a/b; opnd.push(res); return; } char pre(char a,char b) { int i,j; char t[10][10]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=','0'}, {'>','>','>','>','0','>','>'}, {'<','<','<','<','<','0','='}}; switch(a){ case '+': i=0; break; case '-': i=1; break; case '*': i=2; break; case '/': i=3; break; case '(': i=4; break; case ')': i=5; break; case '#': i=6; break; } switch(b){ case '+': j=0; break; case '-': j=1; break; case '*': j=2; break; case '/': j=3; break; case '(': j=4; break; case ')': j=5; break; case '#': j=6; break; } return t[i][j]; } int solve() { int i; char temp,t; optr.push('#'); for(i=0; i<cnt; i++) { if(visit[i])//代表是字符 { if(op[i] == '#') { if(!optr.empty()) { temp = optr.top(); while(temp != '#') { oprate(); temp = optr.top(); } } return 0; } temp = optr.top(); t = pre(temp,op[i]); if(t == '>') { oprate(); i--; // 这里一定要有i--，防止前面还有比当前运算符级别更高的运算符 } else if(t == '<') { optr.push(op[i]); } else if(t == '=') { temp = optr.top(); optr.pop(); } } else { opnd.push(op[i]); } } return 0; } int main() { int i,j,len; while(gets(s)) { while(!optr.empty()) { optr.pop(); } while(!opnd.empty()) { opnd.pop(); } memset(visit,0,sizeof(visit)); memset(op,0,sizeof(op)); len = strlen(s); cnt = 0; for(i=0; i<len; i++) { if(s[i] == ' ') continue; else if(!isdigit(s[i])) { visit[cnt] = 1; op[cnt++] = s[i]; } else { j = i; op[cnt] = s[i]-'0'; while(j!=len-1 && (s[j+1]>='0' && s[j+1]<='9')) { j++; op[cnt] = op[cnt]*10+s[j]-'0'; i=j; } cnt++; } } visit[cnt] = 1; op[cnt++] = '#'; solve(); printf("%d\n",opnd.top()); } return 0; }
