经典算法（五）逆波兰表达式

什么是波兰表达式

早在1920年，波兰科学家扬·武卡谢维奇就发明了一种不需要括号的表示法，可以用来表示一个计算表达式。即将操作符号写在操作数之前，也就是前缀表达式，即波兰式（Polish Notation, PN）。这种表达式直到1960年计算机出现后才发挥出其威力

比如2 + 3 * (5 - 1)这个表达式的前缀表达式为+ 2 * 3 - 5 1来表示。
阅读这个表达式需要从左至右读入表达式，如果一个操作符后面跟着两个操作数时，则计算，然后将结果作为操作数替换这个操作符和两个操作数，重复此步骤，直至所有操作符处理完毕。从左往右依次读取，直到遇到- 5 1，做计算后，将表达式替换为+ 2 * 3 4，然后从左往右再次读取，直到遇到* 3 4，做计算后将表达式替换为+ 2 12，然后从左往右依次读取，读到+ 2 12，计算得到14，到此结束。

可以看到，这种计算过程也相当复杂，需要多次遍历表达式，而且需要识别一个操作符后面跟着两个操作数这种模式，相比而言，下文中的逆波兰式要更为直接和简单。

什么是逆波兰表达式

即后缀表达式，更加广为人知一些，和前缀表达式刚好相反，是将操作符号放置于操作数之后

比如2 + 3 * (5 - 1)用逆波兰式来表示则是：2 3 5 1 - * +。
逆波兰式的计算也是从左往右依次读取，当读到操作符时，将之前的两个操作数做计算，然后替换这两个操作数和操作符，接着读取，重复此步骤。对于这个表达式，读到5 1 -，得到4，然后读取乘号，取出前面的3和上一步的计算结果4，并计算，到12，接着读取加号+，计算2 12 +得到14，计算结束。

上面这个步骤可以很容易的用栈来实现：
从左往右依次读取表达式，如果是数字则将该数字压栈，如果是符号，则将之前的两个数字出栈，做计算后，将计算结果压栈，直到表达式读取结束。栈中剩下的一个数就是计算结果

实现：

 //计算后缀表达式
    public static int calculateHouzhui(List<String> list){
        Stack<String> s=new Stack<String>();
        for(String ob:list){
            if(!operator.contains(ob)){
                s.add(ob);
            }else{
                String b=s.pop();
                String a=s.pop();
                String value=calculate(a, b, ob)+"";
                s.add(value);
            }
        }
        return Integer.parseInt(s.pop());
    }
    public static int calculate(String a,String b,String operator){
        int aa=Integer.parseInt(a);
        int bb=Integer.parseInt(b);
        if(operator.equals("+")){
            return aa+bb;
        }else if(operator.equals("-")){
            return aa-bb;
        }else if(operator.equals("*")){
            return aa*bb;
        }else if(operator.equals("/")){
            return aa/bb;
        }
        return 0;
    }

View Code

  中缀表达式转换为后缀表达式

 (1)当读到数字直接送至输出队列中
 (2)当读到运算符t时：
　　a. 将栈中所有优先级高于或等于t的运算符弹出，送到输出队列中；
　　　　注：这句话不好理解，可以说成这样，从栈顶开始，依次弹出操作符，如果操作符优先级大于或者等于t，则送到输出队列，如果比它优先级低的或者遇到了一个左括号就停止。并同时放这个运算符回到栈中
　　b. t进栈；
（3）读到左括号时总是将它压入栈中
（4）读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号和当前右括号
（5）中缀表达式全部读完后，若栈中仍有运算符，将其送到输出队列中

 举个栗子 中缀表达式：3+(2-5)*6/3

 后缀表达式转中缀表达式

思路：和计算后缀表达式类似。从左往右依次读取表达式，如果是数字则将该数字压栈，如果是符号，则将之前的两个数字出栈，拼接符号，并压栈，记录该符号栈，压栈之前与之前记录的操作符做比较。如果当前操作符大于记录值。则栈中表达式 需要加括号
举个栗子：后缀表达式 3+(2-5)*6/3