最近在学数据结构，刚学完Expression Tree，解答了我多年的疑惑。以前就想写一个二十四点的小游戏，计算机发4张牌，玩家在规定时间内想出4张牌任意四则运算后得到24的表达式。框架搭好，也可以发牌了，电脑怎么答题可以遍历所有可能性，得到24就中止。但玩家输入表达式，怎么计算出值是关键问题。现在终于知道解法了。
【C++计算四则运算表达式程序】代码如下：

#include #include #include using namespace std; int isNumber(char c); /* 单个元素 */ struct Element { int type; //0:数字1:运算符 int value; //数字的值 char operate[5]; //运算符 int op_num; //操作数个数 bool left2right; //运算顺序左结合 }; /* 返回运算符结合性 */ bool isLeft2Right(char c) { switch (c) { case '+': case '-': case '*': case '/': case '&': case '|': case '%':return true; case '^':return false; } }/* 返回运算符的优先级 */ int Rank(char s[]) { switch (s[0]) { case '(':return 0; case ')':return 0; //左右括号优先级小是为了不被其余任何运算符挤出 case '+': case '-':return 5; //低优先级将挤出高优先级 case '*': case '/':return 10; case '^':return 11; case '&': case '|':return 12; case '%':return 15; //取余运算 } int err=-1; if (isNumber(s[0])) err=0; return err; }/* 是运算符 */ int isOperator(char c) { switch (c) { case '(': case ')':return 10; case '+': case '-': case '*': case '/': case '^': case '&': case '|': case '%':return 1; } return 0; }/* 有效性检查（返回0则出现异常字符） */ int isLegal(char c) { if (isNumber(c)) return 1; if (isOperator(c)) return 1; return 0; }int isNumber(char c) { if (c>='0' && c<='9') return 1; else return 0; }/* 由位数得到应该相乘的倍数 如digit=2返回100 */ int digit2num(int digit) { int temp=1; digit--; while (digit) { temp*=10; digit--; } return temp; }/*由in order队列得到post order队列*/ int InQueue2PostQueue(queue *post,queue *in)//返回0:正常 1:括号不配对 { int sq_err=0; stack temp; while (in->size()>0) { if (in->front().type==0) { post->push(in->front()); in->pop(); } else { if (in->front().operate[0]=='(') //左括号直接入栈 { temp.push(in->front()); in->pop(); sq_err++; } else { if (in->front().operate[0]==')')//出现右括号 { while (temp.size()>0) { if (temp.top().operate[0]=='(') { temp.pop(); sq_err--; break; } else { post->push(temp.top()); temp.pop(); } } in->pop(); } else//不是括号 { if (temp.size()>0 && temp.top().left2right==true)//左结合 while (temp.size()>0 && Rank(in->front().operate)<=Rank(temp.top().operate))//临时栈有内容，且新进符号优先级低，则挤出高优先级及同优先级符号 { post->push(temp.top()); //符号进入post队列 temp.pop(); } else//右结合 while (temp.size()>0 && Rank(in->front().operate)push(temp.top()); //符号进入post队列 temp.pop(); }; temp.push(in->front()); //高优先级已全部挤出，当前符号入栈 in->pop(); }} } } while (temp.size()>0) { post->push(temp.top()); temp.pop(); } return sq_err; }/*由字符串表达式得到in order队列*/ int Str2Queue(queue *inorder,char expression[]) { int err=0; Element tempe; int a,b; int type,num,sign=1; for (int i=0; i<(int)strlen(expression); ) { num=0; type=isNumber(expression[i]); if (type) a=i; while (isNumber(expression[i])&&i<(int)strlen(expression)) { i++; } if (type)//数字 { b=i-a; //位数 while (b) { num+=(expression[a]-'0')*digit2num(b); a++; b--; } tempe.type=0; tempe.value=https://www.it610.com/article/num*sign; sign=1; //sign符号正常化 tempe.operate[0]='\0'; (*inorder).push(tempe); } else//不是数字 { if ( (expression[i]=='-' && i==0)||(expression[i]=='-' && isOperator(expression[i-1])) )// { sign*=-1; } else { /* 非法性判定 */ if (isLegal(expression[i])!=1) {err=-1; break; }//出现非法字符 if (i==0 && isOperator(expression[i])) {err=-1; break; }//首字符出现非-的符号 if (i+1<(int)strlen(expression) && isOperator(expression[i])==1 && expression[i+1]==')') {err=-1; break; }//出现*)形式 if (i-1>=0 && isOperator(expression[i])==1 && (expression[i-1]=='(' || isOperator(expression[i-1])==1)) {err=-1; break; }//出现(*形式或**形式tempe.type=1; tempe.value=https://www.it610.com/article/0; tempe.operate[0]=expression[i]; tempe.operate[1]='\0'; tempe.left2right=isLeft2Right(expression[i]); tempe.op_num=2; (*inorder).push(tempe); } i++; } } return err; }/*由运算符c及a,b计算出值*/ int CalcNum(int a,int b,char c) { switch (c) { case '+':return a+b; case '-':return a-b; case '*':return a*b; case '/':return a/b; case '%':return a%b; case '&':return a&b; case '|':return a|b; case '^':return (int)pow((double)a,(double)b); } }/*由post order序列计算出值*/ int Calc(queue *post) { Element tempe; stack temp; int a,b; while (post->size()>0) { if (post->front().type==1)//运算符 { b=temp.top().value; temp.pop(); a=temp.top().value; temp.pop(); tempe.type=0; tempe.operate[0]='\0'; tempe.value=https://www.it610.com/article/CalcNum(a,b,post->front().operate[0]); temp.push(tempe); post->pop(); } else { temp.push(post->front()); post->pop(); } } return temp.top().value; }int main() { cout<<"----- 表达式运算Demo -----"<>"; cin>>expression; /* 1.字符串转换为in order队列 */ queue inorder,postorder; if (Str2Queue(&inorder,expression)!=0) { cout<<"表达式非法。"<