LeetCode 736. Lisp 语法解析

Categories:

题目描述
思路分析
1. 解法一：递归下降解析（推荐）
相似题目

题目描述

✅ 736. Lisp 语法解析

思路分析

解法一：递归下降解析（推荐）

核心思路：

通过递归下降解析表达式，处理 add、mult、let 三种语法。

使用作用域栈保存变量绑定，let 进入新作用域，退出时回滚。

对数字、变量、括号表达式分别处理，保证语义正确。

复杂度分析：

时间复杂度：O(n)，其中 n 表示表达式长度。

空间复杂度：O(n)，递归深度与作用域栈占用。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int evaluate(String expression) {
        Parser parser = new Parser(expression);
        return parser.eval();
    }

    private static class Parser {
        private final String s;
        private int idx;
        private final Deque<Map<String, Integer>> scopes = new ArrayDeque<>();

        Parser(String s) {
            this.s = s;
            this.idx = 0;
        }

        int eval() {
            skipSpaces();
            char ch = s.charAt(idx);
            if (ch == '(') {
                idx++;
                skipSpaces();
                String op = parseToken();
                if (op.equals("add")) {
                    int a = eval();
                    int b = eval();
                    skipSpaces();
                    idx++;
                    return a + b;
                }
                if (op.equals("mult")) {
                    int a = eval();
                    int b = eval();
                    skipSpaces();
                    idx++;
                    return a * b;
                }

                // let
                scopes.push(new HashMap<>());
                while (true) {
                    skipSpaces();
                    char c = s.charAt(idx);
                    if (c == ')') {
                        idx++;
                        scopes.pop();
                        return 0;
                    }

                    if (c == '(' || c == '-' || Character.isDigit(c)) {
                        int val = eval();
                        skipSpaces();
                        idx++;
                        scopes.pop();
                        return val;
                    }

                    String var = parseToken();
                    skipSpaces();
                    if (s.charAt(idx) == ')') {
                        int val = resolve(var);
                        idx++;
                        scopes.pop();
                        return val;
                    }

                    int val = eval();
                    scopes.peek().put(var, val);
                }
            }

            return parseAtom();
        }

        private int parseAtom() {
            skipSpaces();
            char ch = s.charAt(idx);
            if (ch == '-' || Character.isDigit(ch)) {
                int sign = 1;
                if (ch == '-') {
                    sign = -1;
                    idx++;
                }

                int num = 0;
                while (idx < s.length() && Character.isDigit(s.charAt(idx))) {
                    num = num * 10 + (s.charAt(idx) - '0');
                    idx++;
                }
                return sign * num;
            }

            String var = parseToken();
            return resolve(var);
        }

        private int resolve(String var) {
            for (Map<String, Integer> scope : scopes) {
                if (scope.containsKey(var)) {
                    return scope.get(var);
                }
            }
            return 0;
        }

        private String parseToken() {
            int start = idx;
            while (idx < s.length()) {
                char ch = s.charAt(idx);
                if (ch == ' ' || ch == ')') {
                    break;
                }
                idx++;
            }
            return s.substring(start, idx);
        }

        private void skipSpaces() {
            while (idx < s.length() && s.charAt(idx) == ' ') {
                idx++;
            }
        }
    }
}

type Parser struct {
	s      string
	idx    int
	scopes []map[string]int
}

func evaluate(expression string) int {
	p := &Parser{s: expression, idx: 0}
	return p.eval()
}

func (p *Parser) eval() int {
	p.skipSpaces()
	ch := p.s[p.idx]
	if ch == '(' {
		p.idx++
		p.skipSpaces()
		op := p.parseToken()
		if op == "add" {
			a := p.eval()
			b := p.eval()
			p.skipSpaces()
			p.idx++
			return a + b
		}
		if op == "mult" {
			a := p.eval()
			b := p.eval()
			p.skipSpaces()
			p.idx++
			return a * b
		}

		// let
		p.scopes = append(p.scopes, map[string]int{})
		for {
			p.skipSpaces()
			c := p.s[p.idx]
			if c == ')' {
				p.idx++
				p.scopes = p.scopes[:len(p.scopes)-1]
				return 0
			}

			if c == '(' || c == '-' || (c >= '0' && c <= '9') {
				val := p.eval()
				p.skipSpaces()
				p.idx++
				p.scopes = p.scopes[:len(p.scopes)-1]
				return val
			}

			varName := p.parseToken()
			p.skipSpaces()
			if p.s[p.idx] == ')' {
				val := p.resolve(varName)
				p.idx++
				p.scopes = p.scopes[:len(p.scopes)-1]
				return val
			}

			val := p.eval()
			p.scopes[len(p.scopes)-1][varName] = val
		}
	}

	return p.parseAtom()
}

func (p *Parser) parseAtom() int {
	p.skipSpaces()
	ch := p.s[p.idx]
	if ch == '-' || (ch >= '0' && ch <= '9') {
		sign := 1
		if ch == '-' {
			sign = -1
			p.idx++
		}

		num := 0
		for p.idx < len(p.s) {
			c := p.s[p.idx]
			if c < '0' || c > '9' {
				break
			}
			num = num*10 + int(c-'0')
			p.idx++
		}
		return sign * num
	}

	varName := p.parseToken()
	return p.resolve(varName)
}

func (p *Parser) resolve(name string) int {
	for i := len(p.scopes) - 1; i >= 0; i-- {
		if val, ok := p.scopes[i][name]; ok {
			return val
		}
	}
	return 0
}

func (p *Parser) parseToken() string {
	start := p.idx
	for p.idx < len(p.s) {
		ch := p.s[p.idx]
		if ch == ' ' || ch == ')' {
			break
		}
		p.idx++
	}
	return p.s[start:p.idx]
}

func (p *Parser) skipSpaces() {
	for p.idx < len(p.s) && p.s[p.idx] == ' ' {
		p.idx++
	}
}

相似题目

题目	难度	考察点
224. 基本计算器	困难	递归解析
227. 基本计算器 II	中等	解析
772. 基本计算器 III	困难	递归解析
770. 基本计算器 IV	困难	表达式解析
1106. 解析布尔表达式	困难	递归解析

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/79643494