[LeetCode] Parse Lisp Expression 解析Lisp表达式

简介:

You are given a string expression representing a Lisp-like expression to return the integer value of.

The syntax for these expressions is given as follows. 

  • An expression is either an integer, a let-expression, an add-expression, a mult-expression, or an assigned variable. Expressions always evaluate to a single integer.
  • (An integer could be positive or negative.)
  • A let-expression takes the form (let v1 e1 v2 e2 ... vn en expr), where let is always the string "let", then there are 1 or more pairs of alternating variables and expressions, meaning that the first variable v1 is assigned the value of the expression e1, the second variable v2 is assigned the value of the expression e2, and so on sequentially; and then the value of this let-expression is the value of the expression expr.
  • An add-expression takes the form (add e1 e2) where add is always the string "add", there are always two expressions e1, e2, and this expression evaluates to the addition of the evaluation of e1 and the evaluation of e2.
  • A mult-expression takes the form (mult e1 e2) where mult is always the string "mult", there are always two expressions e1, e2, and this expression evaluates to the multiplication of the evaluation of e1 and the evaluation of e2.
  • For the purposes of this question, we will use a smaller subset of variable names. A variable starts with a lowercase letter, then zero or more lowercase letters or digits. Additionally for your convenience, the names "add", "let", or "mult" are protected and will never be used as variable names.
  • Finally, there is the concept of scope. When an expression of a variable name is evaluated, within the context of that evaluation, the innermost scope (in terms of parentheses) is checked first for the value of that variable, and then outer scopes are checked sequentially. It is guaranteed that every expression is legal. Please see the examples for more details on scope.

Evaluation Examples:

Input: (add 1 2)
Output: 3

Input: (mult 3 (add 2 3))
Output: 15

Input: (let x 2 (mult x 5))
Output: 10

Input: (let x 2 (mult x (let x 3 y 4 (add x y))))
Output: 14
Explanation: In the expression (add x y), when checking for the value of the variable x,
we check from the innermost scope to the outermost in the context of the variable we are trying to evaluate.
Since x = 3 is found first, the value of x is 3.

Input: (let x 3 x 2 x)
Output: 2
Explanation: Assignment in let statements is processed sequentially.

Input: (let x 1 y 2 x (add x y) (add x y))
Output: 5
Explanation: The first (add x y) evaluates as 3, and is assigned to x.
The second (add x y) evaluates as 3+2 = 5.

Input: (let x 2 (add (let x 3 (let x 4 x)) x))
Output: 6
Explanation: Even though (let x 4 x) has a deeper scope, it is outside the context
of the final x in the add-expression.  That final x will equal 2.

Input: (let a1 3 b2 (add a1 1) b2) 
Output 4
Explanation: Variable names can contain digits after the first character.

Note:

  • The given string expression is well formatted: There are no leading or trailing spaces, there is only a single space separating different components of the string, and no space between adjacent parentheses. The expression is guaranteed to be legal and evaluate to an integer.
  • The length of expression is at most 2000. (It is also non-empty, as that would not be a legal expression.)
  • The answer and all intermediate calculations of that answer are guaranteed to fit in a 32-bit integer.

 

这道题让我们解析Lisp语言的表达式,以前听说过Lisp语言,但是完全没有接触过,看了题目中的描述和给的例子,感觉很叼。估计题目只让我们处理一些简单的情况,毕竟不可能让我们写一个编译器出来。题目中说了给定的表达式都是合法的,这样也降低了难度。还有一个好的地方是题目给了充足的例子,让我们去更好的理解这门新的语言。我们通过分析例子发现,所有的命令都是用括号来包裹的,而且里面还可以嵌套小括号即子命令。让我们处理的命令只有三种,add,mult,和let。其中add和mult比较简单就是加法和乘法,就把后面两个数字或者子表达式的值加起来或成起来即可。let命令稍稍麻烦一些,后面可以跟好多变量或表达式,最简单的是三个,一般第一个是个变量,比如x,后面会跟一个数字或子表达式,就是把后面的数字或子表达式的值赋值给前面的变量,第三个位置是个表达式,其值是当前let命令的返回值。还有一个比较重要的特性是外层的变量值不会随着里层的变量值改变,比如对于下面这个例子:

(let x 2 (add (let x 3 (let x 4 x)) x))

刚开始x被赋值为2了,然后在返回值表达式中,又有一个add操作,add操作的第一个变量又是一个子表达式,在这个子表达式中又定义了一个变量x,并复制为3,再其返回值表达式又定义了一个变量x,赋值为4,并返回这个x,那么最内层的表达式的返回值是4,那么x被赋值为3的那层的返回值也是4,此时add的第一个数就是4,那么其第二个x是多少,其实这个x并没有被里层的x的影响,仍然是刚开始赋值的2,那么我们就看出特点了,外层的变量是能影响里层变量的,而里层变量无法影响外层变量。那么我们只要在递归的时候不加引用就行了,这样值就不会在递归函数中被更改了。

