A * ( B + C ) / Dis usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."
Infix notation needs extra information to make the order of evaluation of the
operators clear: rules built into the language about operator precedence and
associativity, and brackets
( ) to allow users to override
these rules. For example, the usual rules for associativity say that we
perform operations from left to right, so the multiplication by A is assumed
to come before the division by D. Similarly, the usual rules for precedence
say that we perform multiplication and division before we perform addition and
(see CS2121 lecture).
A B C + * D /
( (A (B C +) *) D /)
/ * A + B C D
(/ (* A (+ B C) ) D)
Although Prefix "operators are evaluated left-to-right", they use values to
their right, and if these values themselves involve computations then this
changes the order that the operators have to be evaluated in. In the example
above, although the division is the first operator on the left, it acts on the
result of the multiplication, and so the multiplication has to happen before
the division (and similarly the addition has to happen before the
Because Postfix operators use values to their left, any values involving computations will already have been calculated as we go left-to-right, and so the order of evaluation of the operators is not disrupted in the same way as in Prefix expressions.
In all three versions, the operands occur in the same order, and just the
operators have to be moved to keep the meaning correct. (This is particularly
important for asymmetric operators like subtraction and division:
A - B does not mean the same as
B - A; the former is equivalent to
A B - or
- A B, the latter to
B A - or
- B A).
|multiply A and B,|
divide C by D,
add the results
|add B and C,|
multiply by A,
divide by D
|divide C by D,|
multiply by A
(X + Y)or
(X Y +)or
(+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.
You can use a similar trick to convert to and from parse trees - each bracketed 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)))
Although Postfix and Prefix notations have similar complexity, Postfix is slightly easier to evaluate in simple circumstances, such as in some calculators (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, see my CS2111 lectures.