[刷题防痴呆] 0224 - 简单计算器 (Basic Calc

题目地址

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

题目描述

224. Basic Calculator

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

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

 

Example 1:

Input: s = "1 + 1"
Output: 2
Example 2:

Input: s = " 2-1 + 2 "
Output: 3
Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

思路

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

关键点

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

代码

• 语言支持：Java

class Solution {
    public int calculate(String s) {
        Deque<Integer> numStack = new ArrayDeque<>();
        numStack.push(0);
        s = s.replaceAll(" ", "");
        Deque<Character> opStack = new ArrayDeque<>();
        int n = s.length();
        char[] sc = s.toCharArray();
        for (int i = 0; i < n; i++) {
            char c = sc[i];
            if (c == '(') {
                opStack.push(c);
            } else if (c == ')') {
                while (!opStack.isEmpty()) {
                    char op = opStack.peek();
                    if (op != '(') {
                        cal(numStack, opStack);
                    } else {
                        opStack.pop();
                        break;
                    }
                }
            } else {
                if (Character.isDigit(c)) {
                    int num = 0;
                    int j = i;
                    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() != '(') {
                        cal(numStack, opStack);
                    }
                    opStack.push(c);
                }
            }
        }
        while (!opStack.isEmpty()) {
            cal(numStack, opStack);
        }
        return numStack.peek();
    }

    private void cal(Deque<Integer> nums, Deque<Character> ops) {
        if (nums.isEmpty() || nums.size() < 2) {
            return;
        }
        if (ops.isEmpty()) {
            return;
        }
        int a = nums.pop();
        int b = nums.pop();
        char op = ops.pop();
        if (op == '+') {
            nums.push(b + a);
        } else {
            nums.push(b - a);
        }
    }
}