对于这种长度不定且每个可能包含子表达式的题,递归是一个很好的选择,由于需要给变量赋值,所以需要建立一个变量和其值之间的映射,然后我们就要来写递归函数了,最开始我们给定的表达式肯定是有括号的,所以我们先处理这种情况,括号对于我们的解析没有用,所以要去掉首尾的括号,然后我们用一个变量cur表示当前指向字符的位置,初始化为0,下面要做的就是先解析出命令单词,我们调用一个子函数parse,在parse函数中,简单的情况就是解析出add,mult,或let这三个命令单词,我们用一个指针来遍历字符,当越界或遇到空格就停止,但是如果我们需要解析的是个子表达式,而且里面可能还有多个子表达式,那么我们就需要找出最外面这个左括号对应的右括号,因为中间可能还会有别的左右括号,里面的内容就再之后再次调用递归函数时处理。判断的方法就是利用匹配括号的方法,用变量cnt来表示左括号的的个数,初始化为1,当要parse的表达式第一个字符是左括号时,进入循环,循环条件是cnt不为0,当遇到左括号时cnt自增1,反之当遇到右括号时cnt自减1,每次指针end都向右移动一个,最后我们根据end的位置减去初始时cur的值(保存在变量t中),可以得到表达式。如果解析出的是命令let,那么进行while循环,然后继续解析后面的内容,如果此时cur大于s的长度了,说明此时是let命令的最后一个部分,也就是返回值部分,直接调用递归函数返回即可。否则就再解析下一个部分,说明此时是变量和其对应值,我们要建立映射关系。如果之前解析出来的是add命令,那么比较简单,就直接解析出后面的两个部分的表达式,并分别调用递归函数,将递归函数的返回值累加并返回即可。对于mult命令同样的处理方式,只不过是将两个递归函数的返回值乘起来并返回。然后我们再来看如果表达式不是以左括号开头的,说明只能是数字或者变量,那么先来检测数字,如果第一个字符是负号或者0到9之间的数字,那么直接将表达式转为int型即可;否则的话就是变量,我们直接从哈希map中取值即可。最后需要注意的就是递归函数的参数哈希map一定不能加引用,具体可以参见上面那个例子的分析,加了引用后外层的变量值就会受内层的影响,这是不符合题意的,参见代码如下:

public:
    int evaluate(string expression) {
        unordered_map<string, int> m;
        return helper(expression, m);
    }
    int helper(string str, unordered_map<string, int> m) {
        if (str[0] == '-' || (str[0] >= '0' && str[0] <= '9')) return stoi(str);
        else if (str[0] != '(') return m[str];
        string s = str.substr(1, str.size() - 2);
        int cur = 0;
        string cmd = parse(s, cur);
        if (cmd == "let") {
            while (true) {
                string var = parse(s, cur);
                if (cur > s.size()) return helper(var, m);
                string t = parse(s, cur);
                m[var] = helper(t, m);
            }
        } else if (cmd == "add") {
            return helper(parse(s, cur), m) + helper(parse(s, cur), m);
        } else if (cmd == "mult") {
            return helper(parse(s, cur), m) * helper(parse(s, cur), m);
        }
    }
    string parse(string& s, int& cur) {
        int end = cur + 1, t = cur, cnt = 1;
        if (s[cur] == '(') {
            while (cnt != 0) {
                if (s[end] == '(') ++cnt;
                else if (s[end] == ')') --cnt;
                ++end;
            }
        } else {
            while (end < s.size() && s[end] != ' ') ++end;
        }
        cur = end + 1;
        return s.substr(t, end - t);
    }
};

参考资料:

https://discuss.leetcode.com/topic/112079/c-recursion-solution-with-explaination/2

LeetCode All in One 题目讲解汇总(持续更新中...)

本文转自博客园Grandyang的博客,原文链接:[LeetCode] Parse Lisp Expression 解析Lisp表达式

,如需转载请自行联系原博主。

