1. The Problem
Build an interpreter for arithmetic expressions like 2 + 3 * 4 that respects precedence (multiplication before addition) and parentheses. Three stages: tokenize the text, parse it into structure, and evaluate the result — here fused into a recursive-descent evaluator.
Why this project? Tokenize → parse → evaluate is how every programming language works. A calculator is the smallest complete example, and recursive descent is the parsing technique used in real compilers.
2. How to Think About This
Tokenizing turns "2 + 3" into [NUM 2, +, NUM 3] with a regex. Precedence falls out of the grammar structure: expr handles +/- (lowest), calls term for *// (higher), which calls factor for numbers and parenthesised sub-expressions (highest). Because factor can call expr again for a (, parentheses and nesting just work.
3. The Build
// ---- 1. TOKENIZE: text -> list of tokens ----
export function tokenize(text) {
const tokens = [];
for (const part of text.match(/\d+|[+\-*/()]/g) || []) {
if (/^\d+$/.test(part)) tokens.push(["NUM", parseInt(part, 10)]);
else tokens.push([part, part]);
}
return tokens;
}
// ---- 2 & 3. PARSE + EVALUATE (recursive descent) ----
class Parser {
constructor(tokens) { this.tokens = tokens; this.pos = 0; }
peek() { return this.pos < this.tokens.length ? this.tokens[this.pos] : [null, null]; }
eat() { return this.tokens[this.pos++]; }
expr() { // + and - (lowest precedence)
let value = this.term();
while (this.peek()[0] === "+" || this.peek()[0] === "-") {
const op = this.eat()[0];
const right = this.term();
value = op === "+" ? value + right : value - right;
}
return value;
}
term() { // * and / (higher precedence)
let value = this.factor();
while (this.peek()[0] === "*" || this.peek()[0] === "/") {
const op = this.eat()[0];
const right = this.factor();
value = op === "*" ? value * right : value / right;
}
return value;
}
factor() { // numbers and parentheses (highest)
const [type, value] = this.eat();
if (type === "NUM") return value;
if (type === "(") {
const inner = this.expr();
this.eat(); // consume ")"
return inner;
}
}
}
export function evaluate(text) {
return new Parser(tokenize(text)).expr();
}
// Demo
console.log(evaluate("2 + 3 * 4")); // 14, not 20
console.log(evaluate("(2 + 3) * 4")); // 204. Test & Prove
import { evaluate, tokenize } from "./interpret.mjs";
let pass = 0, fail = 0;
function test(desc, fn) {
try { fn(); console.log(" \u2713", desc); pass++; }
catch (e) { console.log(" \u2717", desc, "\u2014", e.message); fail++; }
}
function assert(cond, msg) { if (!cond) throw new Error(msg || "assertion failed"); }
test("adds two numbers", () => assert(evaluate("2 + 3") === 5));
test("respects precedence (* before +)", () => assert(evaluate("2 + 3 * 4") === 14));
test("parentheses override precedence", () => assert(evaluate("(2 + 3) * 4") === 20));
test("handles subtraction and division", () => assert(evaluate("20 - 8 / 2") === 16));
test("nested parentheses work", () => assert(evaluate("((1 + 2) * (3 + 4))") === 21));
test("tokenize splits numbers and operators", () => {
assert(JSON.stringify(tokenize("2+3")) === JSON.stringify([["NUM",2],["+","+"],["NUM",3]]));
});
console.log(`\n${pass} passed, ${fail} failed`);5. The Interface
node interpret.mjs 14 20
6. Run It
node interpret.mjs
node interpret.test.mjs🎯 Try this next
- Add support for negative numbers and unary minus
- Add variables: let x = 5, then evaluate expressions using x
- Return the parse tree (AST) instead of a number, then evaluate it separately
- Add exponentiation (^) with right-associative precedence