- Infix notation: X + Y
- Operators are written in-between their operands.This is the usual way we write expressions.An expression such as
A*(B+C)/Dis usually taken to mean something like:"First add B and C together, then multiply the result by A, then divideby D to give the final answer."Infix notation needs extra information to make the order of evaluation of theoperators clear: rules built into the language about operator precedence andassociativity, and brackets
()to allow users to overridethese rules. For example, the usual rules for associativity say that weperform operations from left to right, so the multiplication by A is assumedto come before the division by D. Similarly, the usual rules for precedencesay that we perform multiplication and division before we perform addition andsubtraction.(see CS2121 lecture). - Postfix notation (also known as "Reverse Polish notation"): X Y +
- Operators are written after their operands. The infix expression given aboveis equivalent to
ABC+*D/
The order of evaluation of operators is always left-to-right, and bracketscannot be used to change this order. Because the "+" is to the left of the"*" in the example above, the addition must be performed before themultiplication.
Operators act on values immediately to the left of them. For example, the "+"above uses the "B" and "C". We can add (totally unnecessary) brackets to makethis explicit:( (A (B C +) *) D /)
Thus, the "*" uses the two values immediately preceding: "A", and the resultof the addition. Similarly, the "/" uses the result of the multiplicationand the "D". - Prefix notation (also known as "Polish notation"): + X Y
- Operators are written before their operands. The expressions given above areequivalent to
/*A+BCD
As for Postfix, operators are evaluated left-to-right and brackets aresuperfluous. Operators act on the two nearest values on the right. I haveagain added (totally unnecessary) brackets to make this clear:(/ (* A (+ B C) ) D)
In all three versions, the operands occur in the same order, and just theoperators have to be moved to keep the meaning correct. (This is particularlyimportant for asymmetric operators like subtraction and division:A-B does not mean the same asB-A; the former is equivalent toAB- or -AB, the latter toBA- or -BA).
Examples:
| Infix | Postfix | Prefix | Notes |
|---|---|---|---|
A*B+C/D | AB*CD/+ | +*AB/CD | multiply A and B, divide C by D, add the results |
A*(B+C)/D | ABC+*D/ | /*A+BCD | add B and C, multiply by A, divide by D |
A*(B+C/D) | ABCD/+* | *A+B/CD | divide C by D, add B, multiply by A |
Converting between these notations
The most straightforward method is to start by inserting all the implicitbrackets that show the order of evaluation e.g.:| Infix | Postfix | Prefix |
|---|---|---|
( (A * B) + (C / D) ) | ( (A B *) (C D /) +) | (+ (* A B) (/ C D) ) |
((A * (B + C) ) / D) | ( (A (B C +) *) D /) | (/ (* A (+ B C) ) D) |
(A * (B + (C / D) ) ) | (A (B (C D /) +) *) | (* A (+ B (/ C D) ) ) |
(X+Y)or(XY+)or(+XY).Repeat this for all the operators in an expression, and finally remove anysuperfluous brackets.You can use a similar trick to convert to and from parse trees - eachbracketed triplet of an operator and its two operands (or sub-expressions)corresponds to a node of the tree. The corresponding parse trees are:
/ * + / \ / \ / \ * D A + / \ / \ / \ * / A + B / / \ / \ / \ / \ A B C D B C C D((A*B)+(C/D))((A*(B+C))/D) (A*(B+(C/D)))
Computer Languages
Because Infix is so common in mathematics, it is much easier to read, andso is used in most computer languages(e.g. a simple Infix calculator).However, Prefix is often used for operators that take a single operand(e.g. negation) and function calls.Although Postfix and Prefix notations have similar complexity, Postfix isslightly easier to evaluate in simple circ*mstances, such as in somecalculators (e.g. a simple Postfix calculator),as the operators really are evaluated strictly left-to-right(see note above).
For lots more information about notations for expressions, seemy CS2111 lectures.
