题目描述

给定一个字符串表示的嵌套LISP风格的数学表达式，要求编写程序解析并计算该表达式的结果。表达式中的操作包括加法(add)、减法(sub)、乘法(mul)和整数除法(div)四种。表达式中每个操作符的参数只有两个。对于 div 操作，如果第二个参数为 0，应输出 error 表示除零错误。 注意：可能会爆int。

解题思路

1. 解析表达式：从输入的字符串逐个字符解析。遇到空格时跳过，遇到 ( 表示一个新的表达式开始。( 后紧跟的是操作符（add、sub、mul、div），接着是两个操作数。

2. 递归计算：表达式由多个嵌套的小表达式组成，采用递归来解析和计算结果：

   • 遇到 ( 时，进入递归，依次解析操作符和两个操作数。
   • 遇到数字或负号开头的数字，直接解析为整数。
   • 遇到 ) 表示一个表达式结束，返回结果到上一级递归。

3. 错误处理：

   • 在 div 操作中，如果第二个操作数为 0，返回特殊错误值（如 Long.MIN_VALUE），并在最终结果中输出 "error"。
   • 解析失败时（如不符合格式）也返回错误标记。

4. 返回结果：通过递归层层返回解析和计算的结果，最终输出在主函数中完成。

复杂度分析

• 时间复杂度：O(n)，其中 n 是表达式字符串的长度。每个字符被解析一次，递归深度受嵌套层数限制。
• 空间复杂度：O(d)，其中 d 是表达式嵌套深度，主要体现在递归调用栈的深度上。

代码示例

Cpp

#include <bits/stdc++.h>

using namespace std;

// 计算两个 long long 整数的结果，处理除法的特例
long long calc(const string &op, long long p1, long long p2) {
    if (op == "add") {
        return p1 + p2;
    } else if (op == "sub") {
        return p1 - p2;
    } else if (op == "mul") {
        return p1 * p2;
    } else { // div
        return (p2 == 0) ? LLONG_MIN : (long long) floor(p1 * 1.0 / p2); // LLONG_MIN used to indicate error condition
    }
}

// 递归解析并计算 LISP 表达式
pair<long long, bool> evaluate(const string &expr, size_t &index) {
    // 跳过空格
    while (index < expr.size() && expr[index] == ' ') {
        index++;
    }

    // 如果到达字符串结尾
    if (index >= expr.size()) return {0, false};

    // 处理 '('
    if (expr[index] == '(') {
        index++; // 跳过 '('

        // 读取操作符
        string op;
        while (index < expr.size() && expr[index] != ' ' && expr[index] != ')') {
            op += expr[index++];
        }

        // 读取参数
        long long p1, p2;
        bool success = true;

        // 递归读取第一个参数
        auto [result1, res1Success] = evaluate(expr, index);
        success = success && res1Success;
        p1 = result1;

        // 递归读取第二个参数
        auto [result2, res2Success] = evaluate(expr, index);
        success = success && res2Success;
        p2 = result2;

        // 处理 ')' 
        while (index < expr.size() && expr[index] != ')') {
            index++; // 跳过空格
        }
        index++; // 跳过 ')'

        // 计算结果
        if (!success) return {0, false}; // 如果读取参数失败
        if (op == "div" && p2 == 0) return {0, false}; // 除零错误

        return {calc(op, p1, p2), true}; // 返回计算结果
    }

    // 处理数字
    string number;
    while (index < expr.size() && (isdigit(expr[index]) || expr[index] == '-')) {
        number += expr[index++];
    }

    // 返回数字和成功标志
    return {stoll(number), true}; // 使用 stoll 以处理长整型
}

int main() {
    string s;
    getline(cin, s);
    
    size_t index = 0;
    auto [result, success] = evaluate(s, index);

    if (!success || result == LLONG_MIN) {
        cout << "error" << endl; // 处理错误
    } else {
        cout << result << endl; // 输出结果
    }
    
    return 0;
}

Python

def calc(op, p1, p2):
    # 计算两个 long long 整数的结果，处理除法的特例
    if op == "add":
        return p1 + p2
    elif op == "sub":
        return p1 - p2
    elif op == "mul":
        return p1 * p2
    else:  # div
        return float('-inf') if p2 == 0 else p1 // p2  # float('-inf') used to indicate error condition

def evaluate(expr, index):
    # 跳过空格
    while index[0] < len(expr) and expr[index[0]] == ' ':
        index[0] += 1

    # 如果到达字符串结尾
    if index[0] >= len(expr):
        return 0, False

    # 处理 '('
    if expr[index[0]] == '(':
        index[0] += 1  # 跳过 '('

        # 读取操作符
        op = ""
        while index[0] < len(expr) and expr[index[0]] != ' ' and expr[index[0]] != ')':
            op += expr[index[0]]
            index[0] += 1

        # 读取参数
        success = True

        # 递归读取第一个参数
        result1, res1Success = evaluate(expr, index)
        success = success and res1Success
        p1 = result1

        # 递归读取第二个参数
        result2, res2Success = evaluate(expr, index)
        success = success and res2Success
        p2 = result2

        # 处理 ')'
        while index[0] < len(expr) and expr[index[0]] != ')':
            index[0] += 1
        index[0] += 1  # 跳过 ')'

        # 计算结果
        if not success:
            return 0, False  # 如果读取参数失败
        if op == "div" and p2 == 0:
            return 0, False  # 除零错误

        return calc(op, p1, p2), True  # 返回计算结果

    # 处理数字
    number = ""
    while index[0] < len(expr) and (expr[index[0]].isdigit() or expr[index[0]] == '-'):
        number += expr[index[0]]
        index[0] += 1

    # 返回数字和成功标志
    return int(number), True  # 使用 int 以处理长整型

if __name__ == "__main__":
    s = input().strip()
    index = [0]
    result, success = evaluate(s, index)

    if not success or result == float('-inf'):
        print("error")  # 处理错误
    else:
        print(result)  # 输出结果

JAVA

import java.util.*;

public class Main {
    // 计算两个 long long 整数的结果，处理除法的特例
    public static long calc(String op, long p1, long p2) {
        if (op.equals("add")) {
            return p1 + p2;
        } else if (op.equals("sub")) {
            return p1 - p2;
        } else if (op.equals("mul")) {
            return p1 * p2;
        } else { // div
            return (p2 == 0) ? Long.MIN_VALUE : (long) Math.floor(p1 / (double) p2); // Long.MIN_VALUE used to indicate error condition
        }
    }

    // 递归解析并计算 LISP 表达式
    public static Pair<Long, Boolean> evaluate(String expr, int[] index) {
        // 跳过空格
        while (index[0] < expr.length() && expr.charAt(index[0]) == ' ') {
            index[0]++;
        }

        // 如果到达字符串结尾
        if (index[0] >= expr.length()) return new Pair<>(0L, false);

        // 处理 '('
        if (expr.charAt(index[0]) == '(') {
            index[0]++; // 跳过 '('

            // 读取操作符
            StringBuilder op = new StringBuilder();
            while (index[0] < expr.length() && expr.charAt(index[0]) != ' ' && expr.charAt(index[0]) != ')') {
                op.append(expr.charAt(index[0]++));
            }

            // 读取参数
            long p1, p2;
            boolean success = true;

            // 递归读取第一个参数
            Pair<Long, Boolean> result1 = evaluate(expr, index);
            success = success && result1.getValue();
            p1 = result1.getKey();

            // 递归读取第二个参数
            Pair<Long, Boolean> result2 = evaluate(expr, index);
            success = success && result2.getValue();
            p2 = result2.getKey();

            // 处理 ')'
            while (index[0] < expr.length() && expr.charAt(index[0]) != ')') {
                index[0]++; // 跳过空格
            }
            index[0]++; // 跳过 ')'

            // 计算结果
            if (!success) return new Pair<>(0L, false); // 如果读取参数失败
            if (op.toString().equals("div") && p2 == 0) return new Pair<>(0L, false); // 除零错误

            return new Pair<>(calc(op.toString(), p1, p2), true); // 返回计算结果
        }

        // 处理数字
        StringBuilder number = new StringBuilder();
        while (index[0] < expr.length() && (Character.isDigit(expr.charAt(index[0])) || expr.charAt(index[0]) == '-')) {
            number.append(expr.charAt(index[0]++));
        }

        // 返回数字和成功标志
        return new Pair<>(Long.parseLong(number.toString()), true); // 使用 parseLong 以处理长整型
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        scanner.close();

        int[] index = {0};
        Pair<Long, Boolean> result = evaluate(s, index);

        if (!result.getValue() || result.getKey() == Long.MIN_VALUE) {
            System.out.println("error"); // 处理错误
        } else {
            System.out.println(result.getKey()); // 输出结果
        }
    }

    // 简单的Pair类用于返回多个值
    static class Pair<K, V> {
        private K key;
        private V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

题目内容

$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$”

样例1

输入

(div 12 (sub 45 45))

输出

error

说明

$45$ 减 $45$ 得 $0$ ，$12$ 除以 $0$ 为除零错误，输出 $error$

样例2

输入

(add 1 (div -7 3))

输出

-2

说明

$-7$ 除以 $3$ 向下取整得 $-3$ ，$1$ 加 $-3$ 得 $-2$