刷题笔记合集🔗

仿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

输入格式

输入为长度不超过 的字符串，用例保证了无语法错误。

输出格式

输出计算结果或者 "error"。

样例输入

(div 12 (sub 45 45))

(add 1 (div -7 3))

样例输出

error

-2

数据范围

• 输入字符串长度不超过
• 保证输入无语法错误

题解

这道题目考察的是表达式解析，需要实现一个简单的LISP解释器。LISP语言的特点是所有表达式都用括号包围，形式统一，便于递归处理。

解题的关键在于如何处理嵌套的表达式。在LISP中，最内层的括号会最先被计算，然后逐层向外。比如(sub (mul 2 4) (div 9 3))，需要先计算(mul 2 4)得到8，再计算(div 9 3)得到3，最后计算(sub 8 3)得到5。

实现上，可以使用栈来辅助解析。基本思路如下：

1. 从左到右扫描输入字符串
2. 遇到字符就放入栈中
3. 当遇到右括号')'时，向前查找对应的左括号'('
4. 取出左右括号之间的内容，进行解析和计算
5. 将计算结果转为字符串放回栈中
6. 重复上述过程，直到处理完整个字符串

具体实现中，要特别注意以下几点：

• 除零错误的处理：当除数为0时，立即返回"error"
• 除法的向下取整：对于负数除法，需要特别注意向下取整的实现
• 参数解析：需要正确分割操作符和参数

这种方法的时间复杂度是O(n)，其中n是输入字符串的长度。在最坏情况下，我们需要遍历字符串中的每个字符一次。空间复杂度也是O(n)，主要是栈所需的空间。

虽然题目保证输入没有语法错误，但实际编程时还是要注意边界条件和异常情况的处理，使代码更健壮。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
import math

def calculate_lisp(expr):
    stack = []  # 用于存储解析过程中的字符
    left_idx = []  # 记录左括号的位置
    
    for i in range(len(expr)):
        char = expr[i]
        
        if char == ')':
            # 找到对应的左括号
            left_pos = left_idx.pop()
            # 提取括号内的内容
            fragment = stack[left_pos + 1:]
            # 从栈中移除括号内容和左括号
            del stack[left_pos:]
            
            # 解析操作和参数
            parts = ''.join(fragment).split()
            op = parts[0]
            p1 = int(parts[1])
            p2 = int(parts[2])
            
            # 执行操作
            result = perform_operation(op, p1, p2)
            
            # 如果是错误，直接返回
            if result == "error":
                return "error"
            
            # 将结果添加回栈中
            stack.extend(str(result))
        elif char == '(':
            # 记录左括号位置
            left_idx.append(len(stack))
            stack.append(char)
        else:
            # 其他字符直接添加到栈中
            stack.append(char)
    
    # 最终栈中应该只剩下计算结果
    return