本文最初写作于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 -

img

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

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

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

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

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

qq_pic_merged_1658118047047

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

1
1 2 3 * 2 / + 5 -

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

image-20220718122342759

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

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

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

2.2. 中缀转前缀

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

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

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

1
1 + 2 * 3 / 2 - 5

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

image-20240313145529611

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

1
- + 1 / * 2 3 2 5

2.3. 后缀转中缀

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

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

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

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

1
1 2 3 * 2 / + 5 - 

image-20240313154453407

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

1
1 + 2 * 3 / 2 - 5

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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. 逆波兰表达式求值

image-20220718120022828

3.2. 思路

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

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

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

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

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

3.3. 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//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();
}
};

Snipaste_2022-07-18_11-20-17

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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的操作改成反向迭代器就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 计算前缀表达式
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();
}

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

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

return 0;
}

5. The end

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