Expression Evaluator with Recursive Descent Parser

Project roadmap

1. 01

   Write the tokenizer

   ~1.5h

   Define a Token struct with a type (number, name, plus, minus, star, slash, caret, left and right parenthesis, equals, end) and its position in the input. Write a tokenizer that skips spaces, reads numbers (including decimals such as 3.14) and names, and throws an error with the position for unknown characters. Done when: unit tests show 2*(x+3.5) becomes the right list of tokens.

2. 02

   Define the tree nodes

   ~1h

   Define AST node types: Number, Variable, Unary (negation), Binary (an operator with left and right children) and Assign, with an abstract Node class and std::unique_ptr for children, so memory is freed automatically. Add a to_string method that prints a node fully parenthesized, useful for checking the tree. Done when: you can build a small tree by hand and print it.

3. 03

   Write the recursive descent parser

   ~2.5h

   Write down the grammar first: expression = term { (+|-) term }, term = power { (*|/) power }, power = unary [ ^ power ] (right-associative), unary = - unary | primary, primary = number | name | ( expression ). Write one function per rule that builds nodes, plus assignment (name = expression) at the top. Report errors such as a missing ) with the position. Done when: 2+3*4 parses as 2+(3*4), and 2^3^2 as 2^(3^2).

4. 04

   Evaluate the tree

   ~1.5h

   Write an evaluate function (a virtual method or a visitor) that computes each node's value recursively. Throw clear errors for division by zero and unknown variables. Done when: evaluating test expressions gives the correct results, and 1/0 gives a clear error.

5. 05

   Add variables and a prompt

   ~1.5h

   Keep variables in a std::unordered_map (a symbol table). Assignments store a value and print it; later expressions can use it. Build a prompt loop that reads lines, prints results or errors (with a ^ marker under the error position), and supports commands such as vars and quit. Done when: x = 5 followed by 2 * x prints 10, and errors show where the problem is.

6. 06

   Test it

   ~1.5h

   Write tests (with a small framework such as doctest, or plain assert) for tokenizing, precedence and associativity, parentheses, unary minus (such as -2^2), variables, and errors (unbalanced parentheses, a trailing operator, unknown variables, and division by zero). Done when: all tests pass.

Resources

• DocsCrafting Interpreters: parsing expressions (free book)
• ArticleRecursive descent parser (Wikipedia)
• Docsstd::unique_ptr (cppreference)
• DocsLearn C++: virtual functions