class Solution {
public:
int evaluate(string expression) {
}
};
736. Lisp 语法解析
给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。
表达式语法如下所示:
"(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中 let 总是以字符串 "let"来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v1被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，依次类推；最终 let 表达式的值为 expr表达式的值。"(add e1 e2)" ，其中 add 总是以字符串 "add" 来表示，该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。"(mult e1 e2)" ，其中 mult 总是以字符串 "mult" 表示，该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。"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 <= 2000exprssion 中不含前导和尾随空格expressoin 中的不同部分（token）之间用单个空格进行分隔原站题解
python3 解法, 执行用时: 40 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-13 09:29:45
from enum import Enum, auto
class ExprStatus(Enum):
VALUE = auto() # 初始状态
NONE = auto() # 表达式类型未知
LET = auto() # let 表达式
LET1 = auto() # let 表达式已经解析了 vi 变量
LET2 = auto() # let 表达式已经解析了最后一个表达式 expr
ADD = auto() # add 表达式
ADD1 = auto() # add 表达式已经解析了 e1 表达式
ADD2 = auto() # add 表达式已经解析了 e2 表达式
MULT = auto() # mult 表达式
MULT1 = auto() # mult 表达式已经解析了 e1 表达式
MULT2 = auto() # mult 表达式已经解析了 e2 表达式
DONE = auto() # 解析完成
class Expr:
__slots__ = 'status', 'var', 'value', 'e1', 'e2'
def __init__(self, status):
self.status = status
self.var = '' # let 的变量 vi
self.value = 0 # VALUE 状态的数值，或者 LET2 状态最后一个表达式的数值
self.e1 = self.e2 = 0 # add 或 mult 表达式的两个表达式 e1 和 e2 的数值
class Solution:
def evaluate(self, expression: str) -> int:
scope = defaultdict(list)
def calculateToken(token: str) -> int:
return scope[token][-1] if token[0].islower() else int(token)
vars = []
s = []
cur = Expr(ExprStatus.VALUE)
i, n = 0, len(expression)
while i < n:
if expression[i] == ' ':
i += 1 # 去掉空格
continue
if expression[i] == '(':
i += 1 # 去掉左括号
s.append(cur)
cur = Expr(ExprStatus.NONE)
continue
if expression[i] == ')': # 本质上是把表达式转成一个 token
i += 1 # 去掉右括号
if cur.status is ExprStatus.LET2:
token = str(cur.value)
for var in vars[-1]:
scope[var].pop() # 清除作用域
vars.pop()
elif cur.status is ExprStatus.ADD2:
token = str(cur.e1 + cur.e2)
else:
token = str(cur.e1 * cur.e2)
cur = s.pop() # 获取上层状态
else:
i0 = i
while i < n and expression[i] != ' ' and expression[i] != ')':
i += 1
token = expression[i0:i]
if cur.status is ExprStatus.VALUE:
cur.value = int(token)
cur.status = ExprStatus.DONE
elif cur.status is ExprStatus.NONE:
if token == "let":
cur.status = ExprStatus.LET
vars.append([]) # 记录该层作用域的所有变量, 方便后续的清除
elif token == "add":
cur.status = ExprStatus.ADD
elif token == "mult":
cur.status = ExprStatus.MULT
elif cur.status is ExprStatus.LET:
if expression[i] == ')': # let 表达式的最后一个 expr 表达式
cur.value = calculateToken(token)
cur.status = ExprStatus.LET2
else:
cur.var = token
vars[-1].append(token) # 记录该层作用域的所有变量, 方便后续的清除
cur.status = ExprStatus.LET1
elif cur.status is ExprStatus.LET1:
scope[cur.var].append(calculateToken(token))
cur.status = ExprStatus.LET
elif cur.status is ExprStatus.ADD:
cur.e1 = calculateToken(token)
cur.status = ExprStatus.ADD1
elif cur.status is ExprStatus.ADD1:
cur.e2 = calculateToken(token)
cur.status = ExprStatus.ADD2
elif cur.status is ExprStatus.MULT:
cur.e1 = calculateToken(token)
cur.status = ExprStatus.MULT1
elif cur.status is ExprStatus.MULT1:
cur.e2 = calculateToken(token)
cur.status = ExprStatus.MULT2
return cur.value
java 解法, 执行用时: 8 ms, 内存消耗: 41.3 MB, 提交时间: 2023-04-13 09:29:27
class Solution {
Map<String, Deque<Integer>> scope = new HashMap<String, Deque<Integer>>();
public int evaluate(String expression) {
Deque<Deque<String>> vars = new ArrayDeque<Deque<String>>();
int start = 0, n = expression.length();
Deque<Expr> stack = new ArrayDeque<Expr>();
Expr cur = new Expr(ExprStatus.VALUE);
while (start < n) {
if (expression.charAt(start) == ' ') {
start++; // 去掉空格
continue;
}
if (expression.charAt(start) == '(') {
start++; // 去掉左括号
stack.push(cur);
cur = new Expr(ExprStatus.NONE);
continue;
}
StringBuffer sb = new StringBuffer();
if (expression.charAt(start) == ')') { // 本质上是把表达式转成一个 token
start++; // 去掉右括号
if (cur.status == ExprStatus.LET2) {
sb = new StringBuffer(Integer.toString(cur.value));
for (String var : vars.peek()) { // 清除作用域
scope.get(var).pop();
}
vars.pop();
} else if (cur.status == ExprStatus.ADD2) {
sb = new StringBuffer(Integer.toString(cur.e1 + cur.e2));
} else {
sb = new StringBuffer(Integer.toString(cur.e1 * cur.e2));
}
cur = stack.pop(); // 获取上层状态
} else {
while (start < n && expression.charAt(start) != ' ' && expression.charAt(start) != ')') {
sb.append(expression.charAt(start));
start++;
}
}
String token = sb.toString();
switch (cur.status.toString()) {
case "VALUE":
cur.value = Integer.parseInt(token);
cur.status = ExprStatus.DONE;
break;
case "NONE":
if ("let".equals(token)) {
cur.status = ExprStatus.LET;
vars.push(new ArrayDeque<String>()); // 记录该层作用域的所有变量, 方便后续的清除
} else if ("add".equals(token)) {
cur.status = ExprStatus.ADD;
} else if ("mult".equals(token)) {
cur.status = ExprStatus.MULT;
}
break;
case "LET":
if (expression.charAt(start) == ')') { // let 表达式的最后一个 expr 表达式
cur.value = calculateToken(token);
cur.status = ExprStatus.LET2;
} else {
cur.var = token;
vars.peek().push(token); // 记录该层作用域的所有变量, 方便后续的清除
cur.status = ExprStatus.LET1;
}
break;
case "LET1":
scope.putIfAbsent(cur.var, new ArrayDeque<Integer>());
scope.get(cur.var).push(calculateToken(token));
cur.status = ExprStatus.LET;
break;
case "ADD":
cur.e1 = calculateToken(token);
cur.status = ExprStatus.ADD1;
break;
case "ADD1":
cur.e2 = calculateToken(token);
cur.status = ExprStatus.ADD2;
break;
case "MULT":
cur.e1 = calculateToken(token);
cur.status = ExprStatus.MULT1;
break;
case "MULT1":
cur.e2 = calculateToken(token);
cur.status = ExprStatus.MULT2;
break;
}
}
return cur.value;
}
public int calculateToken(String token) {
if (Character.isLowerCase(token.charAt(0))) {
return scope.get(token).peek();
} else {
return Integer.parseInt(token);
}
}
}
enum ExprStatus {
VALUE, // 初始状态
NONE, // 表达式类型未知
LET, // let 表达式
LET1, // let 表达式已经解析了 vi 变量
LET2, // let 表达式已经解析了最后一个表达式 expr
ADD, // add 表达式
ADD1, // add 表达式已经解析了 e1 表达式
ADD2, // add 表达式已经解析了 e2 表达式
MULT, // mult 表达式
MULT1, // mult 表达式已经解析了 e1 表达式
MULT2, // mult 表达式已经解析了 e2 表达式
DONE // 解析完成
}
class Expr {
ExprStatus status;
String var; // let 的变量 vi
int value; // VALUE 状态的数值，或者 LET2 状态最后一个表达式的数值
int e1, e2; // add 或 mult 表达式的两个表达式 e1 和 e2 的数值
public Expr(ExprStatus s) {
status = s;
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2023-04-13 09:29:13
const (
VALUE = iota // 初始状态
NONE // 表达式类型未知
LET // let 表达式
LET1 // let 表达式已经解析了 vi 变量
LET2 // let 表达式已经解析了最后一个表达式 expr
ADD // add 表达式
ADD1 // add 表达式已经解析了 e1 表达式
ADD2 // add 表达式已经解析了 e2 表达式
MULT // mult 表达式
MULT1 // mult 表达式已经解析了 e1 表达式
MULT2 // mult 表达式已经解析了 e2 表达式
DONE // 解析完成
)
type expr struct {
status int
vr string // let 的变量 vi
value int // VALUE 状态的数值，或者 LET2 状态最后一个表达式的数值
e1, e2 int // add 或 mult 表达式的两个表达式 e1 和 e2 的数值
}
func evaluate(expression string) int {
scope := map[string][]int{}
calculateToken := func(token string) int {
if unicode.IsLower(rune(token[0])) {
vals := scope[token]
return vals[len(vals)-1]
}
val, _ := strconv.Atoi(token)
return val
}
vars := [][]string{}
s := []expr{}
cur := expr{status: VALUE}
for i, n := 0, len(expression); i < n; {
if expression[i] == ' ' {
i++ // 去掉空格
continue
}
if expression[i] == '(' {
i++ // 去掉左括号
s = append(s, cur)
cur.status = NONE
continue
}
var token string
if expression[i] == ')' { // 本质上是把表达式转成一个 token
i++ // 去掉右括号
if cur.status == LET2 {
token = strconv.Itoa(cur.value)
for _, vr := range vars[len(vars)-1] { // 清除作用域
scope[vr] = scope[vr][:len(scope[vr])-1]
}
vars = vars[:len(vars)-1]
} else if cur.status == ADD2 {
token = strconv.Itoa(cur.e1 + cur.e2)
} else {
token = strconv.Itoa(cur.e1 * cur.e2)
}
cur, s = s[len(s)-1], s[:len(s)-1] // 获取上层状态
} else {
i0 := i
for i < n && expression[i] != ' ' && expression[i] != ')' {
i++
}
token = expression[i0:i]
}
switch cur.status {
case VALUE:
cur.value, _ = strconv.Atoi(token)
cur.status = DONE
case NONE:
if token == "let" {
cur.status = LET
vars = append(vars, nil) // 记录该层作用域的所有变量, 方便后续的清除
} else if token == "add" {
cur.status = ADD
} else if token == "mult" {
cur.status = MULT
}
case LET:
if expression[i] == ')' { // let 表达式的最后一个 expr 表达式
cur.value = calculateToken(token)
cur.status = LET2
} else {
cur.vr = token
vars[len(vars)-1] = append(vars[len(vars)-1], token) // 记录该层作用域的所有变量, 方便后续的清除
cur.status = LET1
}
case LET1:
scope[cur.vr] = append(scope[cur.vr], calculateToken(token))
cur.status = LET
case ADD:
cur.e1 = calculateToken(token)
cur.status = ADD1
case ADD1:
cur.e2 = calculateToken(token)
cur.status = ADD2
case MULT:
cur.e1 = calculateToken(token)
cur.status = MULT1
case MULT1:
cur.e2 = calculateToken(token)
cur.status = MULT2
}
}
return cur.value
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2023-04-13 09:28:56
func evaluate(expression string) int {
i, n := 0, len(expression)
parseVar := func() string {
i0 := i
for i < n && expression[i] != ' ' && expression[i] != ')' {
i++
}
return expression[i0:i]
}
parseInt := func() int {
sign, x := 1, 0
if expression[i] == '-' {
sign = -1
i++
}
for i < n && unicode.IsDigit(rune(expression[i])) {
x = x*10 + int(expression[i]-'0')
i++
}
return sign * x
}
scope := map[string][]int{}
var innerEvaluate func() int
innerEvaluate = func() (ret int) {
if expression[i] != '(' { // 非表达式，可能为：整数或变量
if unicode.IsLower(rune(expression[i])) { // 变量
vals := scope[parseVar()]
return vals[len(vals)-1]
}
return parseInt() // 整数
}
i++ // 移除左括号
if expression[i] == 'l' { // "let" 表达式
i += 4 // 移除 "let "
vars := []string{}
for {
if !unicode.IsLower(rune(expression[i])) {
ret = innerEvaluate() // let 表达式的最后一个 expr 表达式的值
break
}
vr := parseVar()
if expression[i] == ')' {
vals := scope[vr]
ret = vals[len(vals)-1] // let 表达式的最后一个 expr 表达式的值
break
}
vars = append(vars, vr)
i++ // 移除空格
scope[vr] = append(scope[vr], innerEvaluate())
i++ // 移除空格
}
for _, vr := range vars {
scope[vr] = scope[vr][:len(scope[vr])-1] // 清除当前作用域的变量
}
} else if expression[i] == 'a' { // "add" 表达式
i += 4 // 移除 "add "
e1 := innerEvaluate()
i++ // 移除空格
e2 := innerEvaluate()
ret = e1 + e2
} else { // "mult" 表达式
i += 5 // 移除 "mult "
e1 := innerEvaluate()
i++ // 移除空格
e2 := innerEvaluate()
ret = e1 * e2
}
i++ // 移除右括号
return
}
return innerEvaluate()
}
java 解法, 执行用时: 2 ms, 内存消耗: 41.2 MB, 提交时间: 2023-04-13 09:28:38
class Solution {
Map<String, Deque<Integer>> scope = new HashMap<String, Deque<Integer>>();
int start = 0;
public int evaluate(String expression) {
return innerEvaluate(expression);
}
public int innerEvaluate(String expression) {
if (expression.charAt(start) != '(') { // 非表达式，可能为：整数或变量
if (Character.isLowerCase(expression.charAt(start))) {
String var = parseVar(expression); // 变量
return scope.get(var).peek();
} else { // 整数
return parseInt(expression);
}
}
int ret;
start++; // 移除左括号
if (expression.charAt(start) == 'l') { // "let" 表达式
start += 4; // 移除 "let "
List<String> vars = new ArrayList<String>();
while (true) {
if (!Character.isLowerCase(expression.charAt(start))) {
ret = innerEvaluate(expression); // let 表达式的最后一个 expr 表达式的值
break;
}
String var = parseVar(expression);
if (expression.charAt(start) == ')') {
ret = scope.get(var).peek(); // let 表达式的最后一个 expr 表达式的值
break;
}
vars.add(var);
start++; // 移除空格
int e = innerEvaluate(expression);
scope.putIfAbsent(var, new ArrayDeque<Integer>());
scope.get(var).push(e);
start++; // 移除空格
}
for (String var : vars) {
scope.get(var).pop(); // 清除当前作用域的变量
}
} else if (expression.charAt(start) == 'a') { // "add" 表达式
start += 4; // 移除 "add "
int e1 = innerEvaluate(expression);
start++; // 移除空格
int e2 = innerEvaluate(expression);
ret = e1 + e2;
} else { // "mult" 表达式
start += 5; // 移除 "mult "
int e1 = innerEvaluate(expression);
start++; // 移除空格
int e2 = innerEvaluate(expression);
ret = e1 * e2;
}
start++; // 移除右括号
return ret;
}
public int parseInt(String expression) { // 解析整数
int n = expression.length();
int ret = 0, sign = 1;
if (expression.charAt(start) == '-') {
sign = -1;
start++;
}
while (start < n && Character.isDigit(expression.charAt(start))) {
ret = ret * 10 + (expression.charAt(start) - '0');
start++;
}
return sign * ret;
}
public String parseVar(String expression) { // 解析变量
int n = expression.length();
StringBuffer ret = new StringBuffer();
while (start < n && expression.charAt(start) != ' ' && expression.charAt(start) != ')') {
ret.append(expression.charAt(start));
start++;
}
return ret.toString();
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.1 MB, 提交时间: 2023-04-13 09:27:53
# 递归解析
class Solution:
def evaluate(self, expression: str) -> int:
i, n = 0, len(expression)
def parseVar() -> str:
nonlocal i
i0 = i
while i < n and expression[i] != ' ' and expression[i] != ')':
i += 1
return expression[i0:i]
def parseInt() -> int:
nonlocal i
sign, x = 1, 0
if expression[i] == '-':
sign = -1
i += 1
while i < n and expression[i].isdigit():
x = x * 10 + int(expression[i])
i += 1
return sign * x
scope = defaultdict(list)
def innerEvaluate() -> int:
nonlocal i
if expression[i] != '(': # 非表达式，可能为：整数或变量
if expression[i].islower(): # 变量
return scope[parseVar()][-1]
return parseInt() # 整数
i += 1 # 移除左括号
if expression[i] == 'l': # "let" 表达式
i += 4 # 移除 "let "
vars = []
while True:
if not expression[i].islower():
ret = innerEvaluate() # let 表达式的最后一个 expr 表达式的值
break
var = parseVar()
if expression[i] == ')':
ret = scope[var][-1] # let 表达式的最后一个 expr 表达式的值
break
vars.append(var)
i += 1 # 移除空格
scope[var].append(innerEvaluate())
i += 1 # 移除空格
for var in vars:
scope[var].pop() # 清除当前作用域的变量
elif expression[i] == 'a': # "add" 表达式
i += 4 # 移除 "add "
e1 = innerEvaluate()
i += 1 # 移除空格
e2 = innerEvaluate()
ret = e1 + e2
else: # "mult" 表达式
i += 5 # 移除 "mult "
e1 = innerEvaluate()
i += 1 # 移除空格
e2 = innerEvaluate()
ret = e1 * e2
i += 1 # 移除右括号
return ret
return innerEvaluate()