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))。
解題思路
- 遞歸解析：從最外層表達式開始，遞歸處理參數。若參數是嵌套表達式，則遞歸解析；若是數字，則直接轉換。
- 分割參數：處理表達式時，正確分割操作符后的兩個參數。參數可能是數字或嵌套表達式，需考慮括號嵌套的情況。
- 運算處理：根據操作符類型計算值，除法需判斷除數是否為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)};}
}
代碼解析
-
主函數
main- 讀取輸入，調用
evaluate處理表達式，捕獲異常輸出error。
- 讀取輸入，調用
-
函數
evaluate- 判斷表達式類型：若以
(開頭則遞歸解析，否則直接轉換為數字。
- 判斷表達式類型：若以
-
函數
parse- 去掉外層括號，分割操作符和參數。
- 遞歸計算兩個參數的值，執行對應運算。除法需檢查除數是否為0。
-
函數
splitParams- 遍歷字符串，根據括號深度分割參數。深度為0時遇到空格分割，確保正確處理嵌套表達式。
示例測試
-
輸入1
(add 1 (div -7 3))輸出：
-2
解析：div -7 3得-3，add 1 -3結果為-2。 -
輸入2
(div 12 (sub 45 45))輸出：
error
解析：sub 45 45得0，除法除數為0拋出異常。 -
輸入3
(mul (add 3 4) (sub 5 2))輸出：
21
解析：add 3 4得7，sub 5 2得3，mul 7 3得21。
綜合分析
-
時間復雜度
- 取決于表達式深度，最壞情況為
O(2^N)（N為嵌套層數），但題目限定輸入長度≤512，可在1秒內處理。
- 取決于表達式深度，最壞情況為
-
空間復雜度
- 遞歸調用棧深度為表達式嵌套層數，空間復雜度
O(N)。
- 遞歸調用棧深度為表達式嵌套層數，空間復雜度
-
正確性保障
- 分割參數時嚴格處理括號嵌套，確保每個參數的完整性。
- 除法檢查除數為0，正確使用向下取整。
-
優勢
- 遞歸結構簡潔，直接模擬表達式計算過程。
- 靈活處理嵌套表達式，保證正確分割參數。
-
適用場景
- 需要處理嵌套表達式的小規模問題，如編譯器前端、公式解析等。
python
問題分析
我們需要解析類似LISP的遞歸嵌套表達式，并進行數學運算。表達式由括號包裹，運算符包括add、sub、mul、div，每個操作符接受兩個參數。參數可以是整數或嵌套表達式。運算過程中需處理除零錯誤和整除向下取整。
解題思路
- 遞歸解析：從外層表達式開始，遞歸處理每個參數。若參數是嵌套表達式，則遞歸解析；若是數字，直接轉換。
- 參數分割：正確分割操作符后的兩個參數，考慮嵌套表達式中的括號匹配。
- 運算處理：根據操作符計算值，除法檢查除數是否為零，并確保整除向下取整。
代碼實現
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
