仿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"

示例1

输入：
(div 12 (sub 45 45))

输出：
error

示例2

输入：
(add 1 (div -7 3))

输出：
-2

题解

使用递归方法来解析和计算LISP表达式。具体步骤如下：

1. 解析表达式：将输入的字符串解析成操作符和参数。参数可能是数字或其他嵌套的表达式。
2. 递归计算：对于每个操作符，递归计算其参数的值。如果参数是嵌套的表达式，继续递归解析和计算。
3. 处理操作：根据操作符的类型执行相应的算术操作。处理除法时，需检查除数是否为零，若为零则返回错误。
4. 错误处理：在计算过程中，任何除数为零的情况都应立即返回错误。

C++

// Author: code5bug
#include <bits/stdc++.h>

using namespace std;

// 整除（向下取整）
int floor_divide(int a, int b) {
    return static_cast<int>(std::floor(static_cast<double>(a) / b));
}

int evaluate(const string &expr) {
    string content = expr.substr(1, expr.size() - 2);
    vector<string> parts;
    string buffer;
    int parenLevel = 0;

    for (char c: content) {
        if (c == '(') {
            parenLevel++;
            buffer += c;
        } else if (c == ')') {
            parenLevel--;
            buffer += c;
        } else if (c == ' ' && parenLevel == 0) {
            if (!buffer.empty()) {
                parts.push_back(buffer);
                buffer.clear();
            }
        } else {
            buffer += c;
        }
    }
    if (!buffer.empty()) {
        parts.push_back(buffer);
    }

    if (parts.size() < 3) {
        throw invalid_argument("Invalid expression format");
    }

    string op = parts[0];
    string operand1 = parts[1];
    string operand2 = parts[2];

    auto parseOperand = [](const string &operand) -> int {
        if (operand[0] == '(') {
            return evaluate(operand);
        } else {
            return stoi(operand);
        }
    };

    int a = parseOperand(operand1);
    int b = parseOperand(operand2);

    if (op == "add") {
        return a + b;
    } else if (op == "sub") {
        return a - b;
    } else if (op == "mul") {
        return a * b;
    } else if (op == "div") {
        if (b == 0) {
            throw runtime_error("Division by zero");
        }
        return floor_divide(a, b);
    } else {
        throw invalid_argument("Unknown operator");
    }
}

int main() {
    string input;
    getline(cin, input);

    try {
        cout << evaluate(input) << endl;
    } catch (...) {
        cout << "error" << endl;
    }

    return 0;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