【leetcode】150.逆波兰表达式求值，以及前缀中缀后缀的相互转换

本文最初写作于2022-07-18，于近日大量更新，故重新发布。

1. 什么是前缀/中缀/后缀表达式？

我们日常学习数学，使用的表达式就是中缀表达式

1	1 + 2 * 3 / 2 - 5

前缀表达式就是将操作符放在操作数之前的表达式；中缀转前缀的方式是，先将中缀表达式按运算顺序加上括号，再将操作符移动到对应括号的前面，最后删除括号，就是前缀表达式

1
2
3

((1 + ((2 * 3) / 2)) - 5)
- (+(1 / (*(2 3) 2))  5)
- + 1 / * 2 3 2 5

后缀表达式就是将操作符放在操作数之前的表达式；同样是加括号，再将运算符移动到括号后，再去括号

1
2
3

((1 + ((2 * 3) / 2)) - 5)
((1 ((2 3)* 2)/) + 5) - 
1 2 3 * 2 / + 5 -

前缀表达式又称“波兰表达式”，后缀表达式为“逆波兰表达式”。

2. 表达式转换

2.1. 中缀转后缀

中缀表达式转换为后缀表达式的手工做法为：

按照运算符的优先级对所有的运算单位加括号。例： ((a/b) + (((c*d) - (e*f))/g))；
把运算符号移动到对应括号的后面，然后去掉括号。例：((ab)/ (((cd)*(ef)*)-g)/+，去掉括号ab/cd*ef*-g/+；

再来看看编程的思路吧，以这个中缀表达式为例，我们都知道，运算顺序应该是先计算2*3然后在计算6/2，最后计算1+3-5得出结果-1。

1	1 + 2 * 3 / 2 - 5

因为*和/操作符的优先级高于加减，这里就需要注意这种情况。我们需要用一个栈来存放操作符：

遇到操作数的时候 先输出 到结果表达式中;
遇到操作符，和栈顶进行比较
- 如果栈为空/操作符优先级高于栈顶，入栈；
- 操作符优先级低于栈顶或和栈顶相同，出栈顶操作符（然后继续比较当前操作符和栈顶操作符）；
最后将栈中的操作符全部出栈，就可以获得后缀表达式；

用上面这个思路走一遍，即为下面的情况（不知道这样写的大家能不能看明白）

最终得到的结果如下，即需要的后缀表达式。

1	1 2 3 * 2 / + 5 -

我们可以用下文OJ中的后缀表达式计算代码测试一下这个用例，得出的结果也是-1，正确！

如果中缀表达式中带括号咋办？

遇到操作数的时候 先输出 到结果表达式中;
遇到操作符，和栈顶进行比较
- 如果栈为空/操作符优先级高于栈顶，入栈；
- 操作符优先级低于栈顶或和栈顶相同，出栈顶操作符（然后继续比较当前操作符和栈顶操作符）；
如果是左括号(，正常入栈；
遇到右括号)，出栈内所有操作符，直到遇到对应左括号，注意，最终的输出后缀表达式中不需要添加左/右括号；
最后将栈中的操作符全部出栈，就可以获得后缀表达式；

简单理解，左括号的优先级低于其他运算符，右括号的优先级高于其他运算符，就可以用前文提到的基本办法来处理带括号的中缀表达式了。

2.2. 中缀转前缀

首先设定一个操作符栈，从右到左顺序扫描整个中缀表达式

如果是操作数，则直接归入最终表达式；
如果是操作符，则检测器是否是右括号，如果是右括号，则直接将其入栈；
如果是左括号，则将栈中的操作符依次弹栈，归入最终表达式，直至遇到右括号，将右括号弹栈，处理结束；
如果是其他操作符，则检测栈顶操作符的优先级与当前操作符的优先级关系，如果栈顶操作符优先级大于当前操作符的优先级，则弹栈，并归入最终表达式，直至栈顶操作符优先级小于等于当前操作符优先级，这时将当前操作符压栈。
当扫描完毕整个中缀表达式后，检测操作符栈是否为空，如果不为空，则依次将栈中操作符弹栈，归入最终表达式。
最后，将得出的最终表达式进行逆置，就得到中缀表达式对应的前缀表达式。

以下面这个中缀表达式为例

1	1 + 2 * 3 / 2 - 5

使用上述步骤的栈操作示意图如下

得到的前缀表达式如下，符合前文使用加括号法得到的结果！

1	- + 1 / * 2 3 2 5

2.3. 后缀转中缀

后缀转中缀会简单一些，因为不需要考虑括号优先级的问题。参考知否;

从左往右遍历后缀表达式：

如果是操作数，入栈；
如果是运算符（设符号为#），从栈顶取两个元素a和b，注意先取出来的是右操作数，将"( b # a )"这个字符串入栈。这里加括号是保证运算顺序。

最终栈顶的字符串就是我们需要的前缀表达式

1	1 2 3 * 2 / + 5 -

得到的中缀表达式符合预期！虽然会有多余的括号，但运算顺序是没有问题的。

1	1 + 2 * 3 / 2 - 5

C++代码如下，设输入的后缀表达式是有效的。

#include <stack>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

string postfix_to_infix(vector<string> expr) {
    stack<string> s;
    for (int i = 0; i < expr.size(); ++i) {
        // a number
        if (!expr[i].empty() && expr[i][0] >= '0' && expr[i][0] <= '9') {
            s.push(expr[i]);
        }
        // an operator
        else {
            string second = s.top(); s.pop();
            string first = s.top(); s.pop();
            s.push("(" + first + expr[i] + second + ")");
        }
    }
    return s.top();
}
int main() {
    vector<string> expr = {"3", "2", "5", "-", "6", "*", "3", "/", "+"};
    // output: (3+(((2-5)*6)/3))
    cout << postfix_to_infix(expr) << endl;
    return 0;
}

2.4. 前缀转后缀

依照上述后缀转前缀的思路，前缀转后缀的操作如下

从右往左遍历后缀表达式：

如果是操作数，入栈；
如果是运算符（设符号为#），从栈顶取两个元素a和b，注意先取出来的是左操作数，将"( a # b )"这个字符串入栈。这里加括号是保证运算顺序。

这样运算就能得到中缀表达式。这里就不做演示了。

2.5. 前缀/后缀转换？

因为已经学会了前缀转中缀，后缀转中缀的思路，前后缀的转换用中缀做个跳板就行了。面试的时候能说出思路来就够。

3. 逆波兰表达式求值

3.1. 题目来源

leetcode：150. 逆波兰表达式求值

3.2. 思路

逆波兰表达式又称为后缀表达式

中缀 1 + 2 * 3；
后缀 1 2 3 + *；

题目所给的参数是后缀表达式，其操作的思路如下：

从左往右遍历，遇到操作数，入栈
遇到运算符，取栈顶两个连续数据进行计算（第二个取出来的是左操作数），再将计算结果入栈

看起来不难，是因为这道题已经是简化后的版本，~~其所给后缀表达式中没有出现括号这种特殊优先级的操作~~。新注：这里理解有误，后缀/前缀表达式本来就是从中缀按优先级转换过来的，它们是不会包含括号的！

3.3. 完整代码

//https://leetcode.cn/problems/evaluate-reverse-polish-notation/submissions/
//150逆波兰表达式
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        for(auto& ch : tokens)
        {
            if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
            {
                int right=s.top();
                s.pop();
                int left=s.top();
                s.pop();
                switch(ch[0])
                {
                    case '+':
                        s.push(left+right);
                        break;
                    case '-':
                        s.push(left-right);
                        break;
                    case '*':
                        s.push(left*right);
                        break;
                    case '/':
                        s.push(left/right);
                        break;
                    default:
                        break;
                }
            }
            else{
                // 注意，题目给的vector中是字符串，需要转数字
                s.push(stoi(ch));
            }   
        }
        return s.top();
    }
};

