Java基础学习之数据结构：利用栈和队列完成表达式解析

在阅读本篇文章之前，相信大家对栈和队列的概念已经有了基本的认识。何为栈？栈就是一种“先进后出”存储数据的结构，即最先进栈的数据，最后出栈；

通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素

而队列是使用队列存储数据，讲究 “先进先出”，即最先进队列的数据，也最先出队列。通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”

关于更多栈和队列的知识点可以参考这里去学习
http://c.biancheng.net/data_structure/stack_queue/

表达式解析求值，是一个编译器非常重要的能力。本身表达式求值解析，是一个非常复杂的过程。针对用户输入的表达式字符串，我们如何通过程序将其计算出来。其实现在很多自带的语言会有计算的方法，但是具体又是怎么实现的呢？为了将问题简化，我们可以思考一个只有整数和加减乘除的表达式：
例如：

输入： 1+2 * 3 * 5 + 4 ，得到对应的结果。然后实现一个交互是的输入控制台，
例如： expr> 1 + 2 * 3 + 4
11

可以思考，如果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 + + 这个结果。

    
  static Queue prefixTransform(String expr) {

        Queue queue = new Queue();
        Stack highPriorityStack = new Stack();

        String[] prts = expr.replaceAll("[+-
    public static Integer eval(String expr) {
        Queue queue=prefixTransform(expr);
        Stack stack=new Stack<>();
        while(queue.size()>0){
            String charC=queue.dequeue();
            switch(charC) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                // 先入栈的为被减数
                    int minuend=stack.pop();
                    int minus=stack.pop();
                    stack.push(minus- minuend);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                // 先入栈的为被除数
                    int divided=stack.pop();
                    int divisor=stack.pop();
                    stack.push(divisor / divided);
                    break;
                default:
                    stack.push(Integer.valueOf(charC));
            }
        }
        return stack.pop();
    }

这样一个简单的加减乘除计算器就完成了，✌