LeetCode/com/zerroi/leetcode/Three22/BasicCalculator.java

package com.zerroi.leetcode.Three22;

import java.util.*;

public class BasicCalculator {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int res = solution.calculate("(1+(4+5+2)-3)+(6+8)");
        System.out.println("res = " + res);
    }
}

class Solution {
    private Map<Character, Integer> map = new HashMap<>();
    private Deque<Character> opQue = new LinkedList<>();
    private Deque<Integer> numQue = new LinkedList<>();

    private void compute() {
        int b = numQue.pollLast();
        int a = numQue.pollLast();
        int op = opQue.pollLast();
        int ans = 0;
        switch (op) {
            case '+':
                ans = a + b;
                break;
            case '-':
                ans = a - b;
                break;
            case '*':
                ans = a * b;
                break;
            case '/':
                ans = a / b;
                break;
            default:
                break;
        }
        numQue.addLast(ans);
    }

    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        map.put('+', 0);
        map.put('-', 0);
        map.put('*', 1);
        map.put('/', 1);
        map.put('(', -1);
        map.put(')', -1);
        numQue.addLast(0);
        char[] sArr = s.toCharArray();
        int n = sArr.length;
        for (int i = 0; i < n; i++) {
            // 截取数字
            if (sArr[i] >= '0' && sArr[i] <= '9') {
                int start = i;
                while (i < n && sArr[i] >= '0' && sArr[i] <= '9') {
                    ++i;
                }
                int num = Integer.parseInt(s.substring(start, i));
                numQue.addLast(num);
            }
            if (i >= n) {
                break;
            }
            // 如果是左括号直接入栈
            if (sArr[i] == '(') {
                opQue.addLast(sArr[i]);
            // 右括号一直计算知道找到左括号
            } else if (sArr[i] == ')') {
                while (opQue.peekLast() != '(') {
                    compute();
                }
                opQue.pollLast();
//                操作符
            } else {
                // 判断是否出现了(- 或者 (+这种情况,那么进行操作数栈补0
                if (i > 0 && sArr[i - 1] == '(') {
                    numQue.addLast(0);
                }
                // 如果当前操作符的优先级小于栈顶优先级
                if (!opQue.isEmpty() && map.get(opQue.peekLast()) >= map.get(sArr[i])) {
                    compute();
                }
                opQue.addLast(sArr[i]);
            }

        }

        // 如果最后还有元素要继续计算
        while (!opQue.isEmpty()) {
            compute();
        }

        return numQue.peekLast();

    }
}