课后习题+面试题：用栈和队列实现表达式解析

表达式解析求值，是一个编译器非常重要的能力。本身表达式求值解析，是一个非常复杂的过程。为了将问题简化，思考一个只有整数和加减乘除的表达式，请你使用上节课学习的队列和栈，对它进行求值。

例如：

输入： 1+2 * 3 * 5 + 4 ，得到对应的结果。

然后实现一个交互是的输入控制台，例如：

expr> 1 + 2 * 3 + 4

11

expr> _

解析

可以思考，如果1+2*3+4转化为 1 2 3 * 4 + + 就可以使用栈进行计算。

下面是计算过程，将1 2 3 * 4 + + 依次入栈，如果遇到符号（+-*/)等，就从栈中取出两个元素进行计算，如下图：

那么如何将1 + 2*3 + 4这样的表达式转化为1 2 3 * 4 + +这样的表达式呢？同样需要一个栈。乘号的优先级高，加号优先级低。

遇到高优先级的操作符，应该先入栈，然后遇到低优先级的操作符，就把之前入栈的高优先级操作符出栈，这样就解决了操作符之间的顺序。

最终结果需要一个队列存储，算法还是从左到右处理所有的输入：

1 2 3 4 在队列中的顺序不会发生变化，只不过插入操作符的时机需要把握。

遇到第1个+号时，栈中没有更高优先级的符号，将+号入栈；遇到第1个乘号时，栈中没有更高优先级的符号，将乘号入栈；遇到最后一个+号时，先将乘号出栈，加入队列，再入栈+号，如下图所示：

最终栈中剩余两个+号，都放入队列，就构造了1 2 3 * 4 + + 这个结果。

public class Expr {

    static Queue<String> prefixTransform(String expr) {

        var queue = new Queue<String>();
        var highPriorityStack = new Stack<String>();

        var prts = expr.replaceAll("[+-/*]+", "#$0#")
                .split("#");

        for(var prt : prts) {
            if(prt.matches("\\d+")) {
                queue.enqueue(prt);
            }
            else if(prt.equals("+") || prt.equals("-")) {
                while(highPriorityStack.size() > 0) {
                    var op = highPriorityStack.pop();
                    if(op.equals("*") || op.equals("/")) {
                        queue.enqueue(op);
                    } else {
                        highPriorityStack.push(op);
                        break;
                    }
                }
                highPriorityStack.push(prt);
            } else if(prt.equals("*") || prt.equals("/")) {
                highPriorityStack.push(prt);
            }
        }
        while(highPriorityStack.size() > 0) {
            queue.enqueue(highPriorityStack.pop());
        }
        System.out.println(queue.toString());
        return queue;
    }

    public static Integer eval(String expr) {

        // 1 + 2 * 3 + 4 -> 1 2 3 * 4 + +
        var queue = prefixTransform(expr);
        
        var stack = new Stack<Integer>();
        while(queue.size() > 0) {
            var item = queue.dequeue();
            if(item.matches("\\+|-|\\*|/")) {
                switch (item) {
                    case "+":
                        stack.push(stack.pop() + stack.pop());
                        break;
                    case "-" :
                        stack.push(stack.pop() - stack.pop());
                        break;
                    case "*":
                        stack.push(stack.pop() * stack.pop());
                        break;
                    case "/":
                        stack.push(stack.pop() / stack.pop());
                        break;
                }

            } else {
                stack.push(Integer.parseInt(item));
            }
        }

        return stack.pop();
    }

    public static void main(String[] argv) throws IOException {

        var scanner = new Scanner(System.in);
        while(true) {
            System.out.print("enter>");
            var expr = scanner.nextLine();
            var value = eval(expr);
            System.out.println(value);
        }
    }

}