#P3210. 仿LISP运算(200分)
-
1000ms
Tried: 145
Accepted: 26
Difficulty: 6
所属公司 :
华为od
仿LISP运算(200分)
题目描述
给定一个字符串表示的嵌套LISP风格的数学表达式,要求编写程序解析并计算该表达式的结果。表达式中的操作包括加法(add)、减法(sub)、乘法(mul)和整数除法(div)四种。表达式中每个操作符的参数只有两个。对于 div 操作,如果第二个参数为 0,应输出 error 表示除零错误。
注意:可能会爆int。
解题思路
-
解析表达式:从输入的字符串逐个字符解析。遇到空格时跳过,遇到
(表示一个新的表达式开始。(后紧跟的是操作符(add、sub、mul、div),接着是两个操作数。 -
递归计算:表达式由多个嵌套的小表达式组成,采用递归来解析和计算结果:
- 遇到
(时,进入递归,依次解析操作符和两个操作数。 - 遇到数字或负号开头的数字,直接解析为整数。
- 遇到
)表示一个表达式结束,返回结果到上一级递归。
- 遇到
-
错误处理:
- 在
div操作中,如果第二个操作数为0,返回特殊错误值(如Long.MIN_VALUE),并在最终结果中输出 "error"。 - 解析失败时(如不符合格式)也返回错误标记。
- 在
-
返回结果:通过递归层层返回解析和计算的结果,最终输出在主函数中完成。
复杂度分析
- 时间复杂度: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