复杂四则运算的中缀表达式转后缀表达式（逆波兰表达式）Java版

分析

逆波兰计算器的原理是使用逆波兰表达式（后缀表达式）来计算出表达式的值，我们人类能够熟练使用的是中缀表达式，比如2×(9+6/3-5)+4就是一个中缀表达式，程序可以通过后缀表达式方便的进行四则运算。 逆波兰计算器的计算过程为：从左到右扫描逆波兰表达式，遇到数字就入栈，遇到操作符就从栈弹出两个数字，然后计算得到的值继续入栈，继续扫描表达式，直到扫描完毕得到结果。

例如前缀表达式3+2*{1+2*[-4/(8-6)+7]}可以转化为后缀表达式3212-486-/7+*+*+。后缀表达式中不含有括号，因为后缀表达式本身包含了运算优先级信息。但是如何将一个中缀表达式转换成一个后缀表达式呢？

这个过程已经有大神给出来了，我们记下来即可：

1. 初始化运算符栈stack，以及存储结果的字符串result；

2. 从左到右扫描中缀表达式的每一个字符c；

3. 若c是操作数，则直接加到结果字符串result中；

4. 若c是运算符：

   1）如果stack为空或c是左括号(，则将c压入到stack，(压入栈后优先级变为最低；
   2）不满足1），则把运算符c和stack栈顶运算符比较优先级，若c高于栈顶字符的优先级，则将c压入stack；
   3）不满足1）和2），弹出stack栈顶运算符，并将该运算符加到结果字符串result中，再次回到2）进行判断。

5. 遇到右括号)时，依次弹出stack中的运算符，并将这些运算符加到结果字符串result中，直到遇到左括号(为止，此时弹出(但不加入到result中（右括号)全程不入栈）；

6. 重复2-5，直到扫描完毕；

7. 若stack不为空，则依次弹出stack中元素，加入到result中

但是上述方法有一个缺点，就是不好处理负数的四则运算，因为负数的负号会被认为是运算符；同时，多位数的处理也会增加相应的处理逻辑。所以我们将原中缀表达式通过简单词法分析，转化为一个ArrayList，将负数和多位数转化为运算数，然后直接处理运算数。

所以对一个中缀表达式的计算过程可分为：

1. 词法分析，处理负数和多位数
2. 转化为逆波兰表达式
3. 通过逆波兰表达式进行四则运算

代码：

public class ReversePolishNotation {
    /**
     * 中缀表达式四则运算方法
     * @param pn 中缀表达式
     * @return 运算结果
     */
    public static int calculate(String pn){
        ArrayList<String> rpn = getRPN(pn);
        Stack<String> stack = new Stack<>();
        for (String s : rpn) {
            if(!isOperator(s)){
                stack.push(s);
            } else{
                int after = Integer.parseInt(stack.pop());
                int before = Integer.parseInt(stack.pop());
                switch (s){
                    case "+":
                        stack.push(before + after + "");
                        continue;
                    case "-":
                        stack.push(before - after + "");
                        continue;
                    case "*":
                        stack.push(before * after + "");
                        continue;
                    case "/":
                        stack.push(before / after + "");
                        continue;
                }
            }
        }
        return Integer.parseInt(stack.peek());
    }

    /**
     * 获取逆波兰表达式方法
     * @param pn 中缀表达式
     * @return ArrayList
     */
    public static ArrayList<String> getRPN(String pn){
        ArrayList<String> lexicalList = lexical(pn);
        ArrayList<String> result = new ArrayList<>(lexicalList.size());
        Stack<String> stack = new Stack<>();
        for (String s : lexicalList) {
            // 判断是数字还是操作符
            if(!isOperator(s)){
                result.add(s);
            } else{
                if(stack.isEmpty() || "(".equals(s)){
                    stack.push(s);
                } else if (")".equals(s)){
                    while (!"(".equals(stack.peek())){
                        result.add(stack.pop());
                    }
                    stack.pop();
                } else if(getPriority(s) > getPriority(stack.peek())){
                    stack.push(s);
                } else {
                    while (!stack.isEmpty() && getPriority(s) <= getPriority(stack.peek())){
                        result.add(stack.pop());
                    }
                    stack.push(s);
                }
            }
        }
        while (!stack.isEmpty()){
            result.add(stack.pop());
        }
        return result;
    }

    /**
     * 操作符优先级方法
     * @param str 操作符
     * @return '+''-'操作符返回1; '*''/'操作符返回2; '('返回-1
     */
    public static int getPriority(String str){
        switch (str){
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
        }
        return -1;
    }
	// 判断当前字符是否是运算符
    public static boolean isOperator(String str){
        return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str) || "(".equals(str) || ")".equals(str);
    }

    /**
     * 词法分析方法
     * @param pn 中缀表达式
     * @return ArrayList
     */
    public static ArrayList<String> lexical(String pn){
        pn = pn.replace("[", "(").replace("{", "(").replace("]", ")").replace("}", ")");
        ArrayList<String> list = new ArrayList();
        String tempNum = "";
        for (int i = 0; i < pn.length(); i++) {
            char c = pn.charAt(i);
            if(Character.isDigit(c)){
                tempNum += c;
                if(i == pn.length() - 1 || !Character.isDigit(pn.charAt(i + 1))){
                    list.add(tempNum);
                    tempNum = "";
                }
            } else if(c == '-' && (i == 0 || pn.charAt(i - 1) == '(')){
                tempNum += c;
            } else {
                list.add(c + "");
            }
        }
        return list;
    }
}
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