实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 1：
输入：s = "1 + 1"
输出：2
示例 2：
输入：s = " 2-1 + 2 "
输出：3
示例 3：
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1. 1 <= s.length <= 3 * 105
2. s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
3. s 表示一个有效的表达式
题目给出, 难度为困难.
刚审完题, 第一感觉还是挺简单的嘛, 只有加减法, 那括号就没用了嘛. 提前说一下, 括号没用这句话是错误的.
一开始, 自己的思路是先把空格, 括号去掉, 然后创建两个栈, 一个存放数字, 一个存放符号, 然后线性循环字符串表达式, 进行响应的运算. 这里推荐一下邓俊华老师的数据结构与算法这门课程(https://www.bilibili.com/video/BV1jt4y117KR?p=127).
当我写完一版, 信心满满的去提交时, 遇到了一个不能把括号省去的字符串表达式: - (3 + (4 + 5)). 原来从最开始的分析问题我就走错了.
那么, 正片开始.
首先, 字符串表达式中的空格是无效字符, 可以去除. 创建两个栈, 一个存放数字, 另一个存放符号. 并且字符串表达式的最后要添加一个终止符, 这个终止符可以是除了表达式可能出现的任意字符, 这里选择了 $ 符号. 符号栈中同样也添加一个 $ 符号表示终止符.
s = s.replace(' ', '') + '$'
数字栈, 符号栈 = [0], ['$']
数字栈中添加一个 0, 一是不会影响 +, - 的运算结果, 二是为了防止表达式中第一个数字是负数的情况.(血淋淋的经验呀, 万恶的 leetcode 什么题都出)
在字符串表达式中, 相加减的两个数字不一定仅是个位数, 但是我们又只能一个字符一个字符的读取, 所以要存储一下前一个读取字符, 如果前一个读取字符是数字, 那么就将数字栈最后一位出栈, 乘以 10 再加上当前数字. 所以需要创建一个变量
上一字符 = ''
如何执行运算呢? 判断符号栈中是否还存在元素, 如果存在就执行循环. 为什么不能只循环一遍字符串表达式呢, 这个可以在最后说.
在循环中, 如果当前字符是数字, 那么就要判断一下, 如果前一个读取的字符是数字, 那么就要将数字栈中的最后一位出栈, 乘以 10 再加上当前数字. 否则直接加入数字栈中.然后将读取字符索引向前一位.
对了, 说到了字符串表达式的索引, 需要提前创建一个存储当前索引的变量.
if s[s_index].isnumeric(): # 是否只包含数字
if 上一字符.isnumeric(): # 上一字符是数字, 要合并
数字栈.append(数字栈.pop() * 10 + int(value))
else:
数字栈.append(int(value))
s_index += 1
在循环中, 如果当前字符是符号, 问题就复杂很多了. 加法减法何时计算, 括号怎么办. 设置优先级就是正解.
| --- | + | - | ( | ) | $ |
|---|---|---|---|---|---|
| + | > | > | < | > | > |
| - | > | > | < | > | > |
| ( | < | < | < | = | |
| ) | |||||
| $ | < | < | < | = |
如果当前字符是符号, 那么判断符号栈中最后一位与当前字符的优先级关系, 如果当前字符优先级高, 也就是 <. 符号栈中最后一位不能计算, 当前符号加入符号栈.
如果当前字符优先级与符号栈中最后一位符号相同, 那么在优先级表中, 只有 $ 与 $ 自身和 ( 与 ) 之间的优先级是相等的. $ 与自身相遇说明结束了, ( 与 ) 相遇说明这一对括号间仅有一个数字, 没有任何符号了, 这时括号就失去作用了. 那么这时的操作就是将符号栈的最后一位出栈.
以上两条分支执行后都需要将字符索引向前一位.
如果当前字符优先级低, 也就是 >, 说明栈中的符号可以计算了. 首先将符号栈中最后一位出栈, 数字栈中最后两位出栈, 注意, 数字栈中, 第一个出栈的数字在计算是应该在符号前. 然后进行计算后将结果加入到数字栈中.这里不需要向前移动字符索引, 因为可能有符号栈中多个字符优先级都高于当前字符.
循环结束后, 在数字栈中可能存在两个元素, 其中第一个是最开始添加的 0, 在不是特殊情况时, 这个元素 0 将不会被使用到. 无论如何, 数字栈中的最后一位就是表达式结果.
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(' ', '') + '$'
数字栈, 符号栈, 上一字符, s_index = [0], ['$'], '', 0
符号优先级表 = {
"+": {"+": '>', '-': '>', '(': '<', ')': '>', '$': '>'},
"-": {"+": '>', '-': '>', '(': '<', ')': '>', '$': '>'},
"(": {"+": '<', '-': '<', '(': '<', ')': '=', '$': ' '},
")": {"+": ' ', '-': ' ', '(': ' ', ')': ' ', '$': ' '},
"$": {"+": '<', '-': '<', '(': '<', ')': ' ', '$': '='}
}
while len(符号栈) >= 1:
value = s[s_index]
if s[s_index].isnumeric(): # 是否只包含数字
if 上一字符.isnumeric(): # 上一字符是数字, 要合并
数字栈.append(数字栈.pop() * 10 + int(value))
else:
数字栈.append(int(value))
s_index += 1
else:
if 符号优先级表[符号栈[-1]][value] == '<': # 栈中的比当前低, 当前符号进栈
符号栈.append(value)
s_index += 1
elif 符号优先级表[符号栈[-1]][value] == '=': # 括号闭合, 或结束
符号栈.pop()
s_index += 1
elif 符号优先级表[符号栈[-1]][value] == '>': # 栈中优先级高, 可计算
符号, 数字A, 数字B = 符号栈.pop(), 数字栈.pop(), 数字栈.pop()
数字栈.append((数字B - 数字A) if 符号 == '-' else (数字B + 数字A))
上一字符 = value
return 数字栈.pop()
公众号 : 「python杂货铺」，专注于 python 语言及其相关知识。发掘更多原创文章，期待您的关注。
