Math Expression Evaluator — Design Document

Requirements Summary

• Language: Go
• Operators: +, -, *, / with parentheses
• Numbers: floating point (e.g. 3.14, 42, 0.5)
• Variables: none
• Interface: CLI REPL
• Error handling: print error message, continue REPL

Approaches Considered

1. Recursive-Descent with AST (chosen)

• Lexer → Parser → AST → Evaluator → REPL
• Clean separation: each stage is independently testable
• AST is a reusable intermediate representation
• Easy to extend (new operators, pretty-printing, optimization)
• Well-suited for 2 precedence levels + parentheses

2. Recursive-Descent with Direct Evaluation

• Parser evaluates inline — no AST
• Fewer types, less code
• Couples parsing and evaluation — harder to test, extend

3. Shunting-Yard Algorithm

• Converts to RPN then evaluates
• Good for many precedence levels; overkill here
• Harder to produce clear error messages

Decision: Approach 1. The AST adds minimal overhead but provides clean boundaries.

Architecture

Input string
    │
    ▼
 ┌───────┐
 │ Lexer │  string → []Token
 └───┬───┘
     │
     ▼
 ┌────────┐
 │ Parser │  []Token → AST (Node)
 └───┬────┘
     │
     ▼
 ┌───────────┐
 │ Evaluator │  Node → float64
 └───┬───────┘
     │
     ▼
 ┌──────┐
 │ REPL │  read line → eval → print result or error
 └──────┘

Component Interfaces

Token (data type)

package token

type Type int

const (
    Number Type = iota
    Plus        // +
    Minus       // -
    Star        // *
    Slash       // /
    LParen      // (
    RParen      // )
    EOF
)

type Token struct {
    Type    Type
    Literal string  // raw text, e.g. "3.14", "+"
    Pos     int     // position in input (for error messages)
}

Lexer

package lexer

// Tokenize converts an input string into a slice of tokens.
// Returns an error if the input contains invalid characters.
func Tokenize(input string) ([]token.Token, error)

AST (data types)

package ast

// Node is the interface all AST nodes implement.
type Node interface {
    node() // sealed marker method
}

// NumberLit represents a numeric literal.
type NumberLit struct {
    Value float64
}

// BinaryExpr represents a binary operation (e.g. 1 + 2).
type BinaryExpr struct {
    Op    token.Type  // Plus, Minus, Star, Slash
    Left  Node
    Right Node
}

Parser

package parser

// Parse converts a slice of tokens into an AST.
// Returns an error for malformed expressions (mismatched parens, etc.).
func Parse(tokens []token.Token) (ast.Node, error)

Grammar (recursive-descent):

expr   → term (('+' | '-') term)*
term   → factor (('*' | '/') factor)*
factor → NUMBER | '(' expr ')'

Evaluator

package evaluator

// Eval evaluates an AST node and returns the result.
// Returns an error on division by zero.
func Eval(node ast.Node) (float64, error)

REPL

package repl

// Run starts the read-eval-print loop, reading from r and writing to w.
func Run(r io.Reader, w io.Writer)

Package Layout

matheval/
├── cmd/
│   └── matheval/
│       └── main.go          # entry point, calls repl.Run
├── token/
│   └── token.go             # Token type and constants
├── lexer/
│   ├── lexer.go             # Tokenize function
│   └── lexer_test.go
├── ast/
│   └── ast.go               # AST node types
├── parser/
│   ├── parser.go            # Parse function
│   └── parser_test.go
├── evaluator/
│   ├── evaluator.go         # Eval function
│   └── evaluator_test.go
├── repl/
│   ├── repl.go              # REPL loop
│   └── repl_test.go
├── docs/
│   ├── design.md
│   └── plan.md
├── go.mod
└── README.md

Error Handling

• Lexer: returns error for invalid characters (e.g. @, #)
• Parser: returns error for syntax errors (unexpected token, mismatched parens)
• Evaluator: returns error for division by zero
• REPL: catches any error, prints it, prompts for next input

Key Design Decisions

1. Functional API over structs — Tokenize(), Parse(), Eval() are stateless functions. No need for struct receivers since there's no configuration or state to carry.
2. Sealed AST interface — unexported marker method prevents external implementations, keeping the node set closed.
3. Position tracking in tokens — enables precise error messages ("error at position 5").
4. REPL takes io.Reader/io.Writer — makes it testable without stdin/stdout.