224. 基本计算器

实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
输入：s = "1 + 1"
输出：2
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式

表达式求值这一类的题比较自然地会想到利用栈来求解。这里的难点是如何解决括号。基本思想如下：
维护一个栈，遍历字符串，

1. 如果当前字符是空格，忽略
2. 如果当前字符是'+'，'-'或者'('，入栈
3. 如果当前字符是数字，判断栈顶元素。如果栈顶元素是'('，则入栈。如果栈顶元素是'+'，'-'，则将运算符出栈。如果此时栈顶元素是数字，则将其出栈，和当前数字做相应运算后将结果入栈。如果此时栈顶元素不是数字（比如说负数'-5'）。我们方便起见可以将左运算数设置为0，和当前数字运算后结果入栈。
4. 如果当前字符是')'，则栈顶元素必是数字，我们只需要出栈，然后忽略该数字前的'('。此时需要判断，如果栈顶是运算符，则需要做类似于3的操作。否则只需要将数字入栈。
5. 循环结束后，栈里的剩余数字就是结果

WeChat Image_20210310222844.jpg

复杂度分析较为简单，时间空间都具有O(n)的复杂度。

class Solution:
    '''
    224. Basic Calculator
    Stack
    '''
    def calculate(self, s: str) -> int:
        evaluate_stack = list()
        idx = 0
        while idx < len(s):
            if s[idx] == ' ':
                # ignore all the space
                idx += 1
                continue
            if s[idx] == '+' or s[idx] == '-' or s[idx] == '(':
                # for parenthesis and operators,
                # just push into stack
                evaluate_stack.append(s[idx])
                idx += 1
                continue
            if s[idx] >= '0' and s[idx] <= '9':
                # get the number in case it has
                # more than 1 digits
                num_str = ''
                while idx < len(s) and s[idx] >= '0' and s[idx] <= '9':
                    num_str += s[idx]
                    idx += 1
                num = int(num_str)
                if len(evaluate_stack) == 0 or evaluate_stack[-1] == '(':
                    # if stack empty or the top
                    # element is parenthesis, just
                    # push it into the stack
                    evaluate_stack.append(num)
                else:
                    # otherwise, the top element in
                    # the stack must be an operator,
                    # then we get the operator and
                    # the operand, evaluate it and
                    # push the result back to the 
                    # stack
                    operator = evaluate_stack.pop()
                    # this is to deal with negative number
                    left_operand = evaluate_stack.pop() if len(evaluate_stack) > 0 else 0
                    evaluate_stack.append((left_operand + num) if operator == '+' else (left_operand - num))
                continue
            if s[idx] == ')':
                # when we see right parenthesis, the top
                # element in the stack must be a number.
                # we just remove the left parenthesis
                # before that, before pushing the number
                # back in, we need to check if the top
                # element is now operator, to handle the
                # case like '··+(1+2)'
                num = evaluate_stack.pop()
                evaluate_stack.pop()
                if len(evaluate_stack) > 0 and evaluate_stack[-1] in ('+', '-'):
                    operator = evaluate_stack.pop()
                    left_operand = evaluate_stack.pop() if len(evaluate_stack) > 0 else 0
                    num = (left_operand + num) if operator == '+' else (left_operand - num)
                evaluate_stack.append(num)
                idx += 1

        # with the assumption that the input string is
        # an valid expression, the only number left in
        # the stack should just be the result
        return evaluate_stack[-1]