🌕 🌗 227. 基本计算器 II

难度: 🌕 🌗

问题描述

---

解法

class Solution {
    public int calculate(String s) {
        // 思路：
        // 双栈 - 数字栈 + 运算符栈
        // 空格 - 跳过
        // 数字 - 直接压 数字栈
        // +- - 压栈前，计算前面的加减部分
        // */ - 压栈前，计算前面所有
        // 特别：
        // 防止出现前导 负号，需要加上 0 
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        int len = s.length();
        LinkedList<Character> operaS = new LinkedList<>();
        LinkedList<Integer> numS = new LinkedList<>();
        int index = 0;

        if(s.charAt(0) == '-') {
            numS.push(0);
        }

        while(index < len) {
            char c = s.charAt(index);
            // 1. 空格
            if(c == ' ') {
                index ++;
                continue;
            }
            // 2. 数字
            if(getSingleNum(c) >= 0) {
                int[] tmp = getNumber(s, len, index);
                numS.push(tmp[0]);
                index = tmp[1];
                continue;
            }
            // 3. 运算符
            while(!operaS.isEmpty() && map.get(c) <= map.get(operaS.peek())) {
                // 先运算前半部分
                cal(operaS, numS);
            }
            operaS.push(c);
            index ++;
        }

        while(!operaS.isEmpty()) {
            cal(operaS, numS);
        }
        return numS.peek();
    }

    private void cal(LinkedList<Character> operaS, LinkedList<Integer> numS) {
        char operator = operaS.pop();
        int b = numS.pop();
        int a = numS.pop();
        if(operator == '+') {
            numS.push(a + b);
        } else if(operator == '-') {
            numS.push(a - b);
        } else if(operator == '*') {
            numS.push(a * b);
        } else if(operator == '/') {
            numS.push(a/ b);
        }
    }

    private int[] getNumber(String s, int len, int left) {
        int val = getSingleNum(s.charAt(left));
        int right = left + 1;
        while(right < len) {
            int cur = getSingleNum(s.charAt(right));
            if(cur >= 0) {
                val = val * 10 + cur;
            } else {
                break;
            }
            right ++;
        }
        return new int[]{val, right};
    }

    private int getSingleNum(char c) {
        if(c >= '0' && c <= '9') {
            return c - '0';
        } else {
            return -1;
        }
    }
}

---

输出