数据结构学习<二> 栈实现中缀表达式计算

中缀表达式

一般来说我们常用的计算表达式就是中缀表达式,例如(59+8)(4*6+7),这样的表达式器运算符操作符是在操作数中间,但对于计算机来说,中缀表达式计算比较麻烦,也不容易实现,而后缀表达式则容易使用栈来实现计算。

后缀表达式

后缀表达式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。
上例中的中缀表达式(59+8)(4*6+7)的后缀表达形式则是598+467+***

对于后缀表达式可以用栈来实现求值

算法:后缀表达式求值
1)建立一个栈S
2)从左到右读表达式,如果读到操作数就将它压入栈S中,
3)如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作数运算,再将运算的结果代替原栈顶的n项,压入栈S中 。
4)如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。

计算598+467+***

1
2
3
4
5
6
7
8
9
10
11
12
表达式值 栈S
5 5
9 5 9
8 5 9 8
+ 5 17
4 5 17 4
6 5 17 4 6
* 5 17 24
* 5 408
7 5 408 7
+ 5 145
* 2075

那么问题来了

  • 中缀表达式怎么转为后缀表达式
  • 后缀表达式求值怎么实现

中缀表达式转后缀表达式

中缀表达式转后缀表达式算法

1
2
3
4
5
6
7
8
1.中缀表达式看成一个字符串,从左到右开始扫描中缀表达式;
2.若是数字就直接给后缀式子;
3.若是运算符号:
a 若为'(',入栈。
b 若为')',则依次把栈中的运算符加入后缀表达式中,直到出现'(',从栈中删除')';
c 若为除括号以外的其他运算符,当其优先级高于除'('以外的运算符时,直接入栈。
否则从栈顶开始依次弹出比当前运算符优先级高和相等的运算符,直到一个比它优先级低的或者遇到一个左括号为止。
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
#include<string>
#include<iostream>
#include<stack>
using namespace std;
bool OpAisBiggerThanOpB(char OpA, char OpB)//判断优先级
{
if (OpB == '(')
return true;
if ('*' == OpA || '/' == OpA&&'*' != OpB&&'/' != OpB) // */高于+-
return true;
else
return false;
}
void Mid2Dow(char * Par)//中缀转后缀
{
int N = strlen(Par);//计算表达式长度
stack<char> STA;
for (int i = 0; i < N; i++)//依次判断
{
if ('(' == Par[i])
{
STA.push(Par[i]);//左括号入栈
}
if (Par[i] == ')')//右括号
{
while (STA.top() != '(')//弹出栈里的操作符直到遇到左括号
{
cout << STA.top();
STA.pop();
}
if (STA.top() == '(')//左括号弹出不使用,消失掉
STA.pop();
}
if (Par[i] == '+' || Par[i] == '*' || '/' == Par[i] || '-' == Par[i])
{
if (STA.empty())//若本身为空栈直接入栈
{
STA.push(Par[i]);
continue;
}
if(!STA.empty()&&OpAisBiggerThanOpB(Par[i],STA.top()))//栈非空,与栈顶元素比较优先级
STA.push(Par[i]);//若大于栈顶元素直接入栈
else//非空且优先级比栈顶元素小
{
//弹出栈里元素直到遇到栈顶元素比入栈元素优先级小再入栈
while (!STA.empty()&&!OpAisBiggerThanOpB(Par[i], STA.top()))
{
cout << STA.top();
STA.pop();
}
STA.push(Par[i]);
}
}
if (Par[i] >= '0'&&Par[i] <= '9')//数字直接输出
cout << Par[i];
if (Par[i] >= 'A'&&Par[i] <= 'Z')
cout << Par[i];
}
while (!STA.empty())//最后输出栈内元素
{
if(STA.top()!='(')
cout << STA.top();
STA.pop();
}
}

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void)
{
char * Par = "5*(((9+8)*(4*6))+7";
char * Par2 = "(-(-1)+$((-1)*(-1)-(4*(-1))))/2";
char * Par3 = "5+(1+2)*4-3";
char * Par4 = "(A+B*C)/D";
char * Par5 = "512+4*+3-";
Mid2Dow(Par3);
return 0;
}

后缀表达式求值

算法之前已经分析过,现在给出代码

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
int Cal(char * Par)
{
int N = strlen(Par);
stack<int> STA;
for (int i = 0; i < N; i++)
{
if (Par[i] >= '0'&&Par[i] <= '9')
STA.push(Par[i] - '0');
if (Par[i] == '+')//弹出两个计算,压回栈
{
int a = STA.top();
STA.pop();
int b = STA.top();
STA.pop();
STA.push(a + b);
}
if (Par[i] == '-')
{
int a = STA.top();
STA.pop();
int b = STA.top();
STA.pop();
STA.push(b - a);
}
if (Par[i] == '*')
{
int a = STA.top();
STA.pop();
int b = STA.top();
STA.pop();
STA.push(a * b);
}
if (Par[i] == '/')
{
int a = STA.top();
STA.pop();
int b = STA.top();
STA.pop();
STA.push(a / b);
}
}
return STA.top();返回答案
}

总结

后缀表达式有着计算先天的优势,而中缀表达式与后缀表达式的转换与之前分析的函数声明分析算法有异曲同工之妙,其次中缀表达式与后缀表达式同树的中序遍历与后续遍历也是道理相通的。