[刷题防痴呆] 0227 - 简单计算器II (Basic Ca

题目地址

https://leetcode.com/problems/basic-calculator-ii/

题目描述

227. Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "3+2*2"
Output: 7
Example 2:

Input: s = " 3/2 "
Output: 1
Example 3:

Input: s = " 3+5 / 2 "
Output: 5

思路

• 跟着三叶的答案, 复盘做法.
• 双栈, 一个存放nums, 一个存放ops.
• 先添加一个0, 防止第一个数是负数.
• 换掉所有空格.
• 左括号直接加入ops, 右括号开始计算, 算到左括号, 计算结果加入nums.
• 数字连续取到最后一个, 加入nums.
• 数学计算符号, 进行计算, 结果加入nums.

关键点

• 注意, edge case有可能括号里第一个字符为运算符, 可以加个0进入nums.

代码

• 语言支持：Java

class Solution {
    Map<Character, Integer> map = new HashMap<>();
    
    public int calculate(String s) {
        initMap();
        s = s.replaceAll(" ", "");
        Deque<Integer> numStack = new ArrayDeque<>();
        Deque<Character> opStack = new ArrayDeque<>();
        numStack.push(0);
        char[] sc = s.toCharArray();
        int n = sc.length;
        for (int i = 0; i < n; i++) {
            char c = sc[i];
            if (c == '(') {
                opStack.push(c);
            } else if (c == ')') {
                while (!opStack.isEmpty()) {
                    if (opStack.peek() == '(') {
                        opStack.poll();
                        break;
                    } else {
                        cal(numStack, opStack);
                    }
                }
            } else {
                if (Character.isDigit(c)) {
                    int j = i;
                    int num = 0;
                    while (j < n && Character.isDigit(sc[j])) {
                        num = num * 10 + sc[j] - '0';
                        j++;
                    }
                    numStack.push(num);
                    i = j - 1;
                } else {
                    if (i > 0 && (sc[i - 1] == '(' || sc[i - 1] == '+' || sc[i - 1] == '-')) {
                        numStack.push(0);
                    }
                    while (!opStack.isEmpty() && opStack.peek() != '(') {
                        char prev = opStack.peek();
                        if (map.get(prev) >= map.get(c)) {
                            cal(numStack, opStack);
                        } else {
                            break;
                        }
                    }

                    opStack.push(c);
                }
            }
        }
        while (!opStack.isEmpty()) {
            cal(numStack, opStack);
        }
        return numStack.peek();
    }

    private void cal(Deque<Integer> numStack, Deque<Character> opStack) {
        if (numStack.isEmpty() || numStack.size() < 2) {
            return;
        }
        if (opStack.isEmpty()) {
            return;
        }
        int a = numStack.poll();
        int b = numStack.poll();
        int ans = 0;
        char c = opStack.poll();
        if (c == '+') {
            ans = a + b;
        } else if (c == '-') {
            ans = b - a;
        } else if (c == '*') {
            ans = a * b;
        } else if (c == '/') {
            ans = b / a;
        } else if (c == '%') {
            ans = b % a;
        } else if (c == '^') {
            ans = (int) Math.pow(b, a);
        }

        numStack.push(ans);
    }
    
    private void initMap() {
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        map.put('%', 2);
        map.put('^', 3);
    }
}