ChunNote
0%

后缀表达式

发表于 分类于

简介

后缀表达式也叫逆波兰表达式，主要是用来进行表达式运算的。数学中对表达式进行求解，都是使用中缀表达式，如：2 * (3 + 4) - 5 这易于人们理解，但是不易于程序编写。在编写程序进行表达式求解时，一般都是先将表达式由中缀表达式转成后缀表达式，再结合栈进行求解。因为后缀表达式可以直接取出括号而对结果没有影响。例如：中缀表达式 2 * (3 + 4) - 5 ，其对应的后缀表达式为 2 ( 3 4 + ) * 5 -，可以简写为 2 3 4 + * 5 -

算法

将中缀表达式转成后缀表达式的算法如下：

  • 用一个栈来存储操作运算符：+、-、*、/、(

  • 遍历中缀表达式字符串，针对每个元素（数字、小括号或运算符，这里数字可以是多位数字），进行以下操作

    • 如果是数字，直接输出
    • 如果是括号或运算符
      • 如果栈为空，直接进栈
      • 如果栈不为空，获取栈顶元素与当前元素判断
        • 如果当前元素是 ( 或者当前元素的优先级大于栈顶元素的优先级，则将当前元素进栈
        • 如果当前元素是 )，则从栈中循环取出栈顶元素输出，直到遇到 (，将 ( 弹出（不输出）
        • 如果当前元素优先级不大于栈顶元素优先级，则从栈中循环取出栈顶元素输出，直到栈顶元素优先级小于当前元素或栈为空（定义左小括号的优先级最低），然后将当前元素入栈

  • 待遍历结束后，判断栈中元素是否为空，如果非空，则将栈中元素依次弹出输出

例子

一个简单的例子代码如下，假设输入的表达式是合法的。

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
107
108
109
110
111
112
113
114
115
116
117
118
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TestRpn
{
    /**
     * 中序表达式转后序表达式
     *
     * @param exp 中序表达式，只包含数字，+，-，*，/，(，)，且保证表达式合法
     * @return 后序表达式元素列表，每个元素按顺序组合就能形成后序表达式字符串
     */
    public List<String> convertInOrder2PostOrder(String exp)
    {
        Stack<Character> opStack = new Stack<>();
        List<String> result = new ArrayList<>();
        int num = 0;
        boolean isAddNum = false;
        boolean isNegative = false;
        for (int i = 0; i < exp.length(); i++)
        {
            char ch = exp.charAt(i);
            if (Character.isDigit(ch))
            {
                isAddNum = true;
                num = num * 10 + (ch - '0');
                continue;
            }

            if (isAddNum)
            {
                if (isNegative)
                {
                    result.add(String.valueOf(-num));
                }
                else
                {
                    result.add(String.valueOf(num));
                }
                num = 0;
                isAddNum = false;
                isNegative = false;
            }

            if (ch == '(')
            {
                opStack.push(ch);
            }
            else if (ch == ')')
            {
                while (!opStack.isEmpty() && opStack.peek() != '(')
                {
                    result.add(String.valueOf(opStack.pop()));
                }
                opStack.pop();
            }
            else
            {
                if (ch == '-' && (i == 0 || (!Character.isDigit(exp.charAt(i - 1)) && exp.charAt(i - 1) != ')')))
                {
                    isNegative = true;
                    continue;
                }

                while (!opStack.isEmpty() && !isHigh(ch, opStack.peek()))
                {
                    result.add(String.valueOf(opStack.pop()));
                }
                opStack.push(ch);
            }

        }

        if (isAddNum)
        {
            if (isNegative)
            {
                result.add(String.valueOf(-num));
            }
            else
            {
                result.add(String.valueOf(num));
            }
        }
        while (!opStack.isEmpty())
        {
            result.add(String.valueOf(opStack.pop()));
        }

        return result;
    }

    /**
     * 判断第一个操作符的优先级是否高于第二个操作符
     *
     * @param firstOp  第一个操作符
     * @param secondOp 第二个操作符
     * @return true，第一个操作符优先级高于第二个操作符，false：第一个操作符优先级小于等于第二个操作符
     */
    private boolean isHigh(char firstOp, char secondOp)
    {
        if (secondOp == '(')
        {
            return true;
        }

        return (firstOp == '*' || firstOp == '/') && (secondOp == '+' || secondOp == '-');
    }

    public static void main(String[] args)
    {
        String exp = "32*9/3+(233-31)*8";
        System.out.println(new TestRpn().convertInOrder2PostOrder(exp));
        // 输出如下
        // [32, 9, *, 3, /, 233, 31, -, 8, *, +]
    }
}