Interpreters

Reverse Polish Notation is a convenient form for evaluating expressions. The infix notation can be converted into RPN using Dijkstra's Shunting yard algorithm.

RPN is a post-order traversal of an AST.

Expression: (1 + 2) * (3 + 4)

AST: Binary('*', Binary('+', 1, 2), Binary('+', 3, 4))

RPN: 1 2 + 3 4 + *

Links