实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号(，右括号)，加号+，减号-，非负整数和空格 。
示例 1:
输入: "1 + 1" 输出: 2示例 2:
输入: " 2-1 + 2 " 输出: 3示例 3:
输入: "(1+(4+5+2)-3)+(6+8)" 输出: 23说明：
你可以假设所给定的表达式都是有效的。请不要使用内置的库函数eval。解题思路
经典问题，首先采用递归的方式求解。这里使用了trick，使用1表示加法，使用-1表示减法，使用l表示左值，使用r表示右值。
当遍历到的字符是'('的时候我们需要递归下去，同时计算左值l += op * dfs()。当遍历到的字符是')'的时候，返回结果l + op * r。当匹配到+-的时候需要调整操作符op，同时需要更新此时的左值l += op * r。当匹配到空格的时候跳过。当匹配到数字的时候，更新右值r = r * 10 + int(s[u])，其中u表示当前的位置。当所有元素都遍历完后，返回l + op * r。 class Solution: def calculate(self, s: str) -> int: u, s_len = 0, len(s) def dfs(): nonlocal u l, r, op = 0, 0, 1 while u < s_len: if s[u] == ' ': u += 1 continue elif s[u] in '+-': l += op * r r, op = 0, 1 if s[u] == '+' else -1 u += 1 elif s[u] == '(': u += 1 l += op * dfs() elif s[u] == ')': u += 1 return l + op * r else: r = r * 10 + int(s[u]) u += 1 return l + op * r return dfs()同样也可以使用递归解决，递归我们也使用了trick，只使用一个栈就解决了。算法思路和上面的方法类似，只是当访问的元素是'('的时候，将l和op添加到栈中，同时更新op=1、l=0。当访问的元素是')'的时候，将栈中的l和op弹出，并且更新l。
class Solution: def calculate(self, s): st, op, r, l = [], 1, 0, 0 for c in s: if c.isdigit(): r = r * 10 + int(c) elif c in "+-": l += op * r r, op = 0, 1 if c == '+' else -1 elif c == "(": st.append(l) st.append(op) op, l = 1, 0 elif c == ")": l += op * r r = 0 l = st.pop() * l + st.pop() return l + op * r我将该问题的其他语言版本添加到了我的GitHub Leetcode
如有问题，希望大家指出！！！
