中缀表达式转为逆波兰式并求值（牛客NC137-表达式求值-C++实现）

今天刷牛客遇到一个表达式求值的题，题目链接如下： 牛客NC137-表达式求值 这道题与Leetcode 224-基本计算器类似，但Leetcode这道题没有要求乘法

涉及到编译原理的内容，后缀表达式计算起来比较容易，复习了一下将中缀表达式转化为后缀表达式的方法。 ①要用到两个stack：一个放数字、一个放运算符，由于数字可能有多位，且存在运算符栈顶pop后向数字栈push的情况，因此两个stack数据类型定义为string。 ②由于放数字的栈存放最后后缀表达式，且需要一次弹出逆序，果断一开始就用queue来存储 因此，定义存放运算符的栈opS、存放数字（及最终逆波兰式）的队列numQ

转化过程结合代码如下，我是用C++写的 首先，对中缀表达式进行遍历：

int len=s.size(); for(int i=0;i<len;i++){ ... }

下面是重点，即for循环中...的部分 ①如果是数字，直接压入numQueue

//当前是数字 if(s[i]>='0' && s[i]<='9'){ string curNum=""; while(i<len && s[i]>='0' && s[i]<='9'){ curNum+=s[i]; i++; } numQ.push(curNum); i--; }

这里i--是因为此时i已经指向非数字字符，要进行下一次循环，因为for有i++，为了不跳过当前字符先自减1

②如果是 ( ：直接压入opStack

//当前是左括号 else if(s[i]=='(') opS.push("(");

刚才提到了opS和numQ存放的都是string，注意push时用双引号

③如果是 ) ：直到opStack栈顶为 ( 前，将栈顶弹出、并压入numQueue；直到栈顶为 ( 时，将左括号弹出

//当前是右括号 else if(s[i]==')'){ while(!opS.empty() && opS.top()!="("){ numQ.push(opS.top()); opS.pop(); } //左括号要弹出来 opS.pop(); }

④如果是其他运算符（ + - * ）: 1. 如果opStack栈空 或 栈顶是（ ，直接压入栈 2.如果当前运算符 s [ i ] 比 opStack栈顶优先级高，直接压入栈 3.否则，将当前 opStack栈顶弹出、并压入numQueue，让当前运算符 s [ i ] 与新的栈顶进行对比

//当前是 + - * 这些符号 else{ //opS栈空、栈顶左括号直接入栈 if(opS.empty() || opS.top()=="(") opS.push(string(1,s[i])); //当前符号运算优先级高于opS栈顶，直接入栈 else if(getPr(s[i])>getPr(opS.top()[0])) opS.push(string(1,s[i])); //否则，将栈顶弹出并压入numQ，与下一个比较 else{ numQ.push(opS.top()); opS.pop(); i--; } }

首先，这里涉及到优先级的判断，一共+ - *三个运算符，函数int getPr(char ch);如下：

int getPr(char ch){ if(ch=='+' || ch=='-') return 0; else if(ch=='*') return 1; }

其次，当前运算符不符合前两个条件时（栈空或栈顶左括号、比栈顶运算符优先级高）时，将栈顶弹出并压入numQ。当前运算符要与新的栈顶比较，由于外面for循环的i++和遇到数字时类似，需要进行i--避免跳过这个运算符。

还有一点需要注意，getPr()参数类型是char，所以即使是单个字符的string也要取[0]；opS存放的类型是string，将char类型的s[i]转为string，语句为string(s[i],1)

下面是根据后缀表达式求值的函数int calc(); 后缀计算比较简单，如下题 Leetcode 150-逆波兰式求值 ①遍历numQ中的字符串， ②遇到数字转为int放入存放int的栈numStk， ③每次遇到运算符号，numStk中必有2个数字， ④将这2个数字弹出，根据运算符算完后再push进numStk， ⑤当后缀遍历完时，numStk栈顶即为所求，代码：

int calc(){ int num1,num2; while(!numQ.empty()){ string cur=numQ.front(); if(cur[0]>='0' && cur[0]<='9') numStk.push(stoi(cur)); else{ num2=numStk.top(); numStk.pop(); num1=numStk.top(); numStk.pop(); if(cur=="+") numStk.push(num1+num2); if(cur=="-") numStk.push(num1-num2); if(cur=="*") numStk.push(num1*num2); } numQ.pop(); } return numStk.top(); }

这里numStk、numQ我用的是全局变量，因此没有传参。

完整代码如下，将 判断运算符优先级getPr()、转为逆波兰表达式toSuffix()、计算逆波兰表达式的值calc()分为3个子函数，比牛客该题大部分提交代码都清晰易读

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */ queue<string> numQ; stack<string> opS; stack<int> numStk; int solve(string s) { toSuffix(s); return calc(); } void toSuffix(string s){ int len=s.size(); for(int i=0;i<len;i++){ //当前是数字 if(s[i]>='0' && s[i]<='9'){ string curNum=""; while(i<len && s[i]>='0' && s[i]<='9'){ curNum+=s[i]; i++; } numQ.push(curNum); i--; } //当前是左括号 else if(s[i]=='(') opS.push("("); //当前是右括号 else if(s[i]==')'){ while(!opS.empty() && opS.top()!="("){ numQ.push(opS.top()); opS.pop(); } //左括号也要弹出来 opS.pop(); } //当前是 + - * / 这些符号 else{ //当符号栈为空、栈顶优先级低于当前s[i]时，直接压入opS if(opS.empty() || opS.top()=="(") opS.push(string(1,s[i])); else if(getPr(s[i]) > getPr(opS.top()[0])) opS.push(string(1,s[i])); //否则将当前符号push进numQ、弹出，并让s[i]与新的栈顶对比 else{ numQ.push(opS.top()); opS.pop(); i--; } } } while(!opS.empty()){ numQ.push(opS.top()); opS.pop(); } } int getPr(char ch){ if(ch=='+' || ch=='-') return 0; else if(ch=='*') return 1; } int calc(){ int num1,num2; while(!numQ.empty()){ string cur=numQ.front(); if(cur[0]>='0' && cur[0]<='9') numStk.push(stoi(cur)); else{ num2=numStk.top(); numStk.pop(); num1=numStk.top(); numStk.pop(); if(cur=="+") numStk.push(num1+num2); if(cur=="-") numStk.push(num1-num2); if(cur=="*") numStk.push(num1*num2); } numQ.pop(); } return numStk.top(); } };

牛客运行结果如下：