Expression notation specifies how operators and operands are arranged to encode a mathematical computation. Infix notation places an operator between operands, as in ; Polish notation places it first, and reverse Polish notation places it last.
The computation can be written in prefix form as
* + a b c or postfix form as a b + c *. Known operator arities make these forms parse without parentheses. Infix notation instead uses parentheses and precedence conventions to distinguish this expression from . All three can describe the same abstract syntax tree.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.
Articles by others on the same topic
There are currently no matching articles.