题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例
示例 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 指的是字符串的长度。
