Week 20: Capstone — Build a Mini Expression Interpreter

1. Project Scope & Grammar

Before writing a tokenizer or a parser, write down exactly what your interpreter accepts — an interpreter with an undefined grammar has no way to say a given input is invalid, only ways to fail unpredictably on it. A well-scoped mini interpreter for this capstone supports:

Integer and decimal number literals (3, 4.5)
The four binary operators +, -, *, /, with standard precedence (*// bind tighter than +/-)
Parentheses for explicit grouping, e.g. (2 + 3) * 4
Unary minus, e.g. -(3 + 4)

Writing that grammar as a small set of production rules up front is what makes the rest of the build mechanical instead of guesswork — every rule below maps directly onto one function in Section 3's parser:

grammar.txt

expression := term (('+' | '-') term)*
term       := factor (('*' | '/') factor)*
factor     := NUMBER
            | '(' expression ')'
            | '-' factor

Notice the grammar is structured in layers — expression is built from terms, and term is built from factors. That layering is precedence encoded directly into the grammar: because term (multiplication/division) sits "closer" to the leaves than expression (addition/subtraction), a recursive-descent parser built from these rules will always group * and / tighter than + and - without any extra precedence-tracking logic.

2. The Tokenizer

The tokenizer's job is narrow on purpose: turn a raw std::string into a flat sequence of typed tokens, and reject anything that isn't a number, operator, or parenthesis. Nothing about precedence or grouping happens here — that's the parser's job in Section 3. Keeping the tokenizer this dumb is what makes it easy to get completely correct.

token.hpp

#include <string>
#include <vector>
#include <stdexcept>
#include <cctype>
using namespace std;

enum class TokenType { NUMBER, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, END };

struct Token {
    TokenType type;
    double value;   // only meaningful when type == NUMBER
};

vector<Token> tokenize(const string& src) {
    vector<Token> tokens;
    size_t i = 0;

    while (i < src.size()) {
        char c = src[i];

        if (isspace(static_cast<unsigned char>(c))) { i++; continue; }

        if (isdigit(static_cast<unsigned char>(c)) || c == '.') {
            size_t start = i;
            while (i < src.size() &&
                   (isdigit(static_cast<unsigned char>(src[i])) || src[i] == '.')) i++;
            tokens.push_back({TokenType::NUMBER, stod(src.substr(start, i - start))});
            continue;
        }

        switch (c) {
            case '+': tokens.push_back({TokenType::PLUS, 0});   break;
            case '-': tokens.push_back({TokenType::MINUS, 0});  break;
            case '*': tokens.push_back({TokenType::STAR, 0});   break;
            case '/': tokens.push_back({TokenType::SLASH, 0});  break;
            case '(': tokens.push_back({TokenType::LPAREN, 0}); break;
            case ')': tokens.push_back({TokenType::RPAREN, 0}); break;
            default:
                throw runtime_error(string("Unexpected character: '") + c + "'");
        }
        i++;
    }

    tokens.push_back({TokenType::END, 0});   // sentinel -- lets the parser peek safely
    return tokens;
}

Why an END sentinel

Without a terminating token, every "what's the next token?" check in the parser would need a separate bounds check against tokens.size(). Appending an explicit END token means the parser can always safely call peek() — the same trick as a sentinel node in a linked list, or the null terminator at the end of a C string.

3. Expression Tree & Recursive-Descent Parser

The expression tree is a binary tree exactly like the ones from Weeks 9–10: an internal node holds an operator and two children, a leaf holds a number. Evaluating 3 + 4 * 2 correctly means the tree must group 4 * 2 as one subtree before it's added to 3 — which is exactly what the grammar from Section 1 guarantees when translated directly into functions:

ast.hpp

#include <memory>
using namespace std;

struct Node {
    TokenType op;                 // meaningful only for internal (non-leaf) nodes
    double value = 0;             // meaningful only for leaf nodes
    bool isLeaf = false;
    unique_ptr<Node> left, right;
};

unique_ptr<Node> makeLeaf(double v) {
    auto n = make_unique<Node>();
    n->isLeaf = true;
    n->value = v;
    return n;
}

unique_ptr<Node> makeBinary(TokenType op, unique_ptr<Node> l, unique_ptr<Node> r) {
    auto n = make_unique<Node>();
    n->op = op;
    n->left = move(l);
    n->right = move(r);
    return n;
}

unique_ptr gives the tree the ownership semantics it needs for free — each node owns its children outright, and the whole tree is freed automatically when its root goes out of scope, with no manual delete anywhere in the parser or evaluator.

The parser itself is recursive descent: one function per grammar rule from Section 1, each calling the next one down and combining the result. This is the same "trust the recursive call to solve the smaller problem" discipline from Week 8 — parseExpression doesn't know how parseTerm handles multiplication, it just trusts it to return a correct subtree:

parser.hpp

class Parser {
public:
    explicit Parser(vector<Token> toks) : tokens(move(toks)), pos(0) {}

    unique_ptr<Node> parseExpression() {
        auto node = parseTerm();
        while (peek().type == TokenType::PLUS || peek().type == TokenType::MINUS) {
            TokenType op = advance().type;
            node = makeBinary(op, move(node), parseTerm());
        }
        return node;
    }

private:
    vector<Token> tokens;
    size_t pos;

    const Token& peek() const { return tokens[pos]; }
    Token advance() { return tokens[pos++]; }

    unique_ptr<Node> parseTerm() {
        auto node = parseFactor();
        while (peek().type == TokenType::STAR || peek().type == TokenType::SLASH) {
            TokenType op = advance().type;
            node = makeBinary(op, move(node), parseFactor());
        }
        return node;
    }

    unique_ptr<Node> parseFactor() {
        if (peek().type == TokenType::NUMBER) {
            return makeLeaf(advance().value);
        }
        if (peek().type == TokenType::MINUS) {          // unary minus
            advance();
            return makeBinary(TokenType::MINUS, makeLeaf(0), parseFactor());
        }
        if (peek().type == TokenType::LPAREN) {
            advance();                                    // consume '('
            auto node = parseExpression();
            if (peek().type != TokenType::RPAREN)
                throw runtime_error("Expected ')'");
            advance();                                    // consume ')'
            return node;
        }
        throw runtime_error("Unexpected token while parsing expression");
    }
};

Trace 3 + 4 * 2 through this: parseExpression calls parseTerm, which calls parseFactor and returns the leaf 3 (no *// follows, so parseTerm returns immediately). Back in parseExpression, the next token is +, so it consumes it and calls parseTerm again — that call parses 4, sees *, and folds in 2 before returning the 4 * 2 subtree. parseExpression then combines 3 and that subtree under +, giving exactly the tree 3 + (4 * 2) that correct precedence requires.

The grammar layering IS the precedence

Nowhere in this parser is there an if-statement checking "is * higher precedence than +?" The precedence is entirely a consequence of which function calls which: parseTerm is only ever called from inside parseExpression or by itself, so *// subtrees are always fully built before a +/- node can wrap them.

4. An Alternative: Two-Stack Evaluation

Section 3's recursive-descent parser is the cleanest way to get a reusable expression tree. But you can also evaluate an expression directly, without ever building a tree, using two stacks — one for pending values, one for pending operators. This is the same monotonic-stack instinct from Week 7 applied to arithmetic: keep popping and resolving the stack as long as doing so is unambiguous, and push when it isn't yet.

stack_eval.hpp

#include <stack>
using namespace std;

int precedence(TokenType op) {
    if (op == TokenType::PLUS || op == TokenType::MINUS) return 1;
    if (op == TokenType::STAR || op == TokenType::SLASH) return 2;
    return 0;
}

double applyOp(double a, double b, TokenType op) {
    switch (op) {
        case TokenType::PLUS:  return a + b;
        case TokenType::MINUS: return a - b;
        case TokenType::STAR:  return a * b;
        case TokenType::SLASH:
            if (b == 0) throw runtime_error("Division by zero");
            return a / b;
        default:
            throw runtime_error("Unknown operator");
    }
}

double evaluateWithStacks(const vector<Token>& tokens) {
    stack<double> values;
    stack<TokenType> ops;

    auto reduceOnce = [&]() {
        TokenType op = ops.top(); ops.pop();
        double b = values.top(); values.pop();
        double a = values.top(); values.pop();
        values.push(applyOp(a, b, op));
    };

    for (const Token& tok : tokens) {
        if (tok.type == TokenType::NUMBER) {
            values.push(tok.value);
        } else if (tok.type == TokenType::LPAREN) {
            ops.push(tok.type);
        } else if (tok.type == TokenType::RPAREN) {
            while (!ops.empty() && ops.top() != TokenType::LPAREN) reduceOnce();
            ops.pop();                          // discard the matching '('
        } else if (tok.type == TokenType::END) {
            break;
        } else {                                 // PLUS, MINUS, STAR or SLASH
            while (!ops.empty() && ops.top() != TokenType::LPAREN &&
                   precedence(ops.top()) >= precedence(tok.type)) {
                reduceOnce();
            }
            ops.push(tok.type);
        }
    }
    while (!ops.empty()) reduceOnce();
    return values.top();
}

The key rule is the while loop before pushing a new operator: it reduces every pending operator on the stack that has equal or higher precedence than the incoming one before pushing. That's what makes 4 * 2 + 1 reduce 4 * 2 the moment + arrives (lower precedence, so the multiplication must resolve first), while 4 + 2 * 1 instead pushes both operators and waits, because * has strictly higher precedence than the + already on the stack.

Tree vs. direct evaluation — when to use which

Direct stack evaluation is leaner when you only ever need the final number once. Building a tree costs more memory and code, but pays off the moment you need the expression more than once — evaluate it with different variable values, simplify it symbolically, or pretty-print it back out — because the tree is a reusable structure and a stack evaluation's result is just a number with no memory of how it was produced.

5. Evaluating the Tree & Handling Errors

Evaluating the expression tree from Section 3 is a two-line recursive function — the same "solve the leaves, combine going back up" shape as every tree problem since Week 9:

evaluator.hpp

double evaluate(const Node* node) {
    if (node->isLeaf) return node->value;

    double l = evaluate(node->left.get());
    double r = evaluate(node->right.get());

    switch (node->op) {
        case TokenType::PLUS:  return l + r;
        case TokenType::MINUS: return l - r;
        case TokenType::STAR:  return l * r;
        case TokenType::SLASH:
            if (r == 0) throw runtime_error("Division by zero");
            return l / r;
        default:
            throw runtime_error("Unknown operator in tree");
    }
}

double interpret(const string& src) {
    auto tokens = tokenize(src);          // throws on an invalid character
    Parser parser(tokens);
    auto tree = parser.parseExpression(); // throws on a malformed expression
    return evaluate(tree.get());          // throws on e.g. division by zero
}

A mini interpreter is only as trustworthy as its error handling — an interpreter that silently returns 0 on "3 + / 4" is far more dangerous than one that throws, because a wrong-but-plausible answer is much harder to catch than a loud failure. Each of the three stages throws a specific runtime_error at the exact point it detects a problem: the tokenizer on an unrecognized character, the parser on a token that doesn't fit the grammar (like a missing closing paren), and the evaluator on a runtime failure like division by zero that no amount of valid syntax could have prevented.

main.cpp — driving it end to end

#include <iostream>
using namespace std;

int main() {
    vector<string> tests = {
        "3 + 4 * (2 - 1)",
        "-(3 + 4) / 2",
        "10 / 0",
        "3 + / 4"
    };

    for (const string& expr : tests) {
        try {
            cout << expr << " = " << interpret(expr) << "\n";
        } catch (const exception& e) {
            cout << expr << " -> error: " << e.what() << "\n";
        }
    }
}

6. The Capstone Project

Capstone

Build, test and extend a complete expression interpreter

Combine Sections 2–5 into one working program, then push past the minimum grammar with at least one real extension of your own.

Requirements:

Implement tokenize, the Node/expression-tree types, the recursive-descent Parser, and evaluate exactly as built in Sections 2, 3 and 5, in one buildable project.
Also implement evaluateWithStacks from Section 4, and write a small test harness that checks it agrees with the tree-based evaluate on at least 10 expressions, including nested parentheses.
Handle every error case explicitly with a test for each: an unknown character, a missing closing parenthesis, an expression ending mid-operator (e.g. "3 +"), and division by zero.
Pick one real extension and implement it fully: exponentiation (^, right-associative), named variables with a string → double environment map, or a modulo operator with integer-only semantics.
Write a short README explaining your grammar (updated for your extension), and note one input your interpreter still can't handle and why.

Why variables are the most instructive extension

Adding a variable lookup (x resolving to a value from an unordered_map<string, double>) forces the tokenizer to recognize identifiers alongside numbers, forces the grammar to add a new factor alternative, and forces the evaluator to take an environment argument — touching all three layers the way a real feature would in production code, which is exactly what makes it worth doing over a smaller change.

7. Final Checklist

Before calling the capstone — and the course — done, confirm each of these honestly:

✓

Was the grammar written down before the tokenizer and parser were built?

A grammar written after the parser exists just describes whatever the code happens to accept, including any accidental gaps. A grammar written first — like Section 1's production rules — gives you something independent to check the implementation against, and it's what let Section 3's parser be written mechanically, one function per rule, instead of guessed at.

✓

Do the tree-based evaluator and the two-stack evaluator agree on every test expression, including ones with nested parentheses?

Two independently-written implementations of the same grammar agreeing on every test is strong evidence both are correct, in the same way a brute-force solution cross-checked against an optimized one catches bugs that a single implementation's own tests would miss. If they disagree, nested parentheses and operator-precedence edge cases are the first place to look — they're where both implementations are most likely to have a subtle bug.

✓

Does every error case — bad character, unbalanced parens, trailing operator, division by zero — fail with a clear message instead of crashing or returning a wrong number?

An interpreter that segfaults or silently returns 0 on malformed input is broken in a way that's much harder to debug than one that throws a specific runtime_error naming exactly what went wrong and where. Section 5's explicit throw at each of the three stages — tokenizing, parsing, evaluating — is what makes every failure traceable to a specific cause instead of an undefined one.

✓

Was a real extension implemented fully, touching the tokenizer, grammar, and evaluator, rather than left as an idea in the README?

Building exactly the minimum from Sections 2–5 proves you can follow a spec; extending it — adding ^, variables, or modulo, and getting the grammar, tokenizer and evaluator to agree on the new rule — proves you understand the three layers well enough to change them without breaking what already worked. That's the difference a reviewer is actually looking for in a capstone.