史上屌炸天超详细的Java实现逆波兰表达式

  人在做四则运算时感觉很简单，那是因为人类的脑瓜子很聪明 但是如果你想尝试用计算机按照人类的思维来计算简单的四则运算那就有点麻烦了！光是处理大小括号就喝一壶的了那么这时候一些智者就提出能不能把我们的表达式写成一种没有大小括号而且把运算符排好序的表达式，那么1929年由波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)提出的一种表达式表示的方法就很好的契合我们的思想

  中缀表达式：1+((2+3)*4)-5
  对应的逆波兰表达式：123+4*+5-

原理分析：

中缀表达式的运算规则上过小学应该都知道吧❓

先乘除后加减有括号先算括号里面的

那我们就从这个规则出发来一步步推导后缀表达式（逆波兰表达式）

第一步：算的是（2+3）它的后缀形式  23+（现在大家知道为什么叫中缀、后缀表达式了吧❗️是中是后看的是运算符在两个操作数的位置，在中就是中缀表达式，在后就是后缀表达式。中缀转后缀就是两个操作数不动把运算符提到后面，那前缀表达式就是提到前面！）第二步：算的是2+3的和与4做乘法，它对应的后缀是23+4*第三步：到了第三步大家可能就有疑惑了，因为((2+3)*4)前是与1做加法操作，后是与5做减法操作，好像先加后减、先减后加都行啊！？理论上确实如此，但是我们知道一个算法要具有确定性，就是同一个输入就必须有同一个输出，那么按照上面的说法同一个中缀表达式我们就会有两种不同的后缀表达式，这显然是不对的！所以这里我们要提一句，对应中缀转后缀我们要遵守左优先原则即左边可以先算就先算左边（中缀转前缀就是右优先原则）所以这时候的后缀表达式就应该是123+4*+第四步：123+4*+5-

总结：我们可以发现按照规则转换后的后缀表达式操作数的顺序是不会变的，因为我们本来就是把操作数固定不动的动的是运算符，变的是各个运算符的顺序，而且大小括号是没有的，因为按规则转出来的后缀表达式就包含了运算顺序！

废话少说直接上图

Java代码实现中缀表达式的计算

在实现代码前先说一下规则（要借助两个栈来实现）：

遇到操作数直接入数栈；遇到操作符:
(1) 如果符号栈为空或者栈顶元素为(，则直接入栈；
(2) 如果栈顶元素是操作符，则要依次弹出优先级大于等于当前操作符的操作符，每弹出一个操作符就要在数栈弹出两个操作符与之作运算，把结果在入栈数栈；
(3) 如果符号栈栈顶元素优先级小于当前，则直接入栈；遇到界限符：
(1) 遇到(直接入符号栈；
(2) 遇到)依次弹出符号栈元素直至符号栈为空或者遇到(为止
【注意：弹出的( 要丢弃不参与运算】

package stack;

import java.util.Scanner;
import java.util.Stack;

@SuppressWarnings("all")
public class PolandNotationFinal {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入要计算的数学表达式：");
        String expr = sc.next();
        int res = parseExpr(expr);
        System.out.printf("%s = %d", expr, res);
    }

    
    private static int parseExpr(String expr) {
        // 操作数栈
        Stack numberStack = new Stack<>();
        // 操作数栈
        Stack operatorStack = new Stack<>();

        // 记录多位数的字符串
        StringBuilder str = new StringBuilder();
        // 记录中缀表达式每个字符
        char c;

        // 扫描中缀表达式
        for (int i = 0; i < expr.length(); i++) {
            c = expr.charAt(i);

            // 如果c不是操作数
            if (c < 48 || c > 57) {
                // 如果符号栈为空或者栈顶元素为 “(” 则c直接入符号栈
                if (operatorStack.isEmpty() || "(".equals(String.valueOf(c)) || "(".equals(operatorStack.peek())) {
                    operatorStack.push(String.valueOf(c));
                } else if (")".equals(String.valueOf(c))) {
                    while (!"(".equals(operatorStack.peek())) {
                        cal(numberStack, operatorStack);
                    }
                    // 最后要把 “(” 弹出
                    operatorStack.pop();
                } else {
                    // 如果当前操作符优先级 > 符号栈栈顶元素的优先级则直接入栈
                    if (Priority.getPriority(String.valueOf(c)) > Priority.getPriority(operatorStack.peek())) {
                        operatorStack.push(String.valueOf(c));
                    } else {
                        // 当符号栈栈顶元素的优先级 >= 当前操作符优先级时进行计算
                        while (!operatorStack.isEmpty() &&
                                Priority.getPriority(operatorStack.peek()) >= Priority.getPriority(String.valueOf(c))) {
                            cal(numberStack, operatorStack);
                        }
                        // 把优先级 “>=” c的操作符弹出并运算完后要把c压入栈中
                        operatorStack.push(String.valueOf(c));
                    }
                }
            } else { // 如果是操作数
                // 每次记录新的多位数时，记得清空上次的记录
                str.setLength(0);
                while (i < expr.length() && (c = expr.charAt(i)) >= 48 && (c = expr.charAt(i)) <= 57) {
                    str.append(c);
                    i++;
                }
                // 注意：这里要进行 i-- 操作退回上一个索引，不然外层for循环还会进行 i++ 的操作，这样会跳过表达式字符
                i--;
                // 把多位数压入数栈
                numberStack.push(str.toString());
            }
        }

        while (!operatorStack.isEmpty()) {
            cal(numberStack, operatorStack);
        }

        return Integer.parseInt(numberStack.pop());
    }

    private static void cal(Stack numberStack, Stack operatorStack) {
        String operation = operatorStack.pop();
        int num1 = Integer.parseInt(numberStack.pop());
        int num2 = Integer.parseInt(numberStack.pop());
        int res = 0;

        switch (operation) {
            case "+":
                res = num2 + num1;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num2 * num1;
                break;
            case "/":
                res = num2 / num1;
                break;
            default:
                break;
        }
        numberStack.push(String.valueOf(res));
    }
}

class Priority {
    private static final int FIRST = 1;
    private static final int SECOND = 2;

    private Priority() {
    }

    @SuppressWarnings("all")
    public static int getPriority(String c) {
        int priority = 0;

        switch (c) {
            case "+":
            case "-":
                priority = FIRST;
                break;
            case "*":
            case "/":
                priority = SECOND;
                break;
        }
        return priority;
    }
}