P2603. 仿LISP运算

解题思路

这道题也是经典的括号配对兼表达式求值的栈题，所给的字符串是一个前缀表达式。和 逆波兰表达式求值 有一定的相似之处。

原字符串的处理

本题的难点主要在于对原字符串的处理，如何把字符串 s = "(sub (mul 2 4) (div 9 3))"，储存为方便栈运算的列表形式 ops = ['(', 'sub', '(', 'mul', '2', '4', ')', '(', 'div', '9', '3', ')', ')']。

对于这个问题，这里提出两种可能的处理方式。

方法一：使用 replace() 和 split()

使用字符串的 replace() 方法，将 s 中所有的左括号 "(" 和右括号 ")" 前后都加上空格，即替换为 " ( " 和 " ) "，然后再对替换后的字符串 s 使用 split() 方法。代码为：

方法二：使用 while 循环遍历

用 while 循环遍历原字符串 s，初始化索引 i = 0。如果 ch = s[i] 为：

• 数字或负号 `"-"`：说明此时正在遍历一个数字，将 ch 添加到列表最后一个元素的尾部 ops[-1] 即可，即一个数字进行延申操作。同时索引 i += 1。
• 字母：说明遇到四种操作符中的一种。只需要记录操作符首字母即可，将首字母字符 ch 加入 ops 列表尾部，同时索引 i += 3。
• 括号：将括号字符 ch 加入 ops 列表尾部，同时索引 i += 1。
• 空格：说明接下来可能要遇到数字，将一个空字符串 "" 加入 ops 列表尾部，用于记录接下来可能出现的数字，同时索引 i += 1。

上述逻辑整理为代码即：

由于第二种方法更加具备通用性，在后面给出的题解代码中将使用第二种方法来处理原始字符串。

栈辅助前缀表达式求值

在获得了 ops 列表之后，剩下的部分就是常规的栈操作了。

首先需要构建一个空栈 stack，然后遍历 ops 中的所有符号 ch。当 ch 为：

• 左括号或字母：ch 入栈。
• 数字：转为整数后，即 int(ch) 入栈。
• 右括号：进行出栈和计算。由于是前缀表达式，因此分别弹出两次栈顶元素，得到 num1 和 num2，然后再次弹出栈顶元素得到用字母表示的操作符 op，然后再一次弹出栈顶元素，把该右括号对应的左括号 "(" 出栈。
• 根据 op 的取值，对 num1 和 num2 进行加减乘除的操作，并且需要把计算的结果 res 再次存入栈中。
• 这里要注意除法操作可能会出现除 0 的情况，如果出现了则需要进行异常处理。

上述逻辑整理为代码即：

复杂度分析 设输入表达式的长度为 n。算法分两个线性阶段。第一阶段把原字符串整理成记号列表 ops：while 循环中每个字符只被访问一次，遇到操作符字母时记录首字母并用 i += 3 一次跳过剩余字母，数字与负号逐字符拼接到当前记号尾部，括号与空格各产生一个记号；整理加上随后过滤空串的列表推导，总计 O(n)。第二阶段对 ops 做栈求值：每个记号至多入栈一次，遇到右括号时弹出两个操作数、一个操作符和一个左括号，做一次加减乘除并把结果压回栈中。由于每个元素只会被压入、弹出各一次，这一阶段的总代价也是 O(n)。因此整体时间复杂度为 O(n)，开销就是两次线性扫描，没有更高阶的瓶颈；出现除零时置 isError 并提前退出，只会更快。空间复杂度 O(n)：ops 列表与求值栈的长度都不超过记号总数，而记号总数与输入长度同阶。