Mathematical Notations
In math, an expression is a group of symbols. Together they show a quantity or a relation.
- Prefix Notation (Polish Notation) - The operator precedes their operands. Example: + A B (which means A + B)
- Infix Notation - The operator is in between their operands. Example: A + B
- Postfix Notation (Reverse Polish Notation) - The operator follows their operands. Example: A B + (which means A + B)
This is the most intuitive, human-readable form. It mirrors how we write math by hand. It needs parentheses, though, to set operator precedence.
Relation to Computers
For programming languages, parsing infix notation is complex. It must also know operator precedence and associativity rules. Compilers convert infix to prefix or postfix notation. A stack can then evaluate these with no parentheses.
For example, take A + B - C in infix notation. In postfix it becomes A B C - +. In prefix it becomes + A - B C.
To read postfix or prefix, just run the operations in order. Run each operation on the next two operands you see.
In programming languages, the tree is built first. Then operands are pushed onto a stack. When an operator shows up, the needed operands are popped. The operation runs. The result is pushed back.
In this example, the stack holds A, B, C in that order. Then the - operator shows up. B and C are popped. B - C is computed and pushed back. Then the + operator shows up. A and (B - C) are popped. A + (B - C) is computed and pushed back.
Now the computer can evaluate the expression with ease.
In programming languages like Java, the expression is first parsed into an expression tree. You can walk the tree in different orders to get different notations. Usually postfix, so the whole expression can go onto a stack.
