Parse Lisp Expression - Practice Coding Problems

Parse Lisp Expression - Problem

You are given a string expression representing a Lisp-like expression. Your task is to return the integer value after evaluating this expression.

Expression Types:

Integer: A positive or negative integer
Variable: A string starting with lowercase letter, followed by lowercase letters or digits
Let Expression: (let v1 e1 v2 e2 ... vn en expr) - assigns variables sequentially, then evaluates expr
Add Expression: (add e1 e2) - returns sum of two expressions
Mult Expression: (mult e1 e2) - returns product of two expressions

Scoping Rules: Variables are resolved from innermost to outermost scope. The names add, let, and mult are reserved and will never be used as variable names.

Input & Output

Example 1 — Let Expression

$ Input: expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"

› Output: 14

💡 Note: Outer scope: x=2. Inner scope: x=3, y=4. Inner expression: add(3,4)=7. Outer expression: mult(2,7)=14.

Example 2 — Nested Add

$ Input: expression = "(add 1 (mult 2 3))"

› Output: 7

💡 Note: First evaluate mult(2,3)=6, then add(1,6)=7.

Example 3 — Variable Scoping

$ Input: expression = "(let x 3 x 2 x)"

› Output: 2

💡 Note: Variable x is reassigned: first x=3, then x=2. Final expression evaluates x which is 2.

Constraints

1 ≤ expression.length ≤ 2000
The expression is syntactically correct
All integers are within the 32-bit signed integer range

Visualization

Tap to expand

Understanding the Visualization

Input

Nested Lisp expression with variables and operations

Parse

Recursive parsing with variable scope management

Output

Final integer result after evaluation

Key Takeaway

🎯 Key Insight: Use recursive parsing to naturally handle nested structure and variable scoping

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is to use recursive parsing to naturally handle nested expressions and maintain variable scoping. The recursive approach with scope passing provides the cleanest solution. Time: O(n), Space: O(d) where d is nesting depth.

Common Approaches

Approach	Time	Space	Notes
✓ String Parsing with Stack	O(n)	O(n)	Parse expression character by character using stack for nested structures
Recursive Parsing with Stack	O(n)	O(d)	Use recursion to handle nested expressions naturally with implicit call stack

String Parsing with Stack — Algorithm Steps

Scan string character by character
Use stack to track parentheses and tokens
Manually handle each expression type
Maintain variable scope with nested maps

Visualization

Tap to expand

Step-by-Step Walkthrough

Tokenize

Split expression into tokens

Process Stack

Handle nested expressions with stack

Evaluate

Calculate result with variable scoping

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_TOKENS 1000
#define MAX_VARS 100

typedef struct {
    char name[50];
    int value;
} Variable;

typedef struct {
    Variable vars[MAX_VARS];
    int count;
} Scope;

char tokens[MAX_TOKENS][50];
int tokenCount = 0;
int tokenIndex = 0;

void tokenize(char* expr) {
    int i = 0, j = 0;
    tokenCount = 0;
    
    while (expr[i]) {
        if (expr[i] == ' ') {
            i++;
        } else if (expr[i] == '(' || expr[i] == ')') {
            tokens[tokenCount][0] = expr[i];
            tokens[tokenCount][1] = '\0';
            tokenCount++;
            i++;
        } else {
            j = 0;
            while (expr[i] && expr[i] != '(' && expr[i] != ')' && expr[i] != ' ') {
                tokens[tokenCount][j++] = expr[i++];
            }
            tokens[tokenCount][j] = '\0';
            tokenCount++;
        }
    }
}

int getValue(char* token, Scope* scope) {
    if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1]))) {
        return atoi(token);
    }
    for (int i = scope->count - 1; i >= 0; i--) {
        if (strcmp(scope->vars[i].name, token) == 0) {
            return scope->vars[i].value;
        }
    }
    return 0;
}

int evaluate(Scope* scope);

int evaluateSingle(Scope* scope) {
    if (strcmp(tokens[tokenIndex], "(") == 0) {
        return evaluate(scope);
    } else {
        return getValue(tokens[tokenIndex++], scope);
    }
}

int evaluate(Scope* scope) {
    if (tokenIndex >= tokenCount) return 0;
    
    if (strcmp(tokens[tokenIndex], "(") == 0) {
        tokenIndex++; // skip '('
        char* op = tokens[tokenIndex++];
        
        if (strcmp(op, "let") == 0) {
            Scope newScope = *scope;
            while (tokenIndex < tokenCount - 1 && strcmp(tokens[tokenIndex], ")") != 0) {
                if (tokenIndex >= tokenCount - 2) break;
                char* var = tokens[tokenIndex++];
                int val = evaluateSingle(&newScope);
                strcpy(newScope.vars[newScope.count].name, var);
                newScope.vars[newScope.count].value = val;
                newScope.count++;
            }
            int result = evaluateSingle(&newScope);
            tokenIndex++; // skip ')'
            return result;
        } else if (strcmp(op, "add") == 0) {
            int val1 = evaluateSingle(scope);
            int val2 = evaluateSingle(scope);
            tokenIndex++; // skip ')'
            return val1 + val2;
        } else if (strcmp(op, "mult") == 0) {
            int val1 = evaluateSingle(scope);
            int val2 = evaluateSingle(scope);
            tokenIndex++; // skip ')'
            return val1 * val2;
        }
    }
    return getValue(tokens[tokenIndex++], scope);
}

int solution(char* expression) {
    tokenize(expression);
    tokenIndex = 0;
    Scope scope;
    scope.count = 0;
    return evaluate(&scope);
}

int main() {
    char expression[1000];
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = 0;
    printf("%d\n", solution(expression));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through expression string of length n

✓ Linear Growth

Space Complexity

O(n)

Stack and variable maps store up to n tokens and variables

⚡ Linearithmic Space

18.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

String Parsing with Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler