算术表达式的前序、中序、后序表示及其转换

写在前面:LeetCode刷题笔记


中序表达式转后序表达式(从左向右读入)

  1. 创建一个队列,存储后缀表达式;创建一个栈,存储操作符。

  2. 遇到操作数则送入队列。

  3. 遇到 “(“ ,入栈,遇到操作符入栈。

  4. 如果遇到其他运算符,不断去除所有运算优先级大于等于当前运算符的运算符,送入队列。最后,新的符号入栈。

  5. 遇到 “)” 括号,则将栈内从 “(“ 到 “)” 的所有操作符全部取出送入队列(左括号出栈但不入队)。

  6. 中序表达式读取结束后,如果栈不为空,则将栈内元素依次出栈送入队列。

  7. 此时队列的表达式即为原中序表达式的后序表达式。

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
/*代码实现中将操作数队列替换为vector*/
/*代码实现中只考虑了加、减运算,故没有判断优先级,如果是一个四则运算表达式可以添加优先级判断部分*/
void inToPost(string s, vector<char>& post)
{
//vector<char> post;
stack<char> op;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(')
{
op.push(s[i]);
}
else if (s[i] == '+')
{
while (!op.empty() && (op.top() == '+' || op.top() == '-'))
{
char tmp = op.top();
op.pop();
post.push_back(tmp);
}
op.push(s[i]);
}
else if (s[i] == '-')
{
while (!op.empty() && (op.top() == '+' || op.top() == '-'))
{
char tmp = op.top();
op.pop();
post.push_back(tmp);
}
op.push(s[i]);
}
else if (s[i] == ')')
{
while (!op.empty() && op.top() != '(')
{
char tmp = op.top();
op.pop();
post.push_back(tmp);
}
op.pop();
}
else
{
post.push_back(s[i]);
}
}
while (!op.empty())
{
post.push_back(op.top());
op.pop();
}
}

参考文章:表达式求值

Author: wnxy
Link: https://wnxy.github.io/2021/05/06/Arithmetic-expression/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.