736. Parse Lisp Expression
https://leetcode.com/problems/parse-lisp-expression/description/
写一个简易的lisp expr parser，要支持三种表达式: (add x y)表示x+y, (mul x y)表示x * y，(let var1 e1 var2 e2 ... last_expr)表示e1赋给var1, e2赋给var2...最后整个表达式的值为last_expr的值。虽然这里有很多括号，但和之前遇到过的eval basket之类的用stack evaluate常量表达式的题不一样，这里()并不表示优先级而是最为表达式的分隔符，且还引入了变量的概念。解法很直观，分治递归解每个子表达式，然后把每个返回值再拼起来解当前的表达式。为了支持变量，每个表达式当作一个函数看待，用deque模拟call stack存储每个表达式产生的变量。
代码参考了花花的。
/*
* @lc app=leetcode id=736 lang=cpp
*
* [736] Parse Lisp Expression
*
* https://leetcode.com/problems/parse-lisp-expression/description/
*
* algorithms
* Hard (45.07%)
* Likes: 183
* Dislikes: 152
* Total Accepted: 7.9K
* Total Submissions: 17.5K
* Testcase Example: '"(add 1 2)"'
*
*
* 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.
*
*/
class Solution {
public:
deque<unordered_map<string, int>> scopes;
int eval(const string &s, int &pos) {
// 支持遍历的call stack
scopes.push_front(unordered_map<string, int>());
int val = 0;
if (s[pos] == '(') ++pos;
const string t = token(s, pos);
if (t == "add") {
val = eval(s, ++pos) + eval(s, ++pos);
} else if (t == "mult") {
val = eval(s, ++pos) * eval(s, ++pos);
} else if (t == "let") {
string var;
// expecting " var1 exp1 var2 exp2 ... last_expr"
while (s[pos] != ')') {
++pos;
// 每个eval会消耗它自身的()，当pos在这里还遇到(说明它是last_expr
if (s[pos] == '(') {
val = eval(s, ++pos);
break;
}
// x (add x y) 的x 或 -12)的-12
var = token(s, pos);
// 是 -12)
if (s[pos] == ')') {
if (isalpha(var[0])) val = value(var);
else val = stoi(var);
break;
}
// (add x y)
val = scopes.front()[var] = eval(s, ++pos);
}
} else if (isalpha(t[0])) {
// var
val = value(t);
} else {
val = stoi(t);
}
if (s[pos] == ')') ++pos;
scopes.pop_front();
return val;
}
int value(const string &symbol) {
// 遍历call stack直到找到var的值
for (const auto &scope : scopes) {
if (scope.count(symbol)) return scope.at(symbol);
}
return 0;
}
string token(const string &s, int &pos) {
string token;
while (pos < s.length()) {
if (s[pos] == ')' || s[pos] == ' ') break;
token += s[pos++];
}
return token;
}
int evaluate(string expression) {
int pos = 0;
return eval(expression, pos);
}
};
Last updated