The "Parse Lisp Expression" problem asks you to evaluate a string that represents a Lisp-like expression. The expression can contain integers, variables, and the following operations: add, mult, and let.
add takes two expressions and returns their sum.
mult takes two expressions and returns their product.
let allows you to assign values to variables for use within the current expression scope.
Expressions are given as strings, for example: "(add 1 2)", "(mult 3 (add 2 3))", or "(let x 2 (mult x 5))".
Key constraints:
let expression.At first glance, the problem seems to require parsing nested expressions and evaluating them according to Lisp semantics. A brute-force approach might involve string manipulation and recursion, but this can quickly get messy due to variable scoping and nested expressions.
The main challenge is handling variable scopes, especially with nested let expressions. Each let can shadow variables from outer scopes, and we must restore previous values once we exit the scope. This suggests that we need a way to manage variable environments, such as using a stack or a dictionary that supports scoping.
The optimized approach is to recursively parse and evaluate the expression while maintaining a stack of variable scopes. This ensures correct variable resolution and clean handling of nested expressions.
Let's break down the solution step-by-step:
add, mult, or let).
let expression, push a new scope onto the stack.
add and mult, recursively evaluate their two arguments.
let, process variable assignments in order, then evaluate and return the final expression.
This approach ensures that variables are resolved correctly according to their scope, and that nested expressions are handled via recursion.
Let's walk through the evaluation of "(let x 2 (mult x 5))":
let, so we enter a new scope.
x = 2 in the current scope.
(mult x 5):
x in the current scope, which is 2.
5, which is 5.
let expression.
Another example: "(let x 2 (let y 3 (add x y)))"
let: assign x = 2let: assign y = 3add x y: x=2, y=3, so result is 5.The "Parse Lisp Expression" problem is a classic example of recursive parsing and evaluation, with the added challenge of variable scoping. By maintaining a stack of variable scopes and using recursion to process nested expressions, we can efficiently and elegantly evaluate any valid Lisp-like expression. The solution combines careful parsing, recursion, and environment management to handle all cases in a clean and modular way.
class Solution:
def evaluate(self, expression: str) -> int:
def parse(expr):
tokens, i, n = [], 0, len(expr)
while i < n:
if expr[i] == '(':
bal, j = 0, i
while i < n:
if expr[i] == '(':
bal += 1
if expr[i] == ')':
bal -= 1
i += 1
if bal == 0:
break
tokens.append(expr[j:i])
elif expr[i] != ' ':
j = i
while i < n and expr[i] != ' ':
i += 1
tokens.append(expr[j:i])
else:
i += 1
return tokens
def eval_expr(expr, env):
if expr[0] != '(':
if expr.lstrip('-').isdigit():
return int(expr)
for scope in reversed(env):
if expr in scope:
return scope[expr]
raise Exception("Variable not found")
expr = expr[1:-1]
tokens = parse(expr)
if tokens[0] == 'add':
return eval_expr(tokens[1], env) + eval_expr(tokens[2], env)
elif tokens[0] == 'mult':
return eval_expr(tokens[1], env) * eval_expr(tokens[2], env)
elif tokens[0] == 'let':
new_env = env + [{}]
i = 1
while i < len(tokens) - 1:
var = tokens[i]
val = eval_expr(tokens[i+1], new_env)
new_env[-1][var] = val
i += 2
return eval_expr(tokens[-1], new_env)
return eval_expr(expression, [])
class Solution {
public:
int evaluate(string expression) {
return eval(expression, {});
}
private:
vector<unordered_map<string, int>> envStack;
vector<string> parse(const string& expr) {
vector<string> tokens;
int i = 0, n = expr.size();
while (i < n) {
if (expr[i] == '(') {
int bal = 0, j = i;
while (i < n) {
if (expr[i] == '(') bal++;
if (expr[i] == ')') bal--;
i++;
if (bal == 0) break;
}
tokens.push_back(expr.substr(j, i - j));
} else if (expr[i] != ' ') {
int j = i;
while (i < n && expr[i] != ' ') i++;
tokens.push_back(expr.substr(j, i - j));
} else {
i++;
}
}
return tokens;
}
int eval(const string& expr, vector<unordered_map<string, int>> env) {
if (expr[0] != '(') {
if (isdigit(expr[0]) || expr[0] == '-') {
return stoi(expr);
}
for (int i = env.size() - 1; i >= 0; --i) {
if (env[i].count(expr)) return env[i][expr];
}
throw runtime_error("Variable not found");
}
string inner = expr.substr(1, expr.size() - 2);
vector<string> tokens = parse(inner);
if (tokens[0] == "add") {
return eval(tokens[1], env) + eval(tokens[2], env);
} else if (tokens[0] == "mult") {
return eval(tokens[1], env) * eval(tokens[2], env);
} else if (tokens[0] == "let") {
env.push_back({});
int i = 1;
while (i < tokens.size() - 1) {
string var = tokens[i];
int val = eval(tokens[i + 1], env);
env.back()[var] = val;
i += 2;
}
return eval(tokens.back(), env);
}
return 0;
}
};
class Solution {
public int evaluate(String expression) {
return eval(expression, new ArrayList<>());
}
private List<Map<String, Integer>> envStack = new ArrayList<>();
private List<String> parse(String expr) {
List<String> tokens = new ArrayList<>();
int i = 0, n = expr.length();
while (i < n) {
if (expr.charAt(i) == '(') {
int bal = 0, j = i;
while (i < n) {
if (expr.charAt(i) == '(') bal++;
if (expr.charAt(i) == ')') bal--;
i++;
if (bal == 0) break;
}
tokens.add(expr.substring(j, i));
} else if (expr.charAt(i) != ' ') {
int j = i;
while (i < n && expr.charAt(i) != ' ') i++;
tokens.add(expr.substring(j, i));
} else {
i++;
}
}
return tokens;
}
private int eval(String expr, List<Map<String, Integer>> env) {
if (expr.charAt(0) != '(') {
if (Character.isDigit(expr.charAt(0)) || expr.charAt(0) == '-') {
return Integer.parseInt(expr);
}
for (int i = env.size() - 1; i >= 0; --i) {
if (env.get(i).containsKey(expr)) return env.get(i).get(expr);
}
throw new RuntimeException("Variable not found");
}
String inner = expr.substring(1, expr.length() - 1);
List<String> tokens = parse(inner);
if (tokens.get(0).equals("add")) {
return eval(tokens.get(1), env) + eval(tokens.get(2), env);
} else if (tokens.get(0).equals("mult")) {
return eval(tokens.get(1), env) * eval(tokens.get(2), env);
} else if (tokens.get(0).equals("let")) {
List<Map<String, Integer>> newEnv = new ArrayList<>(env);
newEnv.add(new HashMap<>());
int i = 1;
while (i < tokens.size() - 1) {
String var = tokens.get(i);
int val = eval(tokens.get(i + 1), newEnv);
newEnv.get(newEnv.size() - 1).put(var, val);
i += 2;
}
return eval(tokens.get(tokens.size() - 1), newEnv);
}
return 0;
}
}
var evaluate = function(expression) {
function parse(expr) {
let tokens = [], i = 0, n = expr.length;
while (i < n) {
if (expr[i] === '(') {
let bal = 0, j = i;
while (i < n) {
if (expr[i] === '(') bal++;
if (expr[i] === ')') bal--;
i++;
if (bal === 0) break;
}
tokens.push(expr.slice(j, i));
} else if (expr[i] !== ' ') {
let j = i;
while (i < n && expr[i] !== ' ') i++;
tokens.push(expr.slice(j, i));
} else {
i++;
}
}
return tokens;
}
function evalExpr(expr, env) {
if (expr[0] !== '(') {
if (/^-?\d+$/.test(expr)) return parseInt(expr);
for (let i = env.length - 1; i >= 0; i--) {
if (expr in env[i]) return env[i][expr];
}
throw new Error("Variable not found");
}
expr = expr.slice(1, -1);
let tokens = parse(expr);
if (tokens[0] === 'add') {
return evalExpr(tokens[1], env) + evalExpr(tokens[2], env);
} else if (tokens[0] === 'mult') {
return evalExpr(tokens[1], env) * evalExpr(tokens[2], env);
} else if (tokens[0] === 'let') {
let newEnv = env.slice();
newEnv.push({});
let i = 1;
while (i < tokens.length - 1) {
let v = tokens[i];
let val = evalExpr(tokens[i+1], newEnv);
newEnv[newEnv.length - 1][v] = val;
i += 2;
}
return evalExpr(tokens[tokens.length - 1], newEnv);
}
}
return evalExpr(expression, []);
};