LeetCode736. Lisp 语法解析

题目描述

本题目来自LeetCode上的『736. Lisp 语法解析』

给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。

表达式语法如下所示:

• 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
• (整数可以是正整数、负整数、0)
• let 表达式采用 "(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中 let 总是以字符串 "let"来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v1被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，依次类推；最终 let 表达式的值为 expr表达式的值。
• add 表达式表示为 "(add e1 e2)" ，其中 add 总是以字符串 "add" 来表示，该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。
• mult 表达式表示为 "(mult e1 e2)" ，其中 mult 总是以字符串 "mult" 表示，该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。
• 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，"add" ，"let" ，"mult" 会被定义为 “关键字” ，不会用作变量名。
• 最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。

示例1：

输入：expression = “(let x 2 (mult x (let x 3 y 4 (add x y))))”
输出：14
解释：
计算表达式 (add x y), 在检查变量 x 值时，
在变量的上下文中由最内层作用域依次向外检查。
首先找到 x = 3, 所以此处的 x 值是 3 。

提示

• 1 <= expression.length <= 2000
• exprssion 中不含前导和尾随空格
• expressoin 中的不同部分（token）之间用单个空格进行分隔
• 答案和所有中间计算结果都符合 32-bit 整数范围
• 测试用例中的表达式均为合法的且最终结果为整数

题解1 - LL(1)语法分析

类似 LL(1) 的语法分析，使用递归分析，消除左递归生成式如下：（编译原理忘得太干净了，有可能写错了，稍微一看就行
$$\begin{array}{rl}S& \to (L)\mid (A)\mid (M)\mid a\mid id\\ L& \to let\text{\ }{L}^{{}^{\prime }}\mid S{L}^{{}^{\prime }}\\ L^{{}^{\prime }}& \to id\text{\ }SL{L}^{{}^{\prime }}\mid \epsilon \\ A& \to add\text{\ }{A}^{{}^{\prime }}\\ A^{{}^{\prime }}& \to SS{A}^{{}^{\prime }}\mid \epsilon \\ M& \to mult\text{\ }{M}^{{}^{\prime }}\\ M^{{}^{\prime }}& \to SS{M}^{{}^{\prime }}\mid \epsilon \end{array}$$

使用栈记录每个变量在对应作用域的值，如 (let x (let x 2 3)) 中，x 的值先为 2 后为 3，使用 pos 记录当前分析的位置。具体递归分析过程如下

• 如果 expression 不是以左括号开头，那么它是一个变量或者整数，需要进行解析。
• 如果 expression 是以左括号开头，跳过左括号后，expression[pos]=='l'，表示 let 语句，跳过 let 字符后：
  • 如果 expression[pos] 不是字母，表示分析到 expr，递归调用分析 expr 的值
  • 如果 expression[pos] 是字母，则分析当前变量名，然后递归调用分析下一个表达式的值，赋给当前变量名
  • 如果 expression[pos] 是右括号，说明上一个分析的必是一个变量名，获取该变量的值并返回
• 如果 expression 是以左括号开头，跳过左括号后，expression[pos]=='a'，表示 add 语句，跳过 add 字符后，递归获取后面两个表达式的值，返回加和。
• 如果 expression 是以左括号开头，跳过左括号后，expression[pos]=='m'，表示 mult 语句，跳过 mult 字符后，递归获取后面两个表达式的值，返回乘积。

注： 本题还可以使用 LR(1) 的分析方法，摸了（

代码

class Solution {
private:
    int pos, n;
    string exp;
    unordered_map<string, stack<int>> varMap;

    // 分析变量名 id
    string parseVar() {
        string ret;
        for (; pos < n && exp[pos] != ' ' && exp[pos] != ')'; ++pos)
            ret += exp[pos];
        return ret;
    }

    // 分析整数值 a
    int parseInt() {
        int ret = 0, sign = 1;
        if (exp[pos] == '-') {
            sign = -1;
            ++pos;
        }
        for (; pos < n && isdigit(exp[pos]); ++pos) 
            ret = ret * 10 + (exp[pos] - '0');
        return ret * sign;
    }

    // 语法分析
    int parse() {
        // 不是左括号，说明是一个变量 id 或者整数 a
        if (exp[pos] != '(') {
            // 变量
            if (islower(exp[pos])) return varMap[parseVar()].top();
            // 整数
            else return parseInt();
        }
        int ret;
        ++pos; // 跳过左括号
        // 是 let
        if (exp[pos] == 'l') {
            pos += 4; // 跳过 let
            vector<string> vars; // 记录作用域内出现过的变量
            while (true) {
                // 不是字母开头，说明解析到 expr
                if (!islower(exp[pos])) {
                    ret = parse();
                    break;
                }
                // 分析 id
                string var = parseVar();
                // 上面的 var 是 let 最后的表达式 expr
                if (exp[pos] == ')') {
                    // 获取 var 的值
                    ret = varMap[var].top();
                    break;
                }
                // 不是 let 最后的表达式，说明给 var 赋上后面表达式的值
                vars.emplace_back(var);
                ++pos; // 跳过空格
                // 获得表达式的值
                varMap[var].emplace(parse());
                ++pos; // 跳过空格
            }
            // 当前作用域结束，还原上一个作用域的值
            for (const auto& var: vars) {
                varMap[var].pop();
            }
        } else if (exp[pos] == 'a') { // 是 add
            pos += 4; // 跳过 add
            int e1 = parse(); // 第一个表达式的值 e1
            ++pos; // 跳过空格
            int e2 = parse(); // 第一个表达式的值 e2
            ret = e1 + e2;
        } else { // 是 mult
            pos += 5; // 跳过 mult
            int e1 = parse(); // 第一个表达式的值 e1
            ++pos; // 跳过空格
            int e2 = parse(); // 第一个表达式的值 e2
            ret = e1 * e2;
        }
        ++pos; // 跳过右括号
        return ret;
    }


public:
    int evaluate(string expression) {
        this->exp = expression;
        this->n = expression.size();
        this->pos = 0;
        return parse();
    }
};

复杂度分析

• 时间复杂度：$O(n)$，每个字符只会遍历一遍
• 空间复杂度：$O(n)$