逆波兰表达式、波兰表达式

1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:- × + 3 4 5 6
2.中缀表达式就是常见的运算表达式，如(3+4)×5-6
3.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,比如:3 4 + 5 × 6

一.通过逆波兰表达式计算结果

我们先看一个例子...后缀表达式3 4 + 5 × 6 -的计算
1.从左至右扫描，将3和4压入堆栈；
2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；
3.将5入栈；
4.接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
5.将6入栈；
6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

 /**
     * 通过逆波兰表达式计算结果
     * @param ls
     * @return
     */
     //求逆波兰表达式的值
    public static int calcRevPolishNotation(String express){
        Stack<String> stack = new Stack<>();
        for (int i = 0; i <express.length() ;i++) {
            // 普通数值的处理
            if ((express.charAt(i) + "").matches("\\d")){
                stack.push(express.charAt(i) + "");
            // + - * / 运算符的处理
            }else if ((express.charAt(i) + "").matches("[\\+\\-\\*\\/]")){
                String k1 = stack.pop();
                String k2 = stack.pop();
                // 计算结果
                int res = calcValue(k1, k2, (express.charAt(i) + ""));
                stack.push(res+"");
            }

        }
        return Integer.valueOf(stack.pop());
    }

     //根据运算符计算结果
    private static int calcValue(String k1, String k2, String c) {
        switch(c){
            case "+":
                return Integer.valueOf(k1)+Integer.valueOf(k2);
            case "-":
                return Integer.valueOf(k2)-Integer.valueOf(k1);
            case "*":
                return Integer.valueOf(k1)*Integer.valueOf(k2);
            case "/":
                return Integer.valueOf(k2)/Integer.valueOf(k1);
            default:
                throw new RuntimeException("没有该类型的运算符！");
        }
    }

 

二.中缀表达式转换为后缀表达式（逆波兰表达式）

中缀表达式转后缀表达式主要用到了栈进行运算符处理，队列进行排序输出，规则为：

1.数字直接入队列
2.运算符要与栈顶元素比较
 ①栈为空直接入栈
 ②运算符优先级大于栈顶元素优先级则直接入栈
 ③小于或等于则出栈入列，再与栈顶元素进行比较，直到运算符优先级小于栈顶元
    素优先级后，操作符再入栈
3.操作符是 ( 则无条件入栈
4.操作符为 )，则依次出栈入列，直到匹配到第一个(为止，此操作符直接舍弃，(直接出栈舍弃

/**
     * 将中缀表达式转换为后缀表达式（逆波兰表达式）
     * @param express
     * @return
     */
    public static String transfer(String express){
        Stack<String> stack = new Stack<>();
        List<String> list= new ArrayList<>();
        for (int i=0;i<express.length();i++){
            if ((express.charAt(i)+"").matches("\\d")){
                list.add(express.charAt(i)+"");
            }else if((express.charAt(i)+"").matches("[\\+\\-\\*\\/]")){
                //如果stack为空
                if (stack.isEmpty()){
                    stack.push(express.charAt(i)+"");
                    continue;
                }
                //不为空

                //上一个元素不为（，且当前运算符优先级小于上一个元素则，将比这个运算符优先级大的元素全部加入到队列中
                while (!stack.isEmpty()&&!stack.lastElement().equals("(")&&!comparePriority(express.charAt(i)+"",stack.lastElement())){
                    list.add(stack.pop());
                }
                stack.push(express.charAt(i)+"");
            }else if(express.charAt(i)=='('){
                //遇到左小括号无条件加入
                stack.push(express.charAt(i) + "");
            }else if(express.charAt(i)==')'){
                //遇到右小括号，则寻找上一堆小括号，然后把中间的值全部放入队列中
                while(!("(").equals(stack.lastElement())){
                    list.add(stack.pop());
                }
                //上述循环停止，这栈顶元素必为"("
                stack.pop();
            }
        }
        //将栈中剩余元素加入到队列中
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        StringBuffer stringBuffer = new StringBuffer();
        //变成字符串
        for (String s : list) {
            stringBuffer.append(s);
        }
        return stringBuffer.toString();
    }

    /**
     * 比较运算符的优先级
     * @param o1
     * @param o2
     * @return
     */
    public static boolean comparePriority(String o1,String o2){
        return getPriorityValue(o1)>getPriorityValue(o2);
    }

    /**
     * 获得运算符的优先级
     * @param str
     * @return
     */
    private static int getPriorityValue(String str) {
        switch(str){
            case "+":
                return 1;
            case "-":
                return 1;
            case "*":
                return 2;
            case "/":
                return 2;
            default:
                throw new RuntimeException("没有该类型的运算符！");
        }
    }

 

参考链接

https://www.jianshu.com/p/649c12a80fe8