实现求解包含括号 + - * / 整数运算的简单表达式求值。
问题思路:
非常经典的栈的运用。
首先实现中缀表达式转成后缀表达式:
去除括号优先级,原先的计算优先级将蕴含到后缀表达式的从左往右序列中。
具体做法: 数字直接加入到后缀表达式,其它入栈时,确保栈顶优先级更低。
遇到数字,直接加入到后缀表达式中。遇到( 直接入栈遇到) 不断弹栈,加入到后缀表达式,在遇到) 时候结束遇到+ - 不断弹栈,加入到后缀表达式,在遇到(时候,或者栈全部为空,此时 + -入栈遇到* / 当栈顶为 * /时,不断弹栈,加入到后缀表达式,最后* /入栈 //首先中缀转后缀 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();//最后操作数栈唯一那个元素即为结果