仿LISP运算

真题目录: 点击去查看

E 卷 200分题型

题目描述

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

题解

思路：

纯逻辑题，难点在于将括号中的片段截取出来，我的处理方案是，遍历输入的每一个字符，当遇到")“时，则在其前面必然存在一个“(”，找到其前面第一个“(”，然后截取“(”和”)"之间的内容（从栈中截取走），进行计算，将结果回填如栈中。

c++

#include <iostream>
#include <stack>
#include <vector>
#include <sstream>
#include <cmath>using namespace std;int operate(const string& op, int p1, int p2) {if (op == "add") return p1 + p2;if (op == "sub") return p1 - p2;if (op == "mul") return p1 * p2;if (op == "div") {if (p2 == 0) throw runtime_error("error");return floor(1.0 * p1 / p2);  // 向下取整}throw runtime_error("error");
}string getResult(const string& s) {// 记录一个括号开始之前栈中元素个数stack<int> leftIdx;// 存储运算符和运算数字vector<string> stack;for (size_t i = 0; i < s.length(); ++i) {if (s[i] == ')') {int l = leftIdx.top();leftIdx.pop();vector<string> fragment(stack.begin() + l, stack.end());stack.erase(stack.begin() + l, stack.end());if (fragment.size() != 3) return "error";try {int p1 = stoi(fragment[1]);int p2 = stoi(fragment[2]);int res = operate(fragment[0], p1, p2);stack.push_back(to_string(res));} catch (...) {return "error";}} else if (s[i] == '(') {leftIdx.push(stack.size());} else if (s[i] != ' ') {string token;while (i < s.length() && s[i] != ' ' && s[i] != ')') {token += s[i];++i;}--i;stack.push_back(token);}}return stack.empty() ? "error" : stack[0];
}int main() {string s;getline(cin, s);try {cout << getResult(s) << endl;} catch (const exception& e) {cout << "error" << endl;}return 0;
}

JAVA

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println(getResult(sc.nextLine()));}public static String getResult(String s) {LinkedList<Character> stack = new LinkedList<>();LinkedList<Integer> leftIdx = new LinkedList<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == ')') {List<Character> fragment = stack.subList(leftIdx.removeLast(), stack.size());StringBuilder sb = new StringBuilder();for (int j = 1; j < fragment.size(); j++) sb.append(fragment.get(j));fragment.clear();String[] tmp = sb.toString().split(" ");String op = tmp[0];int p1 = Integer.parseInt(tmp[1]);int p2 = Integer.parseInt(tmp[2]);String res = operate(op, p1, p2);if ("error".equals(res)) {return "error";} else {for (int k = 0; k < res.length(); k++) stack.add(res.charAt(k));}} else if (c == '(') {leftIdx.add(stack.size());stack.add(c);} else {stack.add(c);}}StringBuilder ans = new StringBuilder();for (Character c : stack) ans.append(c);return ans.toString();}public static String operate(String op, int p1, int p2) {switch (op) {case "add":return p1 + p2 + "";case "sub":return p1 - p2 + "";case "mul":return p1 * p2 + "";case "div":return p2 == 0 ? "error" : (int) Math.floor(p1 / (p2 + 0.0)) + "";default:return "error";}}
}

Python

import math# 输入获取
s = input()def operate(op, p1, p2):p1 = int(p1)p2 = int(p2)if op == "add":return str(p1 + p2)elif op == "sub":return str(p1 - p2)elif op == "mul":return str(p1 * p2)elif op == "div":if p2 == 0:return "error"else:return str(int(math.floor(p1 / p2)))else:return "error"# 算法入口
def getResult():stack = []leftIdx = []for i in range(len(s)):if s[i] == ')':l = leftIdx.pop()fragment = stack[l:]del stack[l:]op, p1, p2 = "".join(fragment[1:]).split(" ")res = operate(op, p1, p2)if res == "error":return "error"else:stack.extend(list(res))elif s[i] == '(':leftIdx.append(len(stack))stack.append(s[i])else:stack.append(s[i])return "".join(stack)# 调用算法
print(getResult())

JavaScript

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});rl.on("line", (line) => {console.log(getResult(line));
});function getResult(s) {const stack = [];const leftIdx = [];for (let i = 0; i < s.length; i++) {if (s[i] === ")") {const fragment = stack.splice(leftIdx.pop());const [op, p1, p2] = fragment.slice(1).join("").split(" ");const res = operate(op, p1 - 0, p2 - 0);if (res === "error") return "error";else stack.push(...String(res));} else if (s[i] === "(") {leftIdx.push(stack.length);stack.push(s[i]);} else {stack.push(s[i]);}}return stack.join("");
}function operate(op, p1, p2) {switch (op) {case "add":return p1 + p2;case "sub":return p1 - p2;case "mul":return p1 * p2;case "div":return p2 === 0 ? "error" : Math.floor(p1 / p2);}
}

Go

package mainimport ("bufio""fmt""math""os""strconv"
)// operate 计算加、减、乘、除运算
func operate(op string, p1, p2 int) (int, error) {switch op {case "add":return p1 + p2, nilcase "sub":return p1 - p2, nilcase "mul":return p1 * p2, nilcase "div":if p2 == 0 {return 0, fmt.Errorf("error") // 返回错误}return int(math.Floor(float64(p1) / float64(p2))), nildefault:return 0, fmt.Errorf("error") // 无效运算符}
}// getResult 解析 LISP 表达式并计算结果
func getResult(s string) string {var stack []stringvar leftIdx []int // 记录 '(' 在 stack 中的索引for i := 0; i < len(s); i++ {if s[i] == ')' {// 取出最近的 '(' 位置if len(leftIdx) == 0 {return "error"}l := leftIdx[len(leftIdx)-1]leftIdx = leftIdx[:len(leftIdx)-1]// 取出括号内的内容fragment := stack[l:]stack = stack[:l] // 移除括号内的内容if len(fragment) != 3 {return "error"}// 解析操作符和两个操作数p1, err1 := strconv.Atoi(fragment[1])p2, err2 := strconv.Atoi(fragment[2])if err1 != nil || err2 != nil {return "error"}// 执行计算res, err := operate(fragment[0], p1, p2)if err != nil {return "error"}// 结果存入 stackstack = append(stack, strconv.Itoa(res))} else if s[i] == '(' {leftIdx = append(leftIdx, len(stack))} else if s[i] != ' ' {// 读取完整的 tokentoken := ""for i < len(s) && s[i] != ' ' && s[i] != ')' {token += string(s[i])i++}i-- // 回退一格防止跳过字符stack = append(stack, token)}}if len(stack) != 1 {return "error"}return stack[0]
}func main() {scanner := bufio.NewScanner(os.Stdin)if scanner.Scan() {expr := scanner.Text()fmt.Println(getResult(expr))}
}