Sign in to watch this lesson
Algorithms - Strings · 4:22
Expression Parsing
Reverse Polish notation puts every operator after its operands, so one stack evaluates it in a single pass. The two-stack parser (Dijkstra's shunting yard) turns ordinary infix into that order with one rule: before pushing an operator, fire every stacked operator of equal or higher priority, with parentheses acting as walls. We run it on a + b * c * d + (e - f) * (g * h + i), then add right associativity for powers and unary minus, and finish with the compile-once, evaluate-every-tick pattern used for risk rules.
You will learn
- Evaluate an expression in reverse Polish notation with one stack in O(n)
- Parse infix with two stacks: fire stacked operators of priority >= the incoming one, treat parentheses as walls, flush at the end
- Handle right-associative operators (fire only on strictly higher priority) and unary minus (detected by may_be_unary)
- Compile a rule to RPN once and evaluate it per tick without allocation, guarding against multi-digit parsing slips, division by zero and overflow