力扣：面试题 16.26. 计算器

逆波兰式：是一种将运算符写在操作数之后的表达式表示方法，也称为后缀表达式‌。逆波兰表达式的求值方法是从左至右扫描表达式，遇到操作数则压栈，遇到运算符则从栈中弹出操作数进行运算，然后将运算结果压入栈中，重复该过程直到表达式结束，最后的结果为栈顶元素。‌逆波兰式的一个显著优点是它不需要括号来区分运算符的优先级，这使得表达式更加简洁且易于计算机处理。此外，逆波兰表达式的求值过程基于堆栈操作，相对于递归操作效率更高。

/**
 * 题目：面试题 16.26. 计算器
 * 难度：中等
 * 需求：给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
 * 表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
 * 原题链接： https://leetcode.cn/problems/calculator-lcci/description/
 */
public class Calculator {
    //定义优先级
    private static HashMap<Character, Integer> map = new HashMap<>(){
        {
            put('+', 1);
            put('-', 1);
            put('*', 2);
            put('/', 2);
        }
    };
    public static void main(String[] args) {
        int calculate = calculate("9+(3-1)*3+10/2");
        System.out.println(calculate);
    }

    /**
     * 逆波兰式（后缀表达式）
     */
    public static String getReversePolishNotation(String s) {
        Stack<Character> symbolStack = new Stack<>();//符号栈
        StringBuilder stringBuffer = new StringBuilder();//接收逆波兰表达式
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            //为空直接跳过
            if (c == ' ')
                continue;
            //为数字则入栈
            if (Character.isDigit(c)) {
                stringBuffer.append(c);
                //判断后续是否都为数字，如果是那么他们就是一个整体直到遇到下一次运算符或则括号
                while (i + 1 < charArray.length && Character.isDigit(charArray[i + 1])) {
                    stringBuffer.append(charArray[++i]);
                }
                //添加空格用于数字之间的隔离，否则无法进行大于9的数值计算
                stringBuffer.append(' ');
                continue;
            }
            //左括号直接进栈
            if (c == '(') {
                symbolStack.push(c);
                continue;
            }
            //右括号弹出括号内所有元素
            if (c == ')') {　　　　　　　　//循环直到遇到左括号
                while (symbolStack.peek() != '(') {
                    Character pop = symbolStack.pop();
                    stringBuffer.append(pop).append(' ');
                }　　　　　　　　//弹出左括号
                symbolStack.pop();
                continue;
            }
            //空栈直接入
            if (symbolStack.isEmpty()) {
                symbolStack.push(c);
                continue;
            }
            //如果栈顶是左括号直接入栈（前面有判断是否为数字所以走到这里的只可能是运算符）
            if (symbolStack.peek() == '(') {
                symbolStack.push(c);
                continue;
            }
            Integer ci = map.get(c);
            Integer si = map.get(symbolStack.peek());
            // 如果栈顶元素小于等于当前元素那就进入下面的循环，弹出所有优先级小于等于该运算符的符号
            if (ci <= si) {
//                判断栈顶运算符的优先级是否大大于当前运算符，如果大于则出栈，直到栈顶元素小于当前元素
                while (!symbolStack.isEmpty() && map.get(symbolStack.peek()) >= ci) {
                    Character pop = symbolStack.pop();
                    stringBuffer.append(pop).append(' ');
                }
                //将当前元素入栈
                symbolStack.push(c);
            } else {
                //如果当前运算符优先级大于栈顶运算符则直接入栈
                symbolStack.push(c);
            }
        }
        //判断栈内是否还有元素未出栈如果有则将他们全部弹出栈
        while (!symbolStack.isEmpty()) {
            Character pop = symbolStack.pop();
            stringBuffer.append(pop).append(' ');
        }
        return stringBuffer.toString().trim();
    }

    //计算逆波兰表达式
    public static int calculate(String s) {
        boolean isCalculate = false;//用于判断是否计算
        s = getReversePolishNotation(s);//转换为逆波兰式
        Stack<Integer> numberStack = new Stack<>();//数字栈
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            // 跳过空格
            if (charArray[i] == ' ') {
                continue;
            }
            // 遇到数字直接进栈
            if (Character.isDigit(charArray[i])) {
                int num = 0;
                //遍历后续多个数位
                while (i < charArray.length && Character.isDigit(charArray[i])) {
                    num = num * 10 + (charArray[i] - '0');
                    i++;
                }
                i--; // 回退一位，因为外部循环会再次递增i
                numberStack.push(num);
                continue;
            }
            // 遇到运算符直接计算，然后将结果再次压入栈中
            Integer num1 = numberStack.pop();
            Integer num2 = numberStack.pop();
            if (charArray[i] == '+') {
                numberStack.push(num2 + num1);
                isCalculate = true;
            } else if (charArray[i] == '*') {
                numberStack.push(num2 * num1);
                isCalculate = true;
            } else if (charArray[i] == '/') {
                numberStack.push(num2 / num1);
                isCalculate = true;
            } else if (charArray[i] == '-') {
                numberStack.push(num2 - num1);
                isCalculate = true;
            }
        }
        System.out.println(numberStack);
        //如果有计算直接弹出计算后的结果
        if (isCalculate) {
            return numberStack.pop();
        }
        //没有计算也就是传入的string没有运算符直接原封不动返回去
        return Integer.parseInt(s);
    }
}