可以使用lambda表达式来改造这个oj的代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> s;
        map<string,function<int(int,int)>> FuncMap = {
            {"+",[](int x,int y){return x+y;}},
            {"-",[](int x,int y){return x-y;}},
            {"*",[](int x,int y){return x*y;}},
            {"/",[](int x,int y){return x/y;}}
        };
        for(auto& ch : tokens)
        {
            if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
            {
                int right=s.top();
                s.pop();
                int left=s.top();
                s.pop();
                int ret = FuncMap[ch](left,right);
                s.push(ret);
            }
            else{
                s.push(stoi(ch));
            }   
        }
        return s.top();
    }
};

4. 前缀表达式求值

前缀表达式的计算方法和后缀基本一致。

从右往左遍历，遇到操作数，入栈；
遇到操作符，从栈顶取出两个数字进行计算，第一个取出来的数字是左操作数。计算后重新入栈。

还是以下面的前缀表达式为例

1	- + 1 / * 2 3 2 5

从右往左遍历入栈

第一波操作后，栈中包括2,3,2,5；
随后遇到第一个操作符*，从栈取出2和3进行计算，得到6，重新入栈6,2,5；
遇到第二个操作符/，从栈取出6和2进行计算，得到3，重新入栈3,5；
操作数1入栈，1,3,5；
操作符+，从栈中取出1和3进行计算，得到4，入栈4,5；
操作符-，从栈中取出4和5进行计算，得到最终结果-1；

这个前缀表达式对应的中缀如下，它的计算结果也是-1，处理正确！

1	1 + 2 * 3 / 2 - 5 = -1

和后缀表达式相比，前缀表达式只有遍历顺序不同，以及从栈取数据时左右操作数位置不同，所以只需要将遍历vector的操作改成反向迭代器就可以了。

// 计算前缀表达式
int evalPN(vector<string>& tokens) {
    stack<int> s;
    map<string,function<int(int,int)>> FuncMap = {
        {"+",[](int x,int y){return x+y;}},
        {"-",[](int x,int y){return x-y;}},
        {"*",[](int x,int y){return x*y;}},
        {"/",[](int x,int y){return x/y;}}
    };
    auto riter = tokens.rbegin();
    for(;riter != tokens.rend();riter++)
    {
        string ch = *riter;
        if(ch=="+"||ch=="-"||ch=="*"||ch=="/")
        {
            // 前缀表达式第一个取出来的是左操作数
            int left=s.top();
            s.pop();
            int right=s.top();
            s.pop();
            int ret = FuncMap[ch](left,right);
            s.push(ret);
        }
        else{
            s.push(stoi(ch));
        }   
    }
    return s.top();
}

使用表达式进行测试，得到正确输出

int main()
{
    vector<string> v = {"-","+","1","/","*","2","3","2" ,"5"};
    cout << evalPN(v) << "\n"; // 输出 -1

    return 0;
}

5. The end

网易雷火的面试考到了前缀表达式求值，故此更新本文