题目

给定一个包含正整数、加(+)、减(-)、乘()、除(/)的算数表达式(包含括号)，计算其结果。
表达式仅包含非负整数，+， - ，，/ ，（，）六种运算符和空格 。 整数除法仅保留整数部分。
URL：https://leetcode.cn/problems/basic-calculator-iii/

题目示例

解题思路

• 设置两个栈，一个栈存储数字，一个栈存储运算符
• 遍历字符串，数字写入到数字栈，运算符写入运算符栈
• 当要入栈的运算符比运算符栈顶运算符优先级低时，则出栈计算，否则，入栈。所有运算字符的优先级都比左括号高。当遍历遇到左括号则入栈，右括号时，则出栈计算。

难点

• 字符数据转换为数字
• 运算符栈优先级判断、出入栈计算时机
• 左右括号和普通运算符的优先级

示例

public class CalculateV2 {
    /**
     * 存放数字
     */
    private Stack<Integer> numStack = new Stack<>();
    /**
     * 存放运算法
     */
    private Stack<Character> opsStack = new Stack<>();

    public int calculate(String s) {
        int i = 0;
        int size = s.length();
        while (i < size) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                i++;
                continue;
            }
            if (Character.isDigit(ch)) {
                int num = 0;
                while (i < size && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i) - '0');
                    i++;
                }
                numStack.push(num);
                continue;
            }
            if(ch == '(') {
                opsStack.push(ch);
                i++;
                continue;
            }
            if (ch == ')') {
                while (!opsStack.isEmpty() && opsStack.peek() != '(') {
                    getOpsAndCalculate(numStack, opsStack);
                }
                opsStack.pop();
                i++;
                continue;
            }

            if (opsStack.isEmpty() || prior(ch, opsStack.peek())) {
                opsStack.push(ch);
                i++;
                continue;
            }
            while (!opsStack.isEmpty() && !prior(ch, opsStack.peek())) {
                getOpsAndCalculate(numStack, opsStack);
            }
            opsStack.push(ch);
            i++;
        }

        while (!opsStack.isEmpty()) {
            getOpsAndCalculate(numStack, opsStack);
        }
        return numStack.pop();
    }

    /**
     * 比较a b运算符的优先级
     * 如果a的优先级大于b，返回true, 否则返回false
     *
     * @param a
     * @param b
     * @return
     */
    private boolean prior(char a, char b) {
        if ((a == '*' || a == '/') && (b == '+' || b == '-')) {
            return true;
        }
        if (b == '(') {
            return true;
        }
        return false;
    }

    private void getOpsAndCalculate(Stack<Integer> numStack, Stack<Character> opsStack) {
        int num2 = numStack.pop();
        int num1 = numStack.pop();
        char op = opsStack.pop();
        int calResult = 0;
        switch (op) {
            case '+':
                calResult = num1 + num2;
                break;
            case '-':
                calResult = num1 - num2;
                break;
            case '*':
                calResult = num1 * num2;
                break;
            case '/':
                calResult = num1 / num2;
                break;
            default:
        }
        numStack.push(calResult);
    }
}