Skip to content

README.md

Latest commit

 

History

History
86 lines (69 loc) · 3.16 KB

README.md

File metadata and controls

86 lines (69 loc) · 3.16 KB
Raw

Lab 07 — RPN Expression Parser and AST

Goal

Parse a Reverse Polish Notation (RPN) arithmetic expression into an abstract syntax tree, then evaluate it, print it, and simplify it.

Description

Expression is the AST node interface: eval(ctx) computes the numeric value given a variable-name-to-value Context, toString() renders the subtree, clone() deep-copies it, and simplify() returns an equivalent, possibly-smaller tree.

Node types:

  • Constant — a literal number, no children.
  • Variable — a name, resolved through the Context at eval time.
  • BinaryOperator — + - * /, with a left and right child.
  • UnaryMinus — negation of a single child, kept as its own node type rather than folded into subtraction (see below for why).

ExpressionParser::parseRPN tokenizes a space-separated RPN string (each token is a number, an identifier, or an operator) and builds the tree with a stack: operands get pushed, and each operator pops its arguments off the stack and pushes the resulting node back on. After processing every token, exactly one node — the root — remains on the stack.

RPN normally can't distinguish binary subtraction from unary negation using only - (e.g. 5 - (-3) naively becomes 5 3 - -, which evaluates to -2 instead of 8). This parser sidesteps the ambiguity by using a separate token, ~, for negation — chosen because it can't collide with a variable name the way a letter or _ could.

simplify() on BinaryOperator/UnaryMinus does two things:

  1. Constant folding — if both operands simplify down to variable-free subtrees, evaluate once and replace the whole node with a Constant.
  2. Algebraic identities — x + 0, 0 + x, x - 0, 0 - x -> -x, x * 0, 0 * x, x * 1, 1 * x, x / 1, applied even when x isn't a plain variable but an unsimplified subtree. x / x -> 1 is deliberately not attempted, since it would require checking that the two subtrees are structurally identical and can't evaluate to zero.

Whether a subtree is "free of variables" is checked by calling eval({}) (an empty context) and seeing whether it throws — Variable::eval throws via std::map::at when its name isn't bound.

Project structure

├── include/Expression.h
├── include/ExpressionParser.h
├── src/Expression.cpp
├── src/ExpressionParser.cpp
└── src/main.cpp

Requirements

  1. The program must compile without errors or warnings (-Wall -Wextra -Wpedantic).
  2. The parser must handle numbers, variables, + - * /, and unary ~ in RPN form, all tokens separated by single spaces.
  3. simplify() must not mutate the original tree — it returns a new one.

Expected output

expr1 = (2 + 3) * 4 -> ((2 + 3) * 4)
expr2 = (x + 2) * x -> ((x + 2) * x)
expr3 = 5 + ((1 + 2) * 4) - 3 -> ((5 + ((1 + 2) * 4)) - 3)
expr4 = -x -> (-x)
expr4(x = 3) = -3? -3
expr5 = -(x + 2) -> (-(x + 2))
expr5(x = 3) = -(3 + 2) = -5? -5
((2 + 5) + 3) -> (10?) : 10
((2 + 5) + 3) * x ->  (10 * x?) : (10 * x)
x + 0 -> x (x?)
0 + x -> x (x?)
x * 0 -> 0 (0?)
x * 1 -> x (x?)
1 * x -> x (x?)
x / 1 -> x (x?)
0 - x -> (-x) (-x?)
((2 + 3) + 0) * x * 1 ->  (5 * x?) : (5 * x)