相关文章
|
5月前
|
算法 Go 索引
【LeetCode 热题100】45:跳跃游戏 II(详细解析)(Go语言版)
本文详细解析了力扣第45题“跳跃游戏II”的三种解法:贪心算法、动态规划和反向贪心。贪心算法通过选择每一步能跳到的最远位置,实现O(n)时间复杂度与O(1)空间复杂度,是面试首选;动态规划以自底向上的方式构建状态转移方程,适合初学者理解但效率较低;反向贪心从终点逆向寻找最优跳点,逻辑清晰但性能欠佳。文章对比了各方法的优劣,并提供了Go语言代码实现,助你掌握最小跳跃次数问题的核心技巧。
195 15
|
5月前
|
机器学习/深度学习 存储 算法
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
315 90
|
4月前
|
存储 算法 Go
【LeetCode 热题100】17:电话号码的字母组合(详细解析)(Go语言版)
LeetCode 17题解题思路采用回溯算法,通过递归构建所有可能的组合。关键点包括:每位数字对应多个字母,依次尝试;递归构建下一个字符;递归出口为组合长度等于输入数字长度。Go语言实现中,使用map存储数字到字母的映射,通过回溯函数递归生成组合。时间复杂度为O(3^n * 4^m),空间复杂度为O(n)。类似题目包括括号生成、组合、全排列等。掌握回溯法的核心思想,能够解决多种排列组合问题。
104 11
|
4月前
|
Go
【LeetCode 热题100】155:最小栈(详细解析)(Go语言版)
本文详细解析了力扣热题155:最小栈的解题思路与实现方法。题目要求设计一个支持 push、核心思路是使用辅助栈法,通过两个栈(主栈和辅助栈)来维护当前栈中的最小值。具体操作包括:push 时同步更新辅助栈,pop 时检查是否需要弹出辅助栈的栈顶,getMin 时直接返回辅助栈的栈顶。文章还提供了 Go 语言的实现代码,并对复杂度进行了分析。此外,还介绍了单栈 + 差值记录法的进阶思路,并总结了常见易错点,如 pop 操作时忘记同步弹出辅助栈等。
119 6
|
4月前
|
Go 索引
【LeetCode 热题100】739:每日温度(详细解析)(Go语言版)
这篇文章详细解析了 LeetCode 第 739 题“每日温度”,探讨了如何通过单调栈高效解决问题。题目要求根据每日温度数组,计算出等待更高温度的天数。文中推荐使用单调递减栈,时间复杂度为 O(n),优于暴力解法的 O(n²)。通过实例模拟和代码实现(如 Go 语言版本),清晰展示了栈的操作逻辑。此外,还提供了思维拓展及相关题目推荐,帮助深入理解单调栈的应用场景。
129 6
|
5月前
|
存储 算法 数据可视化
【二叉树遍历入门:从中序遍历到层序与右视图】【LeetCode 热题100】94:二叉树的中序遍历、102:二叉树的层序遍历、199:二叉树的右视图(详细解析)(Go语言版)
本文详细解析了二叉树的三种经典遍历方式:中序遍历(94题)、层序遍历(102题)和右视图(199题)。通过递归与迭代实现中序遍历,深入理解深度优先搜索(DFS);借助队列完成层序遍历和右视图,掌握广度优先搜索(BFS)。文章对比DFS与BFS的思维方式,总结不同遍历的应用场景,为后续构造树结构奠定基础。
236 10
|
5月前
|
Go 索引 Perl
【LeetCode 热题100】【二叉树构造题精讲:前序 + 中序建树 & 有序数组构造 BST】(详细解析)(Go语言版)
本文详细解析了二叉树构造的两类经典问题:通过前序与中序遍历重建二叉树(LeetCode 105),以及将有序数组转化为平衡二叉搜索树(BST,LeetCode 108)。文章从核心思路、递归解法到实现细节逐一拆解,强调通过索引控制子树范围以优化性能,并对比两题的不同构造逻辑。最后总结通用构造套路,提供进阶思考方向,帮助彻底掌握二叉树构造类题目。
249 9
|
5月前
|
算法 Go
【LeetCode 热题100】73:矩阵置零(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 73——矩阵置零问题,提供两种解法:一是使用额外标记数组,时间复杂度为 O(m * n),空间复杂度为 O(m + n);二是优化后的原地标记方法,利用矩阵的第一行和第一列记录需要置零的信息,将空间复杂度降低到 O(1)。文章通过清晰的代码示例与复杂度分析,帮助理解“原地操作”及空间优化技巧,并推荐相关练习题以巩固矩阵操作能力。适合刷题提升算法思维!
124 9
|
5月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
157 10
|
6月前
|
存储 自然语言处理 算法
【LeetCode 热题100】208:实现 Trie (前缀树)(详细解析)(Go语言版)
本文详细解析了力扣热题 208——实现 Trie(前缀树)。Trie 是一种高效的树形数据结构,用于存储和检索字符串集合。文章通过插入、查找和前缀匹配三个核心操作,结合 Go 语言实现代码,清晰展示了 Trie 的工作原理。时间复杂度为 O(m),空间复杂度也为 O(m),其中 m 为字符串长度。此外,还探讨了 Trie 的变种及应用场景,如自动补全和词典查找等。适合初学者深入了解 Trie 结构及其实际用途。
155 14

推荐镜像

更多
  • DNS