题目链接

772. 基本计算器 III

思路

与【栈】LeetCode 227. 基本计算器 II 完全相同

代码

class Solution {
    public int calculate(String s) {
        // 定义运算符优先级
        Map<Character, Integer> map = new HashMap<Character, Integer>(){{
            put('+', 1);
            put('-', 1);
            put('*', 2);
            put('/', 2);
            put('%', 2);
            put('^', 3);
        }};
        s = s.replaceAll(" ", "");

        Stack<Integer> numbers = new Stack<>();
        Stack<Character> operators = new Stack<>();
        char[] expression = s.toCharArray();

        for(int i = 0; i < expression.length; i++){
            char c = expression[i];
            if(c == '('){
                operators.push(c);
            }else if(c == ')'){
                while(!operators.isEmpty() && operators.peek() != '('){
                    calc(numbers, operators);
                }
                operators.pop();
            }else if(Character.isDigit(c)){
                int u = 0;
                int j = i;
                while(j < expression.length && Character.isDigit(expression[j])){
                    u = u * 10 + expression[j] - '0';
                    j++;
                }
                numbers.push(u);
                i = j - 1;
            }else{
                if(i > 0 && expression[i - 1] == '('){
                    numbers.push(0);
                }
                while(!operators.isEmpty() && operators.peek() != '('){
                    char prev = operators.peek();
                    if(map.get(prev) >= map.get(c)){
                        calc(numbers, operators);
                    }else{
                        break;
                    }
                }
                operators.push(c);
            }
        }

        while(!operators.isEmpty()){
            calc(numbers, operators);
        }

        return numbers.peek();
    }

    void calc(Stack<Integer> numbers, Stack<Character> operators){
        if(numbers.size() < 2){
            return;
        }
        if(operators.isEmpty()){
            return;
        }

        int second = numbers.pop();
        int first = numbers.pop();
        char c = operators.pop();

        switch(c){
            case '+':
                numbers.push(first + second);
                break;
            case '-':
                numbers.push(first - second);
                break;
            case '*':
                numbers.push(first * second);
                break;
            case '/':
                numbers.push(first / second);
                break;
            case '%':
                numbers.push(first % second);
                break;
            case '^':
                numbers.push((int)Math.pow(first, second));
                break;
        }
    }
}