后缀表达式

Entropy Lv4

基于STL的中缀转后缀实现

1.定义分析

首先明确后缀表达式的定义

后缀表达式是一种不需要括号的表达式,这表示在将中缀表达式转化为后缀表达式时,如果中缀表达式中存在括号,不能将括号写入后缀表达式

那么这里引出一个问题,后缀表达式中不存在括号那要如何表示运算的优先级?

理解后缀表达式的运算过程

以(1+5-4)*(6-9)为例,它的后缀表达式是15+4-69-*

先分析中缀表达式的运算过程,参与运算过程的操作符依次是+ - - *,正好是后缀表达式中从左往右的操作符顺序。而操作符所涉及到的2个操作数都是位于该操作符的前面。

那么回到上面的问题来看,中缀表达式中的括号的作用如何在后缀表达式中体现出来

以1+2*3、(1+2)*3为例

1+2*3的后缀表达式为123*+

(1+2)*3的后缀表达式为12+3*

通过对比可以发现当表达式中存在括号时,括号中的操作符提前输出了,这表示在遇到括号的情况时,可以将括号内的操作符提前输出。

此外,还需要考虑四则运算中,乘除的优先级高于加减

以1+2*3为例,如果不加以判断直接转化后缀表达式,结果为12+3*,先运算+再运算*,这显然违背了基本的四则运算法则,实际上正确的结果应该是123*+

通过对比两个结果,可以发现优先级较低的操作符移到了后面,这表示在运算过程中可以先将优先级低的操作符存储起来,而将优先级高的运算符输出

2.思路分析

采用STL模板实现中缀转后缀,这里使用的是stack。定义一个stack字符栈专门用于存储操作符

这里特别说明一下字符栈,字符栈栈底的操作符优先级最低,栈顶的操作符优先级最高

1.输入中缀表达式的字符串依次获取字符串中的每个字符

2.对字符进行以下的判断和操作

  • 数字字符,直接输出
  • 左括号字符,直接存入stack
  • 右括号字符,将stack中的操作符依次输出,直到遇到左括号时停止,将左括号出栈但不输出
  • 加减乘除字符
    • 优先级高的字符直接存入stack
    • 优先级低的字符,则比较当前字符栈栈顶操作符的优先级,遇到优先级更低的操作符或左括号字符时不出栈,并将当前操作符入栈

3.当字符串遍历完成后,再依次输出字符栈内剩余的操作符

3.实现过程分析

以(1+5-4)*(6-9)为例,字符串长度为13

获取到的字符:(

表达式:

字符栈:(

获取到的字符:1

表达式:1

字符栈:(

获取到的字符:+

表达式:1

字符栈:(+

获取到的字符:5

表达式:15

字符栈:(+

获取到的字符:-

表达式:15+

字符栈:(-

获取到的字符:4

表达式:15+4

字符栈:(-

获取到的字符:)

表达式:15+4-

字符栈:

获取到的字符:*

表达式:15+4-

字符栈:*

获取到的字符:(

表达式:15+4-

字符栈:*(

获取到的字符:6

表达式:15+4-6

字符栈:*(

获取到的字符:-

表达式:15+4-6

字符栈:*(-

获取到的字符:9

表达式:15+4-69

字符栈:*(-

获取到的字符:)

表达式:15+4-69-

字符栈:*

最后,依次输出字符栈中所有的操作符

表达式:15+4-69-*

4.源代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <algorithm>
#include <stack>
#include <list>
using namespace std;

list<string> transfer(string s)
{
int len = s.length(); //记录长度
list<string> listIn; //存储中缀表达式
list<string> listOut; //存储后缀表达式
stack<char> symbol; //符号栈
stack<char> ans; //结果表达式

listIn.push_back(s);
for (int i = 0; i < len; i++)
{
//思路
//数字直接存入ans
//运算符:
//如果是'('直接存入symbol
//如果是')'依次出栈symbol中的运算符并存入ans, 直到遇到'(', '('不存入ans
//其他符号, 依次出栈symbol中的运算符并存入ans, 直到遇到优先级更低的运算符或'('时, 将当前符号存入symbol
//字符串遍历完成后, 依次出栈符号栈中剩余的运算符并存入ans
if (listIn.back()[i] >= '0' && listIn.back()[i] <= '9')
ans.push(listIn.back()[i]);
else if (listIn.back()[i] == '(')
symbol.push(listIn.back()[i]);
else if (listIn.back()[i] == ')')
{
while (symbol.top() != '(')
{
ans.push(symbol.top());
symbol.pop();
}
symbol.pop(); //将'('出栈
}
else
{
//这里手动优先考虑乘除的优先级高于加减
if (listIn.back()[i] == '+' || listIn.back()[i] == '-') //加减符号优先级最低
{
while (!symbol.empty() && symbol.top() != '(')
{
ans.push(symbol.top()); //直接存入symbol中的运算符
symbol.pop();
}
symbol.push(listIn.back()[i]); //符号栈存入当前从listIn中获取的符号
}
else //乘除符号优先级高直接存入符号栈
{
symbol.push(listIn.back()[i]);
}
}
}

while (!symbol.empty())
{
ans.push(symbol.top());
symbol.pop();
}

//将结果表达式的值存入listOut
//先利用已经清空的symbol实现反转
while (!ans.empty())
{
symbol.push(ans.top());
ans.pop();
}

string res = "";
while (!symbol.empty())
{
res += symbol.top();
symbol.pop();
}
listOut.push_back(res);

return listOut;
}

int main()
{
string s;
while (cin >> s)
{
list<string> res = transfer(s);
cout << res.front() << "\n";
}
}

  • 标题: 后缀表达式
  • 作者: Entropy
  • 创建于 : 2022-10-27 00:28:58
  • 更新于 : 2023-04-01 07:55:52
  • 链接: https://www.entropy-tree.top/2022/10/27/suffix-expression/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
后缀表达式