逆波兰表达式

虽然数据结构比较简单,但是有些题遇到之后直接盲敲也并无十足的把握,往往还需要找些资料理清一下思路才敢去写;

有些内容本身就比较复杂,涉及到的知识点也比较多,只看的话不容易记住,只有自己练习一遍印象才会深刻。

所以本专题主要记录这些内容,毕竟好记性不如烂笔头。

从一个简单题目谈起

【问题描述】

从标准输入中读入一个整数算术运算表达式,如 24 / ( 1 + 5%3 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )=,计算表达式结果,并输出。

【要求】

  1. 表达式运算符只有 +,-,*,/,%,表达式末尾的 = 字符表示表达式输入结束,表达式中可能会出现空格

  2. 表达式中会出现圆括号,括号可能嵌套,不会出现错误的表达式

  3. 出现除号 / 时,以整数相除进行运算,结果仍为整数,例如:5/3 结果应为 1

  4. 要求采用逆波兰表达式来实现表达式计算

【输入形式】

从键盘输入一个以 = 结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。

【输出形式】

在屏幕上输出计算结果(为整数,即在计算过程中除法为整除)。

【样例输入】

24 / ( 1 + 5%3 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 ) =

【样例输出】

18

【样例说明】

按照运算符及括号优先级依次计算表达式的值。

思路

表达式的三种形式:前缀型、中缀型与后缀型。其中为大家熟知的是中缀形式,如 2 + 3 * (5 - 4)

前缀型表达式又叫波兰式(Polish Notation),后缀性表达式又叫逆波兰式(Reverse Polish Notation)。他们最早于1920年波兰数学家Jan Lukasiewicz发明,这两种表示方式的最大特点是不需要括号来表明优先级,他们经常用于计算机科学,特别是编译器设计方面。

所以我们的基本思路是先把中缀表达式转化为后缀表达式,再对后缀表达式进行求值

中缀 –> 后缀

使用栈

规则

中缀表达式 a + b*c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f  + g * +

转换过程需要用到栈,具体过程如下:

  1. 如果遇到操作数,我们就直接将其输出

  2. 如果遇到运算符,我们将其放入到栈中,遇到左括号时我们也将其放入栈中

  3. 如果遇到一个右括号,则将栈元素弹出并输出直到遇到左括号为止。注意,左括号只弹出并不输出

  4. 如果遇到任何其他的操作符,如 '+','*','(' 等,将栈中比该运算符优先级高的依次弹出并输出,直到遇到更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到右括号 ')' 的情况下我们才弹出左括号 '(' ,其他情况我们都不会弹出左括号 '('

  5. 如果我们读到了输入的末尾栈不为空,则将栈中所有元素依次弹出

实例

规则很多,还是用实例比较容易说清楚整个过程。以上面的转换为例,输入为 a + b * c + (d * e + f)*g,处理过程如下:

  1. 首先读到 a,直接输出

  2. 读到 '+',将其放入到栈中

  3. 读到 b,直接输出

此时栈和输出的情况如下:

stack01

  1. 读到 '*',因为栈顶元素 '+' 优先级比 '*' 低,所以将 '*' 直接压入栈中

  2. 读到 c,直接输出

此时栈和输出情况如下:

stack02

  1. 读到 '+',因为栈顶元素 '*' 的优先级比它高,所以弹出 '*' 并输出, 同理,栈中下一个元素 '+' 优先级与读到的操作符 '+' 一样,所以也要弹出并输出。然后再将读到的 '+' 压入栈中。

此时栈和输出情况如下:

stack03

  1. 下一个读到的为 '(',它优先级最高,所以直接放入到栈中。

  2. 读到 d,将其直接输出。

此时栈和输出情况如下:

stack04

  1. 读到 '*',由于只有遇到 ')' 的时候左括号 '(' 才会弹出,所以 '*' 直接压入栈中。

  2. 读到 e,直接输出。

此时栈和输出情况如下:

stack05

  1. 读到 '+',弹出 '*' 并输出,然后将 '+' 压入栈中。

  2. 读到 f,直接输出。

此时栈和输出情况:

stack06

  1. 接下来读到 ')',则直接将栈中元素弹出并输出直到遇到 '(' 为止。这里右括号前只有一个操作符 '+' 被弹出并输出。

stack07

  1. 读到 '*',压入栈中。读到 g,直接输出。

stack08

  1. 此时输入数据已经读到末尾,栈中还有两个操作符 '*''+',直接弹出并输出。

stack09

至此整个转换过程完成。

参考代码

代码仅供参考,如有错误,还请指出

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
#define MAXLEN 10007

int priority(char c)
{//优先级
if (c == '(')
return 3;
if (c == '*' || c == '/' || c == '%')
return 2;
if (c == '+' || c == '-')
return 1;
return 0;
}

int isop(char c)
{// ')' 单独判断,不在此判断
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '(';
}

char stack_op[MAXLEN]; //记录运算符的栈
int top_op = -1; //记录运算符栈的栈顶
char output[MAXLEN]; //记录最终结果的数组
int pos = 0; //记录最终结果的下标

int main()
{
int c;
while ((c = fgetc(stdin)) != EOF) {
if (isdigit(c)) {
output[pos++] = c;
while ((c = fgetc(stdin)) != EOF && isdigit(c)) {
output[pos++] = c;
}
output[pos++] = ' ';
}
if (isop(c)) {
if (top_op == -1 || priority(stack_op[top_op]) < priority(c)) {
stack_op[++top_op] = c;
}
else {
while (top_op > -1 && priority(stack_op[top_op]) >= priority(c) && stack_op[top_op] != '(') {
output[pos++] = stack_op[top_op--];
output[pos++] = ' ';
}
//该运算符入栈
stack_op[++top_op] = c;
}
}
else if (c == ')') {
while (stack_op[top_op] != '(') {
// '(' 之前的全部出栈
output[pos++] = stack_op[top_op--];
output[pos++] = ' ';
}
// '(' 也要出栈
top_op--;
}
}

//如果运算符的栈中还有元素,全部出栈
while (top_op > -1) {
output[pos++] = stack_op[top_op--];
output[pos++] = ' ';
}
output[--pos] = '\0';
printf("%s\n", output);
return 0;
}

使用表达式树

本质上是二叉树,不过这棵树的树叶全为操作数(operand),其他的节点均为运算符。对该树进行先序遍历、中序遍历和后序遍历正好对应前缀表达式、中缀表达和后缀表达式。

对于表达式树的求值操作非常简单,甚至只需要两条语句。因为这里大部分操作都是递归定义,而递归函数本身都是很简洁的。

另一种转换方法

仅提供一种思路,具体操作起来可能比较麻烦,有兴趣可自行尝试

  1. 先按照运算符的优先级对中缀表达式加括号,变成 ( ( a+(b*c) ) + ( ((d*e)+f) *g ) )

  2. 将运算符移到括号的后面,变成 ((a(bc)*)+(((de)*f)+g)*)+

  3. 去掉括号,得到 abc*+de*f+g*+

对后缀表达式求值

常规的逆波兰表达式求值,比较简单,读取到数字直接入栈,读取到运算符就取出栈顶两个数字做运算,然后将运算结果入栈,最后栈中剩余的数即为计算结果。下面直接给出参考代码

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
int stack_num[MAXLEN];  //记录数字的栈
int top_num = -1; //记录数字栈的栈顶

int cal(int a, char op, int b)
{
switch (op)
{
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
case '%':return a % b;
default:
return 0;
}
}

int result(char output[]) //output[] 中是后缀表达式
{
int i, a, b, c, tmp_num;
char tmp_op;
for (i = 0; output[i] != '\0'; i++) {
c = output[i];
if (isdigit(c)) {
tmp_num = c - '0';
while ((c = output[++i]) && isdigit(c))
tmp_num = tmp_num * 10 + c - '0';
stack_num[++top_num] = tmp_num;
}
if (isop(c)) {
//出栈两个数字,计算后将结果入栈
a = stack_num[top_num--];
b = stack_num[top_num--];
//注意 a,b 的顺序,不要反了
stack_num[++top_num] = cal(b, c, a);
}
}
return stack_num[top_num];
}

代码优化

由于题目中只要求给出最终结果,并不要求输出后缀表达式,所以我们将计算后缀表达式和计算最终结果的过程合并到一起来写,下面是参考代码:

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
#define MAXLEN 10007

int priority(char c)
{
if (c == '(')
return 3;
if (c == '*' || c == '/' || c == '%')
return 2;
if (c == '+' || c == '-')
return 1;
return 0;
}

int isop(char c)
{
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '(';
}

int cal(int a, char op, int b)
{
switch (op)
{
case '+':return a + b;
case '-':return a - b;
case '*':return a * b;
case '/':return a / b;
case '%':return a % b;
default:
return 0;
}
}

int stack_num[MAXLEN]; //记录数字的栈
char stack_op[MAXLEN]; //记录运算符的栈
int top_num = -1; //记录数字栈的栈顶
int top_op = -1; //记录运算符栈的栈顶

int main()
{
int c, a, b, tmp_num;
char tmp_op;
while ((c = fgetc(stdin)) != EOF) {
if (isdigit(c)) {
tmp_num = c - '0';
while ((c = fgetc(stdin)) != EOF && isdigit(c))
tmp_num = tmp_num * 10 + c - '0';
stack_num[++top_num] = tmp_num;
}

if (isop(c)) {
if (top_op == -1 || priority(stack_op[top_op]) < priority(c)) {
stack_op[++top_op] = c;
}
else {
while (top_op > -1 && priority(stack_op[top_op]) >= priority(c) && stack_op[top_op] != '(') {
tmp_op = stack_op[top_op--];
a = stack_num[top_num--];
b = stack_num[top_num--];
//注意 a,b 的顺序,不要反了
stack_num[++top_num] = cal(b, tmp_op, a);
}
//该运算符入栈
stack_op[++top_op] = c;
}
}
else if (c == ')') {
while (stack_op[top_op] != '(') {
tmp_op = stack_op[top_op--];
a = stack_num[top_num--];
b = stack_num[top_num--];
stack_num[++top_num] = cal(b, tmp_op, a);
}
// '(' 也要出栈
top_op--;
}
}

//如果运算符的栈中还有元素,全部出栈
while (top_op > -1) {
tmp_op = stack_op[top_op--];
a = stack_num[top_num--];
b = stack_num[top_num--];
stack_num[++top_num] = cal(b, tmp_op, a);
}
printf("%d\n", stack_num[top_num]);
return 0;
}

leetcode 227. 基本计算器

可以参考 leetcode 227进行练习,本题更为简单,没有涉及到括号,下面是 Java 版的代码:

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
class Solution {
private int priority(char c) {
if (c == '(')
return 3;
if (c == '*' || c == '/' || c == '%')
return 2;
if (c == '+' || c == '-')
return 1;
return 0;
}

private boolean isop(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '(';
}

private int cal(int a, char op, int b) {
switch (op) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '%':
return a % b;
default:
return 0;
}
}

public int calculate(String s) {
Deque<Integer> stack_num = new LinkedList<>();
Deque<Character> stack_op = new LinkedList<>();

for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int tmp_num = 0;
while (Character.isDigit(c)) {
tmp_num = tmp_num * 10 + c - '0';
++i;
if (i >= s.length())
break;
c = s.charAt(i);
}
stack_num.push(tmp_num);
}

if (isop(c)) {
if (!stack_op.isEmpty() && priority(stack_op.peek()) >= priority(c)) {
while (!stack_op.isEmpty() && priority(stack_op.peek()) >= priority(c) && stack_op.peek() != '(') {
char tmp_op = stack_op.pop();
int a = stack_num.pop();
int b = stack_num.pop();
stack_num.push(cal(b, tmp_op, a));
}
}
stack_op.push(c);
} else if (c == ')') {
while (!stack_op.isEmpty() && stack_op.peek() != '(') {
char tmp_op = stack_op.pop();
int a = stack_num.pop();
int b = stack_num.pop();
stack_num.push(cal(b, tmp_op, a));
}
stack_op.pop();
}
}

while (!stack_op.isEmpty()) {
char tmp_op = stack_op.pop();
int a = stack_num.pop();
int b = stack_num.pop();
stack_num.push(cal(b, tmp_op, a));
}
return stack_num.pop();
}
}

最后

将此算法稍作修改,即可拓展到计算浮点数运算式的加减乘除、乘方、取对数、开根号、求阶乘等等复杂的数学运算(大家可以想想如何修改),但是基本的思想是不变的。

参考资料

中缀表达式转换为后缀表达式
表达式树
根据表达式序列(前缀、中缀、后缀)构建表达式树

坚持原创技术分享,感谢您的支持和鼓励!