Leetcode 224. Basic Calculator

题目

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces.

Example 1:

Input: "1 + 1"
Output: 2

Example 2:

Input: " 2-1 + 2 "
Output: 3

Example 3:

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

Note:

• You may assume that given expression is always valid.

• Do not use the eval built-in library function.

思路

首先，我们可以先从最基础的两个数相加相减开始思考。

比如我们input string为123 - 234, 我们首先需要做的是从string中识别出123和234两个operand。我们知道数字为连续的digit characters，因此，我们可以循环地从左到右将123拆成100 + 20 + 3，或234拆成200 + 30 + 4即可得operand。另外，我们需要意识到加法和减法本质上是一样的，123 - 234 = 123 + (-234)。因此如果我们可以利用一个sign为1或-1来表示加减，即operand1 + (sign) * operand2.

然后，我们再从两个数的加减变为多个数的加减（没有括号的情况）。

比如我们的input string为12 + 23 - 34。按照我们之前的思路，可得0 + sign1 * operand1 + sign2 * operand2 + sign3 * operand。其中operand1,2,3分别为12, 23, 34, sign1，2，3分别为+1, +1, -1. 我们注意到当数变多之后，我们需要记录的sign和operand也越来越多，非常不方便。因此，我们可以在从左到右读input string的时候，同时进行计算，并将结果储存于result中，即12 + 23直接变为35这个result，然后整个式子变成了35 + (- 34)，即result += operand * sign。

最后，我们再考虑有括号的情况。当我们遇见左括号时，说明我们需要保存当前的result和sign，再重新开启一轮新的括号内的运算；当我们遇见右括号时，我们应该首先计算出括号内结果bracketResult，然后将之前保存的result更新为result += sign * bracketResult。

比如1 + 1 - (2 - 5)，我们在走完1 + 1之后得到result = 2，和括号前的sign = -1，我们可以先将他们保存至stack，然后重置result, sign，以重新开始括号内运算。当见到)时，我们首先将括号内的运算完成，即bracketResult = 2 - 5 = -3，然后再将bracketResult和之前保存至stack的数和相加或相减。

下图可以让大家更直观的理解这个过程：

Illustration

解答

大家也可结合解答代码中每种情况的注释来理解我们的算法。

class Solution {
    public int calculate(String s) {

        Stack<Integer> stack = new Stack<Integer>();
        int result = 0;
        int operand = 0;
        int sign = 1;

        for (char ch : s.toCharArray()) {

            // Covert digits to number (e.g. operand = 12, string = "123" -> 12 * 10 + 3)
            if (Character.isDigit(ch)) {
                operand = operand * 10 + (int) Character.getNumericValue(ch);
                continue;
            }

            switch (ch) {
                case '+': { // evaluate result, sign, operand
                    result += sign * operand;
                    sign = 1;
                    operand = 0;
                    break;
                }
                case '-': { // evaulate result, sign, operand
                    result += sign * operand;
                    sign = -1;
                    operand = 0;
                    break;
                }
                case '(': { // stack: [result, sign], reset temp result/sign to calculate
                    stack.push(result);
                    stack.push(sign);
                    result = 0;
                    sign = 1;
                    break;
                }
                case ')': { // evaluate bracketResult, sign, operand; evaluate stack [result, sign] + bracketResult.
                    result += sign * operand;
                    result *= stack.pop();
                    result += stack.pop();
                    operand = 0;
                }
            }
        }
        return result + (sign * operand);
    }
}

Complexity Analysis

• Time Complexity: O(n). 我们需要遍历String中的所有字母。

• Space Complexity: O(n). Stack中最多可能装String中的所有数字。

拓展

如果不使用sign来负责加减，我们还能有其他什么办法解决这个问题呢？

总结

这类题型要求我们非常细致对问题进行分情况讨论，且不错过各种细节。一种比较好的思路即为从最简单版的问题想起（比如两个数相加），再逐渐扩充、修改，以满足题目要求。