Evaluating the AST

Tree-Walk Interpretation

We have tokens and a parse tree. Now let's evaluate it! A tree-walk interpreter recursively visits each node and computes its value.

The Evaluate Function

function evaluate(node) {
    if (node.type === "NumberLiteral") {
        return node.value;
    }
    if (node.type === "BinaryExpr") {
        const left = evaluate(node.left);
        const right = evaluate(node.right);
        if (node.op === "+") return left + right;
        if (node.op === "-") return left - right;
        if (node.op === "*") return left * right;
        if (node.op === "/") return left / right;
    }
}

That's it! The recursion follows the tree structure naturally:

• For (+ 2 (* 3 4)): evaluate left (2), evaluate right (* 3 4 = 12), add = 14

Putting It All Together

Now we have the full pipeline:

source code  ->  tokenize  ->  parse  ->  evaluate  ->  result
  "2+3*4"      [tokens...]     AST        14

Your Task

Combine the tokenizer, parser, and evaluator into a single interpret(input) function. It should return the numeric result of evaluating the expression.