华为OD机试真题——仿LISP运算（2025B卷：200分）Java/python/JavaScript/C/C++/GO最佳实现

2025 B卷 200分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《仿LISP运算》：

文章快捷目录

题目描述及说明

Java

python

JavaScript

C++

C

GO

题目名称：仿LISP运算

知识点：字符串、栈操作（递归/逆波兰）、逻辑处理
时间限制：1秒
空间限制：256MB
限定语言：不限

题目描述

LISP 语言唯一的语法是括号必须配对。表达式形如 (OP P1 P2 …)，括号内元素由单个空格分割。其中第一个元素 OP 为操作符，后续元素均为其参数，参数个数固定为 2。参数 P1、P2 可能是整数或其他嵌套的表达式。

运算符规则：

• add、sub、mul、div 分别代表加减乘除，运算结果为整数。
• 除法规则：向下取整（如 3/2=1）；若除数为 0，输出 error。
• 嵌套规则：表达式可多层嵌套，如 (sub (mul 2 4) (div 9 3))。

输入描述

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

输出描述

• 输出计算结果或 error。

示例

输入

(add 1 (div -7 3))  

输出

-2  

说明
div 运算中 -7/3 向下取整为 -3，add 结果为 1+(-3)=-2。

输入

(div 12 (sub 45 45))  

输出

error  

说明
sub 结果为 0，导致除零错误。

Java

问题分析

我们需要解析类似LISP的嵌套表达式，并计算结果。运算符包括add、sub、mul、div，每个运算符接受两个参数。除法需向下取整，若除数为0则输出error。表达式可能存在多层嵌套，例如(sub (mul 2 4) (div 9 3))。

解题思路

1. 递归解析：从最外层表达式开始，递归处理参数。若参数是嵌套表达式，则递归解析；若是数字，则直接转换。
2. 分割参数：处理表达式时，正确分割操作符后的两个参数。参数可能是数字或嵌套表达式，需考虑括号嵌套的情况。
3. 运算处理：根据操作符类型计算值，除法需判断除数是否为0，并正确取整。

代码实现

import java.util.*;

public class Main {
   
    public static void main(String[] args) {
   
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine().trim();
        try {
   
            int result = evaluate(input);
            System.out.println(result);
        } catch (Exception e) {
   
            System.out.println("error");
        }
    }

    private static int evaluate(String expr) throws Exception {
   
        if (expr.startsWith("(")) {
    // 判断是否是表达式
            return parse(expr);
        } else {
    // 否则为数字直接解析
            return Integer.parseInt(expr);
        }
    }

    private static int parse(String expr) throws Exception {
   
        // 去掉外层括号并去除首尾空格
        expr = expr.substring(1, expr.length() - 1).trim();
        int opEnd = expr.indexOf(' ');
        String op = expr.substring(0, opEnd); // 提取操作符
        String paramsStr = expr.substring(opEnd + 1).trim(); // 参数部分字符串

        // 分割参数为两个部分
        String[] params = splitParams(paramsStr);

        // 递归计算参数值
        int v1 = evaluate(params[0]);
        int v2 = evaluate(params[1]);

        // 根据操作符计算结果
        switch (op) {
   
            case "add":
                return v1 + v2;
            case "sub":
                return v1 - v2;
            case "mul":
                return v1 * v2;
            case "div":
                if (v2 == 0) {
   
                    throw new ArithmeticException("Division by zero");
                }
                return Math.floorDiv(v1, v2);
            default:
                throw new IllegalArgumentException("Invalid operator: " + op);
        }
    }

    private static String[] splitParams(String expr) {
   
        List<String> tokens = new ArrayList<>();
        int depth = 0; // 括号深度
        int start = 0;

        for (int i = 0; i < expr.length(); i++) {
   
            char c = expr.charAt(i);
            if (c == '(') depth++;
            else if (c == ')') depth--;
            
            // 当括号深度为0且遇到空格时分割参数
            if (c == ' ' && depth == 0) {
   
                if (start < i) {
   
                    tokens.add(expr.substring(start, i).trim());
                }
                start = i + 1;
                if (tokens.size() == 2) break; // 只需分割两个参数
            }
        }

        // 添加最后一个参数
        if (start <= expr.length()) {
   
            tokens.add(expr.substring(start).trim());
        }

        return new String[]{
   tokens.get(0), tokens.get(1)};
    }
}

代码解析

1. 主函数 main

   • 读取输入，调用evaluate处理表达式，捕获异常输出error。

2. 函数 evaluate

   • 判断表达式类型：若以(开头则递归解析，否则直接转换为数字。

3. 函数 parse

   • 去掉外层括号，分割操作符和参数。
   • 递归计算两个参数的值，执行对应运算。除法需检查除数是否为0。

4. 函数 splitParams

   • 遍历字符串，根据括号深度分割参数。深度为0时遇到空格分割，确保正确处理嵌套表达式。

示例测试

1. 输入1

   (add 1 (div -7 3))
   

   输出：-2
   解析：div -7 3得-3，add 1 -3结果为-2。

2. 输入2

   (div 12 (sub 45 45))
   

   输出：error
   解析：sub 45 45得0，除法除数为0抛出异常。

3. 输入3

   (mul (add 3 4) (sub 5 2))
   

   输出：21
   解析：add 3 4得7，sub 5 2得3，mul 7 3得21。

综合分析

1. 时间复杂度

   • 取决于表达式深度，最坏情况为O(2^N)（N为嵌套层数），但题目限定输入长度≤512，可在1秒内处理。

2. 空间复杂度

   • 递归调用栈深度为表达式嵌套层数，空间复杂度O(N)。

3. 正确性保障

   • 分割参数时严格处理括号嵌套，确保每个参数的完整性。
   • 除法检查除数为0，正确使用向下取整。

4. 优势

   • 递归结构简洁，直接模拟表达式计算过程。
   • 灵活处理嵌套表达式，保证正确分割参数。

5. 适用场景

   • 需要处理嵌套表达式的小规模问题，如编译器前端、公式解析等。

python

问题分析

我们需要解析类似LISP的递归嵌套表达式，并进行数学运算。表达式由括号包裹，运算符包括add、sub、mul、div，每个操作符接受两个参数。参数可以是整数或嵌套表达式。运算过程中需处理除零错误和整除向下取整。

解题思路

1. 递归解析：从外层表达式开始，递归处理每个参数。若参数是嵌套表达式，则递归解析；若是数字，直接转换。
2. 参数分割：正确分割操作符后的两个参数，考虑嵌套表达式中的括号匹配。
3. 运算处理：根据操作符计算值，除法检查除数是否为零，并确保整除向下取整。

代码实现

def evaluate(expr):
    expr = expr.strip()
    if expr.startswith('('):
        return parse(expr)
    else:
        return int(expr)

def parse(expr):
    expr = expr.strip()
    # 去掉外层括号
    if expr.startswith('(') and expr.endswith(')'):
        expr = expr[1:-1].strip()
    # 分割操作符和参数部分
    op_end = expr.find(' ')
    op = expr[:op_end]
    params_str = expr[op_end+1:].strip()
    # 分割两个参数
    params = split_params(params_str)
    # 递归计算参数值
    a = evaluate(params[0])
    b = evaluate(params[1])
    # 执行运算
    if op == 'add':
        return