共计 2463 个字符，预计需要花费 7 分钟才能阅读完成。
实现一个根本的计算器来计算一个简略的字符串表达式 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/vide…
当我写完一版, 信念满满的去提交时, 遇到了一个不能把括号省去的字符串表达式: - (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 语言及其相干常识。挖掘更多原创文章，期待您的关注。
