括号题或者字符串运算题

括号题

算法思路：

1. 优先考虑用Stack。Stack可以将字符压入比较或者字符的下标压入比较，后者信息量更大
   三种情况不合法： ‘[‘ (stack有余，for后发生), ‘]’ (要匹配的时候stack为空，for中发生), ‘{]’ (不匹配，for中发生)
2. DP
3. 1) 左括号的数量在每一位都大于等于右括号数量
   2) 右括号的总和要等于右括号总和
   以上两个条件都满足的话，左右括号匹配，但此法只能用于单种括号

应用：

1. 括号题
2. 字符串运算题如, 3+4, (3+4)*5

括号运算题

res是作为同一层的临时计算结果，若遇到左括号，res保留在stack中且reset，若遇到右括号，stack的结果还原到res
num也是临时变量负责储存整数

注意事项：

1. char.isdigit()的计算
2. 左括号：入栈和reset res和num。
3. 右括号:出栈和还原res = tmp + f(res)。

括号运算题模板：

def parenthesis(self, s: str) -> int:
    (Optional) s边界处理如s += '+' 
	res, num, stack = '', 0, []
	for char in s:
        if char == ' ':
            continue
		if char.isdigit(): 
			num = num * 10 + int(char)
		if char.isalpha():
			res += char
		if char == '+' # 或其他操作符
			res = 同层计算
			num = 0  # reset 不能reset res，因为res是这一层的临时结果
		if char == '[':
			多个入栈(res) 
			res = '' # reset
			num = 0  # reset 
		if char == ']':
			(Optional) res = 同层计算, 这两步同+运算符
			tmp = 多个出栈
			res = tmp + f(res) # 还原上层结果
			(Optional) num = 0
	return res

算法分析：

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