中序表达式转为后序表达式

表达式根据运算符所在位置可分为三种：

• 前缀表达式（波兰式），如(- (+ 3 (* 2 4)) 1)，Lisp语言就是使用的这种表示方法
• 中缀表达式，如3+2*4-1，最适合人阅读的表示方法
• 后缀表达式（逆波兰式），如3 2 4 * + 1 -，计算机处理起来比较方便

E.W.Dijkstra 在 20 世纪 60 年代发明了一个非常简单的算法来计算中缀表达式，需要维护两个栈，一个是运算符栈，另一个是操作数栈。

表达式由括号、运算符和操作数（数字）组成。我们根据以下 4 种情况从左到右逐个将它们送入栈处理：

• 将操作数压入操作数栈；
• 将运算符压入运算符栈；
• 忽略左括号；
• 在遇到右括号时，弹出一个运算符，弹出所需数量的操作数，并将运算符和操作数的运算结果压入操作数栈。

在处理完最后一个右括号之后，操作数栈上只会有一个值，它就是表达式的值。

这个算法是怎么保证运算结果的正确性的呢？
每遇到一个被括号包围的表达式，都用它的值来替代它，这个值与表达式的值相同，反复利用这个规律得到的最终值就是整个表达式的最终值。

下面是 算法（第四版） 的代码：

public class Evaluate
{
    public static void main(String[] args)
    {
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        while (!StdIn.isEmpty())
        { // 读取字符，如果是运算符则压入栈
            String s = StdIn.readString();
            if (s.equals("(")) ;
            else if (s.equals("+")) ops.push(s);
            else if (s.equals("-")) ops.push(s);
            else if (s.equals("*")) ops.push(s);
            else if (s.equals("/")) ops.push(s);
            else if (s.equals(")"))
            { // 如果字符为 ")"，弹出运算符和操作数，计算结果并压入栈
                String op = ops.pop();
                double v = vals.pop();
                if (op.equals("+")) v = vals.pop() + v;
                else if (op.equals("-")) v = vals.pop() - v;
                else if (op.equals("*")) v = vals.pop() * v;
                else if (op.equals("/")) v = vals.pop() / v;
                vals.push(v);
            } // 如果字符既非运算符也不是括号，将它作为 double 值压入栈
            else vals.push(Double.parseDouble(s));
        }
        StdOut.println(vals.pop());
    }
}
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

计算后缀表达式很简单，只需要维护一个栈，让数字依次进栈，遇到运算符时，就弹出栈顶两个元素，将计算结果入栈，如图：

为了把较难处理的中缀表达式转化为容易处理的后缀表达式，Dijsktra（怎么又是他）引入了一个使用栈的算法，称为调度场算法。

为什么要是用栈呢？因为当处理 a+b 时，不知道下一个运算符是 * 还是 +，所以要先 + 号放到栈中，等后面有足够信息了再把 + 放出来。

Wikipedia调度场算法示意图。

算法示意图，使用了3个空间。输入用符号代替，如果输入是一个数字则直接进输出队列，即图中 b),d),f),h)。如果输入是运算符，则压入操作符堆栈，即图中 c),e)，但是，如果输入运算符的优先级低于或等于运算符栈顶的操作符优先级，则栈内元素进入输出队列，输入操作符压入运算符堆栈，即图中 g)。 最后，运算符堆栈内元素入输出队列，算法结束。

括号处理： 括号具有最高的优先级，所以遇到右括号时需要将括号内的所有运算符出栈。遇到左括号时要进栈，用来确定括号范围。

综上，可得调度场算法描述：

1. 读到数字：直接输出；
2. 读到一般运算符：如果栈顶的运算符优先级不低于该运算符，则输出栈顶运算符并使之出栈，直到栈空或不满足上述条件为止；然后入栈；
3. 读到左括号：直接入栈；
4. 读到右括号：输出栈顶运算符并使之出栈，直到栈顶为左括号为止；令左括号出栈。
5. 当读入完毕时，依次输出并弹出栈顶运算符，直到栈被清空。

例题：算法（第四版）习题1.3.10 与 习题1.3.11，计算后缀表达式并利用后序表达式求值。

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

import java.util.HashMap;
import java.util.LinkedList;

public class exercise1310 {
    private static boolean isNumeric(String s) {
        for (int i = 0; i < s.length(); ++i) {
            if (!Character.isDigit(s.charAt(i)))
                return false;
        }
        return true;
    }

    private static boolean isOperator(String s) {
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("^"))
            return true;
        return false;
    }

    public static void EvaluatePostfix(LinkedList<String> S) {
        Stack<Double> stack = new Stack<>();
        for (String s : S) {
            if (isOperator(s)) {
                double a = stack.pop();
                double b = stack.pop();
                switch (s) {
                    case "+":
                        stack.push(b + a);
                        break;
                    case "-":
                        stack.push(b - a);
                        break;
                    case "*":
                        stack.push(b * a);
                        break;
                    default:
                        stack.push(b / a);
                        break;
                }
            } else {
                stack.push(Double.parseDouble(s));
            }

        }
        StdOut.println(stack.pop());
    }

    public static LinkedList<String> InfixToPostfix(String[] S) {
        LinkedList<String> result = new LinkedList<>();
        int i = 0;
        Stack<String> stack = new Stack<>();
        HashMap<String, Integer> operAdv = new HashMap<>();
        operAdv.put("+", 1);
        operAdv.put("-", 1);
        operAdv.put("*", 2);
        operAdv.put("/", 2);
        for (String s : S) {
            if (s.equals("(")) {
                stack.push(s);
                continue;
            }
            if (s.equals(")")) {
                while (!stack.isEmpty() && !stack.peek().equals("(")) {
                    result.add(stack.peek());
                    StdOut.print(stack.pop() + " ");
                }
                stack.pop();
                continue;
            }
            if (isNumeric(s)) {
                result.add(s);
                StdOut.print(s + " ");
                continue;
            }
            if (isOperator(s)) {
                while (!stack.isEmpty() && (isOperator(stack.peek()) && operAdv.get(stack.peek()) >= operAdv.get(s))) {
                    result.add(stack.peek());
                    StdOut.print(stack.pop() + " ");
                }
                stack.push(s);
            }
        }
        for (String s : stack) {
            result.add(s);
            StdOut.print(s + " ");
        }
        StdOut.println();
        return result;
    }

    public static void main(String[] args) {
        String express = StdIn.readAll();
        express = express.substring(0, express.length() - 2);
        String[] S = express.split(" ");
        LinkedList<String> strings = InfixToPostfix(S);
        EvaluatePostfix(strings);
    }
}

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

运算结果：

( 1234 + 4 + 5 ) * 3 * 10 / 5 + 3
^Z
1234 4 + 5 + 3 * 10 * 5 / 3 +
7461.0

( 2 + 4 ) / ( 4 * ( 3 - 1 ) * 10 ) + 123
^Z
2 4 + 4 3 1 - * 10 * / 123 +
123.075
1
2
3
4
5
6
7
8
9