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 。

---

示例 2：

输入：expression = "(let x 3 x 2 x)"
输出：2
解释：let 语句中的赋值运算按顺序处理即可。

---

示例 3：

输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
输出：5
解释：
第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。 
第二个 (add x y) 计算结果是 3 + 2 = 5

---

提示：

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

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/parse-lisp-expression
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

其实思路说起来没什么，每一个细节说出来都懂，但是细节太多写起来麻烦。

首先就是括号套娃。解析到一半的时候会遇到(let temp 9 (add 1 (mult 2这样的不完整括号，用栈来表示。不过这里我直接用std::vector了，是因为这样还可以访问栈底元素的变量表。

然后是变量表。用unordered_map表示从变量名到变量值之间的映射。这里用string_view表示变量名，在string_view内部直接通过指针访问输入表达式中的字符数据，省去了一些复制。考虑到变量作用域，栈中每一层的let函数都有个独立变量表，查找时优先从内层查找。

词法分析很简单，左括号和右括号是特殊符号，除此之外的字符都用括号或空格分隔成单词，一个单词可能是函数名、变量名或数字，左括号后第一个单词是函数名，以数字或负号开头为数字。

每起一个左括号，就开始数这是第几个参数，参数可能是单词也可能是嵌套括号，那么在遇到单词时和遇到右括号（除了最后一个右括号）时都应该填一个参数进来。

加法和乘法比较简单，数够两个参数就行。比较复杂的是let，他的参数比较特殊，第奇数个参数可能是变量名，也可能是最终返回值。当第奇数个参数是变量名时，还应该注意变量名后是否还有参数，那么这个变量名其实是返回值。例如(let x 8 x)中最后一个x其实是返回值，他和(let x 8 x 9 10)中第二个x的意义完全不同。

---

作者：chronosphere
链接：https://leetcode.cn/problems/parse-lisp-expression/solution/c-8ms-9467-73mb-bian-li-yi-ci-biao-da-shi-gou-zao-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

---

代码：

class Solution {
    struct IncompleteExpression {
        unordered_map<string_view, int> variables;
        string_view varname;
        int count, value;
        char type;  // 函数名首字母
 
        IncompleteExpression() : variables(), varname(), count(0), value(), type() {}
 
        void update_arithmetic(int val) {
            if(type == 'a') { // 加法
                if(count == 1) { // 第一个参数（第零个是函数名）
                    value = val;
                } else {         // 第二个参数
                    value += val;
                }
            } else {       // 乘法
                if(count == 1) {
                    value = val;
                } else {
                    value *= val;
                }
            }
        }
    };
    
    struct Parser {
        vector<IncompleteExpression> nested;
        int value;
 
        // 求一个数字的值
        static int eval_int(const char* str, size_t str_len) {
            int x = 0;
            for(size_t i = 0; i != str_len; ++i) {
                x = x * 10 + str[i] - '0';
            }
            return x; 
        }
        
        // 求一个变量的值
        int eval_variable(string_view name) {
            for(auto i = nested.rbegin(), e = nested.rend(); i != e; ++i) {
                auto x = i->variables.find(name);
                if(x != i->variables.end()) {
                    return x->second;
                }
            }
            return 0;
        }
 
        // 求一个变量或数字的值
        int eval(const char* str, size_t str_len) {
            if(isdigit(*str)) {
                return eval_int(str, str_len);
            } else if (*str == '-') { // 不支持变量前加负号，负号开头的只能是数字
                return - eval_int(str + 1, str_len - 1);
            } else return eval_variable(string_view(str, str_len));
        }
 
        // 遇到左括号
        void left_parenthesis() {
            nested.emplace_back();
        }
 
        // 遇到右括号
        void right_parenthesis() {
            auto& inner = nested.back();
            int val;
            if(!inner.varname.empty()) { // 右括号前有个变量名还没解析 e.g. (let x 8 x)
                val = eval_variable(inner.varname);
            } else {
                val = inner.value;
            }
            nested.pop_back();
            if(!nested.empty()) {  // 不是最后一个大括号
                auto& t = nested.back();
                if(t.type == 'l') { // let
                    if((t.count & 1) != 0) {
                        t.value = val;
                    } else {
                        t.variables[t.varname] = val;
                        t.varname = string_view(); // 清空未解析的变量名
                    }
                }  else {
                    t.update_arithmetic(val);
                }
                ++t.count;
            } else {// 最后一个大括号，得到最终结果存在Parser::value里
                value = val;
            }
        }
 
        // 可能是函数名、变量名或数字
        void new_identifier(const char* str, size_t str_len) {
            auto& t = nested.back();
            if(t.count == 0) {
                t.type = *str;
            } else if(t.type == 'l') { // let
                if((t.count & 1) != 0) {
                    if (isdigit(*str)) {
                        t.value = eval_int(str, str_len);
                    } else if (*str == '-') { // 不支持变量前加负号，负号开头的只能是数字
                        t.value = - eval_int(str + 1, str_len - 1);
                    } else {
                        t.varname = string_view(str, str_len);
                    }
                } else {
                    t.variables[t.varname] = eval(str, str_len);
                    t.varname = string_view(); // 清空未解析的变量名
                }
            } else {
                t.update_arithmetic(eval(str, str_len));
            }
            ++t.count;
        }
    };
public:
    int evaluate(string expression) {
        Parser parser;
        for(auto i = expression.cbegin(), e = expression.cend(); i != e;) {
            if(*i == '(') {
                parser.left_parenthesis();
                ++i;
            } else if(*i == ')') {
                parser.right_parenthesis();
                ++i;
            } else if(isspace(*i)) {
                ++i;
            } else {
                auto j = i;
                for(; !isspace(*i) && *i != '(' && *i != ')'; ++i);
                parser.new_identifier(addressof(*j), i - j);
            }
        }
        return parser.value;
    }
};