【栈】2023B-仿 LISP 运算
题目描述与示例
题目描述
LISP 语言唯一的语法就是括号要配对。 形如 (OP P1 P2 …)，括号内元素由单个空格分割。 其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数取决于操作符类型
注意：参数 P1, P2 也有可能是另外一个嵌套的 (OP P1 P2 …) 当前 OP 类型为 add / sub / mul / div（全小写），分别代表整数的加减乘除法。简单起见，所有 OP 参数个数均为 2
举例：
- 输入：
(mul 3 -7) 输出： -21
- 输入：
(add 1 2) 输出：3
- 输入：
(sub(mul 2 4) (div 9 3)) 输出：5
- 输入：
(div 1 0) 输出：error
题目涉及数字均为整数，可能为负；不考虑 32 位溢出翻转，计算过程中也不会发生 32 位溢出翻转 除零错误时，输出 "error"，除法遇除不尽，向下取整，即 3 / 2 = 1
输入
输入为长度不超过 512 的字符串，用例保证了无语法错误
输出
输出计算结果或者 "error"
示例一
输入
(div 12 (sub 45 45))
输出
error
示例二
输入
(add 1 (div -7 3))
输出
-2
解题思路
这道题也是经典的括号配对兼表达式求值的栈题，所给的字符串是一个前缀表达式。
原字符串的处理
其难点主要在于对原字符串的处理，如何把字符串 s = (sub(mul 2 4) (div 9 3))，储存为方便栈运算的列表形式 ops = ['(', 'sub', '(', 'mul', '2', '4', ')', '(', 'div', '9', '3', ')', ')']。
对于这个问题。这里提出两种可能的处理方式。
- 使用字符串的
replace() 方法，将 s 中所有的左括号 "(" 和右括号 ")" 前后都加上空格，即替换为 " ( " 和 " ) "，然后再对替换后的字符串 s 使用 split() 方法。代码为
s = input()
s = s.replace("(", " ( ")
s = s.replace(")", " ) ")
ops = s.split()
- 用
while 循环遍历原字符串 s，初始化索引 i = 0。如果 ch = s[i] 为：
- 数字或负号
"-"。说明此时正在遍历一个数字，将 ch 添加到列表最后一个元素的尾部 ops[-1] 即可，即一个数字进行延申操作。同时索引 i += 1
- 字母。说明遇到四种操作符中的一种。只需要记录操作符首字母即可，将首字母字符
ch 加入 ops 列表尾部，同时索引 i += 3
- 括号。将括号字符
ch 加入 ops 列表尾部，同时索引 i += 1
- 空格，说明接下来可能要遇到数字，将一个空字符串
"" 加入 ops 列表尾部，用于记录接下来可能出现的数字，同时索引 i += 1。
上述逻辑整理为代码即
s = input()
ops = list()
# 初始化遍历字符串s的索引i = 0
i = 0
n = len(s)
# 先将字符串s转化为一个方便进行遍历的数组
while i < n:
ch = s[i]
# ch是数字或者负号"-"的情况，添加到列表最后一个元素的尾部即可，即一个数字进行延申操作
if ch.isdigit() or ch == "-":
# 往栈顶的数字+1
ops[-1] += ch
i += 1
# ch是括号、操作符或空格的情况
else:
# 遇到字母，是一个操作符，记录操作符首字母即可，首字母字符加入ops列表尾部，索引i前进3格
if ch.isalpha():
ops.append(ch)
i += 3
# 遇到括号，括号字符字符加入ops列表尾部，索引i前进1格
if ch == "(" or ch == ")":
ops.append(ch)
i += 1
# 遇到空格，说明接下来可能要遇到数字，将一个空字符串加入ops列表尾部，用于记录数字，
# 索引i前进1格
else:
ops.append("")
i += 1
栈辅助前缀表达式求值
在获得了 ops 列表之后，剩下的部分就是常规的栈操作了。首先需要构建一个空栈 stack，然后遍历 ops 中的所有符号 ch。当 ch 为
上述逻辑整理为代码即
for ch in ops:
if ch == "(" or ch.isalpha():
stack.append(ch)
elif ch == ")":
num2 = stack.pop()
num1 = stack.pop()
op = stack.pop()[0]
stack.pop()
if op == "a":
res = num1 + num2
elif op == "s":
res = num1 - num2
elif op == "m":
res = num1 * num2
elif op == "d":
if num2 == 0:
isError = True
break
res = floor(num1 / num2)
stack.append(res)
else:
stack.append(int(ch))
代码
# 题目：2023B-仿LISP运算
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码看不懂的地方，请直接在群上提问
from math import floor
# 处理字符串的方式取第一种做法
s = input()
s = s.replace("(", " ( ")
s = s.replace(")", " ) ")
ops = s.split()
# 初始化空栈
stack = list()
# 初始化一个错误标记
isError = False
# 遍历ops中的所有符号
for ch in ops:
# 遇到左括号和字母操作符
# 入栈
if ch == "(" or ch.isalpha():
stack.append(ch)
# 遇到右括号，出栈
elif ch == ")":
num2 = stack.pop()
num1 = stack.pop()
# 弹出操作符，只获得其首字母即可
op = stack.pop()[0]
# 弹出左括号
stack.pop()
# 加法操作
if op == "a":
res = num1 + num2
# 减法操作
elif op == "s":
res = num1 - num2
# 乘法操作
elif op == "m":
res = num1 * num2
# 除法操作
elif op == "d":
# 出现除0的错误
if num2 == 0:
isError = True
break
res = floor(num1 / num2)
stack.append(res)
# 遇到数字，转为int后入栈
else:
stack.append(int(ch))
if isError:
print("Error")
else:
print(stack[0])
时空复杂度
时间复杂度：O(N)。仅需一次遍历数组，每一个字符最多出入栈各一次。
空间复杂度：O(N)。栈所占用的额外空间。
华为OD算法冲刺训练
-
华为OD算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
-
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
-
30+天陪伴式学习，20+直播课时，300+动画图解视频，200+LeetCode经典题，100+华为OD真题，还有简历修改与模拟面试将为你解锁
-
可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)
-
绿色聊天软件戳 sheepvipvip了解更多
