赞
踩
本文首发于公众号:code路漫漫,欢迎关注
- 逆波兰表达式求值
- 基本计算器
- 基本计算器 II
- 基本计算器 III
特别说明,由于精度的问题,这里的题目凡是涉及到除法都只保留整数部分
对于逆波兰表达式,我们可以用一个栈就能求解出结果,这也是150. 逆波兰表达式求值
的答案
class Solution: def evalRPN(self, tokens: List[str]) -> int: num = [] for t in tokens: # 可能含有负数 if t.isdigit() or t[1:].isdigit(): num.append(int(t)) else: if t == '+': a,b = num.pop(),num.pop() num.append(a+b) elif t == '-': a,b = num.pop(),num.pop() num.append(b-a) elif t == '*': a,b = num.pop(),num.pop() num.append(a*b) elif t == '/': a,b = num.pop(),num.pop() num.append(int(b/a)) return num[-1]
那么如何将中缀表达式转换成逆波兰表达式呢?
这个转换有很多实现,最关键的一点是我们要记住符号的优先级和出入栈的规则,为了通过leetcode中-xxx
和xx(-x+x)
这种样例,我们还要对字符换进行预处理
假定一个字符串表达式合法,并且只含有以下字符:+
, -
, *
, /
, (
, )
, ,我们需要两个栈来存储变量,一个
pos
存储转换后的结果,一个opt
存储转换过程中的操作符,我们按照如下规则转换:
pos
中opt
opt
我们不断弹出栈顶元素添加到pos
中直到遇到(
,然后弹出(
+
, -
, *
, /
,它们的优先级依次是1
,1
,2
,2
,即加减同级,乘除同级并且高于+,-pos
中,直到栈空或者遇到左括号,然后将自己入栈我们按照上面5个规则可以写出代码,下面的代码可以帮我们完成转换
def transfer(s): pri = {'+': 1, '-': 1, '*': 2, '/': 2} pos = [] opt = [] # --- 处理特殊样例 --- # 如果不需要可以注释掉这一块代码 def isopt(ch): if ch == '+' or ch == '-' or ch == '*' or ch == '/': return True return False ts = [] for i in range(len(s)): ch = s[i] ts.append(ch) # 我们检查括号后是否是opt if ch == '(': if isopt(s[i + 1]): ts.append('0') # 补一个0,保证以数字开头 s = ''.join(ts) if isopt(s[0]): s = '0' + s # --- 处理特殊样例 --- # 转换过程 i = 0 while i < len(s): ch = s[i] if ch == ' ': pass elif '0' <= ch <= '9': # 如果是数字,获取这一块数字 t = 0 while i < len(s) and '0' <= s[i] <= '9': t = t * 10 + int(s[i]) i += 1 i -= 1 # 由于判断外统一+1,我们这里先-1 pos.append(t) elif ch == '(': # 如果左括号,我们直接入栈 opt.append(ch) elif ch == ')': # 由于是合法的表达式,我们不需要检查栈空 while opt[-1] != '(': # 出栈直到遇到左括号 pos.append(opt.pop()) # 弹出左括号 opt.pop() else: # 遇到操作符 while opt and opt[-1] != '(' and pri[opt[-1]] >= pri[ch]: pos.append(opt.pop()) opt.append(ch) i += 1 # 弹出剩余的操作符 while opt: pos.append(opt.pop()) return pos
转换后我们传递结果给求解逆波兰表达式的算法即可
def evalRPN(pos): num = [] for t in pos: if type(t) == int: num.append(t) else: if t == '+': a, b = num.pop(), num.pop() num.append(a + b) elif t == '-': a, b = num.pop(), num.pop() num.append(b - a) elif t == '*': a, b = num.pop(), num.pop() num.append(a * b) elif t == '/': a, b = num.pop(), num.pop() num.append(int(b / a)) return num[-1]
224. 基本计算器
和227. 基本计算器 II
的答案
class Solution: def transfer(self, s): pri = {'+': 1, '-': 1, '*': 2, '/': 2} pos = [] opt = [] # --- 处理特殊样例 def isopt(ch): if ch == '+' or ch == '-' or ch == '*' or ch == '/': return True return False ts = [] for i in range(len(s)): ch = s[i] ts.append(ch) # 我们检查括号后是否是opt if ch == '(': if isopt(s[i + 1]): ts.append('0') # 补一个0,保证以数字开头 s = ''.join(ts) if isopt(s[0]): s = '0' + s # --- 处理特殊样例 # 转换过程 i = 0 while i < len(s): ch = s[i] if ch == ' ': pass elif '0' <= ch <= '9': # 如果是数字,获取这一块数字 t = 0 while i < len(s) and '0' <= s[i] <= '9': t = t * 10 + int(s[i]) i += 1 i -= 1 # 由于判断外统一+1,我们这里先-1 pos.append(t) elif ch == '(': # 如果左括号,我们直接入栈 opt.append(ch) elif ch == ')': # 由于是合法的表达式,我们不需要检查栈空 while opt[-1] != '(': # 出栈直到遇到左括号 pos.append(opt.pop()) # 弹出左括号 opt.pop() else: # 遇到操作符 while opt and opt[-1] != '(' and pri[opt[-1]] >= pri[ch]: pos.append(opt.pop()) opt.append(ch) i += 1 # 弹出剩余的操作符 while opt: pos.append(opt.pop()) return pos def evalRPN(self, pos): num = [] for t in pos: if type(t) == int: num.append(t) else: if t == '+': a, b = num.pop(), num.pop() num.append(a + b) elif t == '-': a, b = num.pop(), num.pop() num.append(b - a) elif t == '*': a, b = num.pop(), num.pop() num.append(a * b) elif t == '/': a, b = num.pop(), num.pop() num.append(int(b / a)) return num[-1] def calculate(self, s: str) -> int: pos = self.transfer(s) ans = self.evalRPN(pos) return ans
转换的开销其实还挺大的,如果很长很长的表达式,那么不建议用这个解法
如果追求高效,可以利用题目的特点去入手,下面以224. 基本计算器
和227. 基本计算器 II
为例,记录递归如何解决这类问题
先考虑224. 基本计算器
,整个式子只有+ - ( )
如果我们把括号展开,那么可以遍历一次得到答案,即数字和符号的组合相加
例如 1+2+(3-(4+5)) = 1+2+3-4-5
,是+1 +2 +3 -4 -5
这些数字合起来
关键是我们怎么把括号展开同时给每个数字赋予正确的符号
数字的符号被两个因素影响
例如-(1+2)
中2的符号,第一点,2的符号是+
,第二点,2的符号受到了括号前-
的影响,综合下来2的符号是-
数字当前的符号很好判断,要么是正要么是负,但是数字之前的符号需要记录下来,每个括号成对出现,所以我们可以用栈来表示,遇到左括号时,当前符号入栈,遇到右括号时,栈顶符号弹出
经过以上分析,我们需要两个变量
sign = 1
ops = [1]
sign初始化为1,ops初始化为[1]
,这是因为我们为了方便处理-
开头的表达式,相当于在表达式前加上0
,变为以+
开头
ret = 0 n = len(s) i = 0 while i < n: if s[i] == ' ': i += 1 elif s[i] == '+': # + pass elif s[i] == '-': # - pass elif s[i] == '(': # 左括号 pass elif s[i] == ')': # 右括号 pass else: # 碰到数字 pass
然后我们逐个分析
如果是+:
由于+不会改变当前符号的性质,所以我们保持sign = ops[-1]
即可
如果是-:
由于-会反转符号,所以我们用sign = -ops[-1]
来记录当前符号
如果是(:
我们碰到了新的括号,当前的sign
对括号内的元素来说是之前的元素,我们用ops.append(sign)
来记录括号之外的符号
如果是):
括号对结束了,我们把栈顶元素弹出
如果碰到数字:
按照之前的分析,我们获取数字,然后统计结果 ret += sign*num
即可
上面的代码完善后变为
class Solution: def calculate(self, s: str) -> int: ops = [1] sign = 1 ret = 0 n = len(s) i = 0 while i < n: if s[i] == ' ': i += 1 elif s[i] == '+': # +号继承之前的符号 sign = ops[-1] i += 1 elif s[i] == '-': # -号反转 sign = -ops[-1] i += 1 elif s[i] == '(': ops.append(sign) i += 1 elif s[i] == ')': ops.pop() i += 1 else: num = 0 while i<n and s[i].isdigit(): num = num*10 + ord(s[i]) - ord('0') i+=1 ret += num*sign return ret
然后我们看 227. 基本计算器 II
还是一样的思路,这里只多了乘除而少了括号,整个式子没有括号并不会改变运算的优先级,所以我们按照同样的思路来做
有意思的是整个表达式没有括号,不会改变运算的优先级,那么整个数字可以拆分为两部分:
如果是不涉及到乘除的数字,那么我们直接入栈,因为本质上是在做加法
如果涉及到乘除,那么涉及到的数字最终都会得到一个结果,我们可以不断对栈顶操作得到这个结果
具体来说,遍历字符串 s,并用变量 preSign 记录每个数字之前的运算符,对于第一个数字,其之前的运算符视为加号。每次遍历到数字末尾时,根据 preSign 来决定计算方式:
加号:将数字压入栈;
减号:将数字的相反数压入栈;
乘除号:计算数字与栈顶元素,并将栈顶元素替换为计算结果。
代码实现中,若读到一个运算符,或者遍历到字符串末尾,即认为是遍历到了数字末尾。处理完该数字后,更新 preSign 为当前遍历的字符。
class Solution: def calculate(self, s: str) -> int: n = len(s) stack = [] preSign = '+' num = 0 for i in range(n): if s[i] != ' ' and s[i].isdigit(): num = num * 10 + ord(s[i]) - ord('0') if i == n - 1 or s[i] in '+-*/': if preSign == '+': stack.append(num) elif preSign == '-': stack.append(-num) elif preSign == '*': stack.append(stack.pop() * num) else: stack.append(int(stack.pop() / num)) preSign = s[i] num = 0 return sum(stack)
先设计处理加减、乘除法的方法,然后遇到括号的时候再递归
224
的解法一样,我们用一个栈来存放结果,然后把式子变成累加的形式def cal1(s): num = 0 stack = [] sign = '+' # 方便做最后判断 s += '+' for i in range(len(s)): ch = s[i] if ch == ' ': continue elif ch.isdigit(): num = num * 10 + ord(ch) - ord('0') else: if sign == '+': stack.append(num) elif sign == '-': stack.append(-num) sign = ch num = 0 return sum(stack)
227
一样def cal2(s): num = 0 stack = [] sign = '+' # 方便做最后判断 s += '+' for i in range(len(s)): ch = s[i] if ch == ' ': continue elif ch.isdigit(): num = num * 10 + ord(ch) - ord('0') else: if sign == '+': stack.append(num) elif sign == '-': stack.append(-num) elif sign == '*': stack[-1] *= num elif sign == '/': stack[-1] = int(stack[-1] / num) sign = ch num = 0 return sum(stack)
cal2
封装为一个函数,给定一个不带括号的式子,它能正确计算并且返回结果,接下来我们只需要处理括号就行了def calculate(s) -> int: def helper(s) -> int: num = 0 stack = [] sign = '+' # 方便做最后判断 s += '+' while len(s) > 0: ch = s.pop(0) # 碰到左括号,递归计算括号内的式子 if ch == '(': num = helper(s) if ch == ' ': continue elif ch.isdigit(): num = num * 10 + ord(ch) - ord('0') else: if sign == '+': stack.append(num) elif sign == '-': stack.append(-num) elif sign == '*': stack[-1] *= num elif sign == '/': stack[-1] = int(stack[-1] / num) sign = ch num = 0 # 碰到右括号,结束递归,返回计算的结果 if ch == ')': break return sum(stack) return helper(list(s))
为了方便处理,我们把s变成list,然后不断弹出左边的字符来判断
不过由于递归开销过大,上面的代码通过不了leetcode的题目
上面的递归方法能够处理一般的计算器类问题,如果有特殊的符号,例如^
,sqrt
,需要我们做出一些改动
另外《算法》中有两道题目,感兴趣可以做一下
这里提示一下,用格式化构造字符串的方式可以很方便的补全
参考答案:
https://github.com/hhmy27/Alg4_Code/blob/master/src/ch01/part3/ex_1_3_9.java
https://github.com/hhmy27/Alg4_Code/blob/master/src/ch01/part3/InfixToPostfix.java
https://github.com/hhmy27/Alg4_Code/blob/master/src/ch01/part3/EvaluatePostfix.java
https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484903&idx=1&sn=184beaad36a71c9a8dd93c41a8ba74ac&chksm=9bd7fbefaca072f9beccff92a715d92ee90f46c297277eec10c322bc5ccd053460da6afb76c2&scene=21#wechat_redirect
https://leetcode-cn.com/problems/basic-calculator-ii/solution/zui-hou-du-bian-cheng-zuo-jia-fa-leetcod-oxx9/
https://leetcode-cn.com/problems/basic-calculator-ii/solution/ji-ben-ji-suan-qi-ii-by-leetcode-solutio-cm28/
https://leetcode-cn.com/problems/basic-calculator/solution/shuang-zhan-jie-jue-tong-yong-biao-da-sh-olym/
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。