#include <cstdio> #include <stack> #include <ctype.h> using namespace std; int operate(int a,char Optr,int b); int cmp(char Optr1,char Optr2); int Get_OP(stack<char> *s); void push(stack<char> *s,int op); int main() { freopen("in.txt","r",stdin); stack<char> Opnd; stack<char> Optr; Optr.push('#'); char ch; int OP1,OP2,OP3; while(1 == scanf("%c",&ch)) { if(isdigit(ch)) Opnd.push(ch); else { if(-1 == cmp(Optr.top(),ch)) Optr.push(ch); if(1 == cmp(Optr.top(),ch)) { OP2 = Get_OP(&Opnd); OP1 = Get_OP(&Opnd); OP3 = operate(OP1,Optr.top(),OP2); printf("%c\n",Optr.top()); Optr.pop(); while(Optr.top() != '#') { if(1 == cmp(Optr.top(),ch)) { OP2 = OP3; OP1 = Get_OP(&Opnd); OP3 = operate(OP1,Optr.top(),OP2); Optr.pop(); } else if(0 == cmp(Optr.top(),ch)) { printf("%c\n",Optr.top()); Optr.pop(); break; } else break; } if(ch != ')') Optr.push(ch); Opnd.push(','); push(&Opnd,OP3); } if(ch != '#' && ch != '('&& ch != ')') Opnd.push(','); } } printf("%d\n",Get_OP(&Opnd)); return 0; } int operate(int a,char Optr,int b) { if(Optr == '+') return a+b; else if(Optr == '-') return a-b; else if(Optr == '*') return a*b; else return a/b; } int cmp(char Optr1,char Optr2) { if(Optr1 == Optr2) { if(Optr1 == '#') return 0; if(Optr1 == '(') return -1; if(Optr1 == ')') return 1; } else { if(Optr1 == '+') { if(Optr2 == ')' || Optr2 == '-' || Optr2 == '#') return 1; else return -1; } if(Optr1 == '-') { if(Optr2 == ')' || Optr2 == '+' || Optr2 == '#') return 1; else return -1; } if(Optr1 == '*' || Optr1 == '/') { if(Optr2 == '(') return -1; else return 1; } if(Optr1 == '(') { if(Optr2 == ')') return 0; else return -1; } if(Optr1 == ')') { return 1; } if(Optr1 == '#') { return -1; } } return 2; } int Get_OP(stack<char> *s) { char ss[8]; int r,i; memset(ss,'0',8*sizeof(char)); i = 7; while(!(*s).empty()) { if((*s).top() == ',') { (*s).pop(); break; } ss[i--] = (*s).top(); (*s).pop(); } if(ss[++i] == '-') { ss[i] = '0'; sscanf(ss,"%d",&r); r = -1*r; } else sscanf(ss,"%d",&r); return r; } void push(stack<char> *s,int op) { char buf[8]; if(op<0) { op = -1*op; sprintf(buf,"%d",op); (*s).push('-'); for(int j=0;j<strlen(buf);j++) { (*s).push(buf[j]); } } else { sprintf(buf,"%d",op); for(int j=0;j<strlen(buf);j++) { (*s).push(buf[j]); } } }
具体思想参见 《数据结构C语言版--严蔚敏》直接贴代码: