blog

逆波兰表达式

发表于 更新于 分类于
逆波兰表达式

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

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

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

从一个简单题目谈起

【问题描述】

从标准输入中读入一个整数算术运算表达式，如 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();
    }
}

最后

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

参考资料

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

相关文章推荐
坚持原创技术分享，感谢您的支持和鼓励！