中缀表达式转后缀表达式及求值

栈的应用—中缀表达式转后缀表达式并求值


后缀表达式也称逆波兰(Reverse Polish Notation, RPN)

例如一个标准四则运算表达式9+(3-1)*3+6/2,转变成后缀表达式9 3 1 - 3 * + 6 2 / +

中缀表达式转后缀表达式

实现原理

中缀转后缀原理很简单,利用即可。

要点

  • 遇到数字:直接输出。
  • 遇到'(':压栈。
  • 遇到')':持续出栈,直到'('已出栈。
  • 遇到符号则判断该符号与栈顶符号的运算优先级(乘除优先级>加减),如果栈顶符号的运算优先级 <= 栈顶元素的优先级,则栈顶元素依次出栈,最后将该元素入栈。
  • 处理完字符串后将栈中剩余的符号全部输出。

根据后缀表达式求值

实现原理

同样是使用

要点

  • 初始化一个空栈。
  • 遇到数字,直接入栈。
  • 遇到符号,取出栈顶元素以及紧挨着栈顶的栈的第二个元素,相加减乘除,再压入栈。
  • 栈最后剩下的单独的元素即为答案

代码

下面的代码利用了C++ STL标准模板库中的Stack实现栈。

只是简单的模拟过程,只能计算10以下的数

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
#include<vector>
#include<string>
#include<stack>
using namespace std;
int main(void)
{
string str; //原始的四则运算表达式
stack<char> s;
vector<char> res;//后缀表达式
cin >> str;
for(int i=0; i<str.size(); i++)
{
if(str[i]>='0'&&str[i]<='9')
{
res.push_back(str[i]);
}
if(str[i]=='*'||str[i]=='/')
{
if(s.empty()||s.top()!='*'&&s.top()!='/')
{
s.push(str[i]);
}
else
{
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
s.push(str[i]);
}
}
if(str[i]=='+'||str[i]=='-')
{
if(s.empty()||s.top()!='*'&&s.top()!='/'&&s.top()!='+'&&s.top()!='-')
{
s.push(str[i]);
}
else
{
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
s.push(str[i]);
}
}
if(str[i]=='(') s.push(str[i]);
if(str[i]==')')
{
while(s.top()!='(')
{
res.push_back(s.top());
s.pop();
}
s.pop();
}
}
while(!s.empty())
{
res.push_back(s.top());
s.pop();
}
for(auto i: res)
cout<<i;
cout<<endl;
stack<int> cal;
for(int i=0;i<res.size();i++)
{
if(res[i]>='0'&&res[i]<='9')
cal.push(res[i]-48);
if(res[i]=='+')
{
int t = cal.top();
cal.pop();
cal.top() = cal.top() + t;
}
if(res[i]=='-')
{
int t = cal.top();
cal.pop();
cal.top() = cal.top() - t;
}
if(res[i]=='*')
{
int t = cal.top();
cal.pop();
cal.top() = cal.top() * t;
}
if(res[i]=='/')
{
int t = cal.top();
cal.pop();
cal.top() = cal.top() / t;
}
}
cout<<cal.top()<<endl;
cal.pop();
return 0;
}