LeetCode 772 Basic Calculator III

LeetCode

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1+1”
Output: 2

Example 2:

Input: s = “6-4/2”
Output: 4

Example 3:

Input: s = “2(5+52)/3+(6/2+8)”
Output: 21

Constraints:

1 <= s <= 10<sup>4</sup> s consists of digits, '+', '-', '*', '/', '(', and ')'.
s is a *valid expression.

题目大意：

实现字符串加减乘除且有括号。

解题思路：

类似于Leetcode 227求加减乘除，这里多了括号，括号内含加减乘除，所以每对括号是一轮DFS。遇到左括号，就进入递归，遇到右括号就返回递归值

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

解题步骤：

N/A

注意事项：

1. 不同于L227, 类似于填位法将i作为DFS参数传入，返回括号内的值以及i。i放入while循环， i += 1要加入到空格情况和循环最后
2. 最后位加入加号要移除DFS中，放入主函数
3. 注意处理括号情况的顺序，左括号在空格后，右括号在最后

Python代码：

def calculate(self, s: str) -> int:
	s += '+'
	return self.dfs(s, 0)

def dfs(self, s, i):
	res, num, stack, op = 0, 0, [], '+'
	while i < len(s):
		char = s[i]
		if char == ' ':
			i += 1
			continue
		if char == '(':
			num, i = self.dfs(s, i + 1)
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char

		if char == ')':
			return sum(stack), i
		i += 1
	return sum(stack)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)