实现求解包含括号 + - * / 整数运算的简单表达式求值。
问题思路：
非常经典的栈的运用。
首先实现中缀表达式转成后缀表达式：
去除括号优先级，原先的计算优先级将蕴含到后缀表达式的从左往右序列中。
具体做法： 数字直接加入到后缀表达式，其它入栈时，确保栈顶优先级更低。
遇到数字，直接加入到后缀表达式中。遇到( 直接入栈遇到) 不断弹栈，加入到后缀表达式，在遇到) 时候结束遇到+ - 不断弹栈，加入到后缀表达式，在遇到(时候，或者栈全部为空，此时 + -入栈遇到* / 当栈顶为 * /时，不断弹栈，加入到后缀表达式，最后* /入栈 //首先中缀转后缀 stack<string> stk;//栈序列 vector<string> res; for(int i=0;i<s.size();i++) { if(s[i]>='0' && s[i]<='9') //某个字符为数字 { int l=i; while(i+1<s.size() && (s[i+1]>='0' && s[i+1]<='9') ) i++; int r=i; res.push_back(s.substr(l,r-l+1));//截取出数字字符串 } else if(s[i]=='(')//左括号 总是入栈 { stk.push("("); } else if(s[i]==')') //遇到右括号不断退栈 直到遇到左括号 { while(stk.empty()==false && stk.top()!="(") { res.push_back(stk.top()); stk.pop(); //不断弹出栈顶 } stk.pop();//最后这个左括号也弹出 } else if(s[i]=='+' || s[i]=='-') { //栈非空 并且不是(括号 那么一直弹出栈 while(stk.empty()==false && stk.top()!="(") { res.push_back(stk.top()); stk.pop(); } string one; one+=s[i]; stk.push(one);//入栈 } else if(s[i]=='*' || s[i]=='/') { //栈非空 并且栈顶为* / 时一直弹出栈 while(stk.empty()==false && (stk.top()=="*"||stk.top()=="/" )) { res.push_back(stk.top()); stk.pop(); } string one; one+=s[i]; stk.push(one);//入栈 } } while(stk.empty()==false) //最后栈中剩余 如 2+3 最后剩余 + { res.push_back(stk.top()); stk.pop(); }
后缀表达式求值：
初始化一个操作数栈
开始遍历后缀表达式：
若遇到为数字，那么直接入操作数栈。（之前需要先分割好数字）若遇到运算符，那么弹出栈顶两个数字num1 num2 进行运算，结果入操作数栈最后结束，栈中唯一那个数字即为结果。易错点：
num1 num2 在进行 - / 运算时顺序为 num2 op num1
//表达式求值 stack<int> num_stk;//操作数栈 for(int i=0;i<res.size();i++) { if(res[i][0]>='0' && res[i][0]<='9') //是一个数字 { num_stk.push(to_num(res[i]));//入操作数栈 } else if(res[i][0]=='+') { int num1=num_stk.top(); num_stk.pop(); int num2=num_stk.top(); num_stk.pop(); num_stk.push(num1+num2);//运算之后入栈 } else if(res[i][0]=='-') { int num1=num_stk.top(); num_stk.pop(); int num2=num_stk.top(); num_stk.pop(); num_stk.push(num2-num1);//运算之后入栈 } else if(res[i][0]=='*') { int num1=num_stk.top(); num_stk.pop(); int num2=num_stk.top(); num_stk.pop(); num_stk.push(num1*num2);//运算之后入栈 } else if(res[i][0]=='/') { int num1=num_stk.top(); num_stk.pop(); int num2=num_stk.top(); num_stk.pop(); num_stk.push(num2/num1);//运算之后入栈 } } return num_stk.top();//最后操作数栈唯一那个元素即为结果
