Expression notation

Place each operator after its operands. A binary application encodes its first subtree, then its second subtree, then the operator, a postorder traversal. A stack machine evaluates the tokens in one pass, popping the right operand before the left one. Reversing a Polish notation token list also reverses operand order: prefix subtraction - a b would become b a - rather than the required a b -.

Place each operator before its operands. With known operator arities and unambiguous tokens, the abstract syntax tree is recovered recursively without precedence rules or parentheses. A binary application is encoded by its operator, the first subtree's encoding and the second subtree's encoding: this is a preorder traversal of the expression tree.