1.什么是后缀表达式

百度百科：

实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？
原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。
相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

后缀表达式就通过一定的排列顺序，将一个我们平时一眼就能看明白的数学算式转变为机器能够读懂的表达式。

例如：

  • 10 + 5 * 3转变为后缀表达式就是10 5 3 * +
  • (5 + 3) * 2转变为后缀表达式就是5 3 + 2 *

2.构建后缀表达式

2.1.前缀表达式转后缀表达式的规则

我们先用5 - ( 3 + 4 ) * 2 / 7来进行转换

  1. 先构造一个模拟栈 stack，和一个模拟队列 queue，栈中存放的是临时运算符，队列存放的就是后缀表达式
  2. 首先取出第一个字符 5，因为是数字，我们直接入队列。
    队列中现在就是{ 5 }
  3. 第二个字符是运算符 -，由于当前栈里没有元素，直接入栈。
    栈中现在就是[ - ]
  4. 第三个字符是运算符 (，由于是开括号，运算级别最高，所以直接入栈。
    栈中现在就是[ -, ( ]
  5. 第四个字符是数字 3，直接入队列。
    队列中现在就是{ 5, 3 }
  6. 第五个字符是运算符 +，由于栈顶是开括号，直接入栈。
    栈中现在就是[ -, (, + ]
  7. 第六个字符是数字4，直接入队列。
    队列中现在就是{ 5, 3, 4 }
  8. 第七个字符是闭合（右）括号，这时就要将栈中所有运算符弹出来存进队列，结束条件就是当栈顶碰到开括号，所以循环以后栈为空。注意：开括号也需要弹出来，但是不用入队列
    • 队列中现在就是{ 5, 3, 4, + }。栈中现在就是[ - ]
  9. 第八个字符是运算符*，和栈顶运算符进行比较，当前等级比栈顶的等级高，入栈。
    栈中现在就是[ -, * ]
  10. 第九个字符是数字2，直接入队列。队列中现在就是{ 5, 3, 4, +, 2}
  11. 第十个字符是运算符/，和栈顶运算符进行比较，当前等级和栈顶同等级。
    • 栈顶弹出入队列。{ 5, 3, 4, +, 2, *}。
      栈中现在就是[ - ]
    • 再继续和栈顶运算符（-）比较，当前等级比栈顶的等级高，入栈。
      栈中现在就是[ -, / ]
  12. 第十一个字符是数字7，直接入队列。
    队列中现在就是{ 5, 3, 4, +, 2, *, 7}
  13. 中缀表达遍历完毕，但是栈中可能还有运算符没有出来，所以我们需要把栈中的元素一次放入队列。
    最后的队列就是{ 5, 3, 4, +, 2, *, 7, /, -}

这里要注意的就是，第十步中，和栈顶比较玩以后还要继续和新的栈顶进行比较，直到当前的运算符比栈顶等级高或栈为空为止

2.2.编码（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
public static final String DIGITAL = "01234567890.";
public static final String H_OPERATOR = "*×/÷";
public static final String L_OPERATOR = "+-";

public static Queue<String> buildExpression(String originExpr) {
    String temp = "";
    // 后缀表达式
    Deque<String> suffix = new LinkedList<>();
    // 临时栈，用来存储括号里的表达式
    Stack<Character> stack = new Stack<>();
    Character c = null;
    for (int i = 0; i < originExpr.length(); i++) {
        c = originExpr.charAt(i);
        if (DIGITAL.indexOf(c) >= 0) {
            // 如果遇到数字字符
            for (; i < originExpr.length(); i++) {
                // 循环遍历后面的字符，将所有连续的数字整合为一个数值
                c = originExpr.charAt(i);
                if (DIGITAL.indexOf(c) >= 0) {
                    temp += c;
                } else {
                    break;
                }
            }
            suffix.add(temp);
            temp = "";
            i--;
        } else if ("(".indexOf(c) >= 0) {
            // 如果遇到的是左括号, 直接放入栈中
            stack.push(c);
        } else if (")".indexOf(c) >= 0) {
            // 如果遇到右括号
            // 将栈里的所有字符都依次取出，直到碰到左括号
            while (!stack.isEmpty() && stack.peek() != '(') {
                suffix.add(stack.pop().toString());
            }
            // 弹出左括号
            stack.pop();
        } else if (H_OPERATOR.indexOf(c) >= 0 || L_OPERATOR.indexOf(c) >= 0) {
            // 遇到运算符
            if (stack.isEmpty() || "(".indexOf(stack.peek()) >= 0) {
                // 如果栈为空 或 为开括号，直接入栈
                stack.push(c);
            } else {
                // 如果栈顶为高等级运算符，或同低等级
                while (!stack.isEmpty() && doPop(stack.peek(), c)) {
                    // 栈顶运算符出栈
                    suffix.add(stack.pop().toString());
                }
                // 当前运算符入栈
                stack.push(c);
            }
        }
    }
    while (!stack.isEmpty()) {
        suffix.add(stack.pop().toString());
    }
    return suffix;
}

/**
 * 判断栈顶是否为高等级运算符，或者是否同低等级
 * @param stackTop 栈顶元素
 * @param c 当前元素
 * @return 是否需要进行栈顶弹出入队列
 */
public static boolean doPop(Character stackTop, Character c) {
    if ((H_OPERATOR.indexOf(stackTop) >= 0)
        || (L_OPERATOR.indexOf(stackTop) >= 0 && L_OPERATOR.indexOf(c) >= 0)) {
        return true;
    }
    return false;
}

代码还有优化空间，如加入负数的运算，优化代码结构等，这里没有直接将队列转为字符串是因为为了方便进行后缀表达式的计算

3.对后缀表达式进行四则运算

3.1.后缀表达式解析规则

后缀表达式的运算就相对简单了，我们只需要遍历队列就行，遇到数字入栈，遇到运算符就对最上面两个数字进行四则运算

如上面的我们计算出来的后缀表达式是 { 5, 3, 4, +, 2, *, 7, /, -}

  1. 因为前三位都是数字，直接入栈。栈[5, 3, 4]
  2. 第四位是+运算符，计算栈中最上面两个，就是3 + 4，将结果7再入栈，栈[5, 7]
  3. 第五位是数字2，入栈。栈[5, 7, 2]
  4. 第六位是*运算符，计算7 * 2，结果入栈。栈[5, 14]
  5. 第七位是数字7，入栈。栈[5, 14, 7]
  6. 第八位是/运算符，计算14 / 7，结果入栈。栈[5, 2]
  7. 第八位是-运算符，计算5 / 2，结果入栈。栈[3]

遍历结束，所以最后的结果就是栈顶的3

这里需要注意的一点就是，进行除法的运算时，先取出来的数是除数，第二个数才是被除数，如上面的第六步

3.2.编码（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
public static Double calcExpression(Queue<String> suffixExpr) {
    String regx = "-?[0-9]+(\\.[0-9]+)?";
    Stack<Double> stack = new Stack<>();
    String expr = "";
    while (!suffixExpr.isEmpty()) {
        expr = suffixExpr.poll();
        if (expr.matches(regx)) {
            // 遇到数值
            stack.push(Double.parseDouble(expr));
        } else if (L_OPERATOR.indexOf(expr) >= 0 || H_OPERATOR.indexOf(expr) >= 0) {
            // 遇到运算符
            // 取出第一和第二个数值
            double x = stack.pop();
            double y = stack.pop();
            if (expr.equals("-")) {
                stack.push(y - x);
            } else if (expr.equals("+")) {
                stack.push(y + x);
            } else if ("*×".indexOf(expr) >= 0) {
                stack.push(y * x);
            } else if ("/÷".indexOf(expr) >= 0) {
                if (x == 0) {
                    throw new ArithmeticException("/ by zero");
                }
                stack.push(y / x);
            }
        }
    }
    return stack.pop();
}