题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。

示例

示例 1：

输入: "1 + 1"
输出: 2

示例2：

输入: " 2-1 + 2 "
输出: 3

示例3：

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

说明：

• 你可以假设所给定的表达式都是有效的。
• 请不要使用内置的库函数 eval。

解答方法

方法一：栈和不反转字符串

思路

• 把字符串中所有的数字和数字前面的符号看做一个整体，以正负数的形式表达，这样在计算时全看做加法。
• 遇到括号时先保存之前的计算结果，计算完括号里的之后在于之前的结果相加。
• 结果的保存用栈来实现

代码

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        res = 0
        nums = 0
        sign = 1
        for ch in s:
            if ch.isdigit():
                nums = nums*10 + int(ch)
            
            if ch is '+':
                res += sign * nums
                sign = 1
                nums = 0
            
            if ch is '-':
                res += sign * nums
                sign = -1
                nums = 0
            
            if ch is '(':
                stack.append(res)
                stack.append(sign)
                sign = 1
                res = 0

            if ch is ')':
                res += sign * nums
                res *= stack.pop()
                res += stack.pop()
                nums = 0

        return res + sign*nums

时间复杂度

O(N)，其中 N 指的是字符串的长度。

空间复杂度

O(N)，其中 N 指的是字符串的长度。