Expressions consists of two components namely operands and operators. Operators indicate the operation to be carried out on operands. There are two kinds of operators namely unary and binary. Unary operators require one operand to carry out the intended operation whereas binary operators requires two operands to carry out the intended operation. Most operators are binary.
There are three ways of representing expressions:
Examples:
| PREFIX | = A / * H + B1 B2 2 |
|---|---|
| INFIX | A = H * (B1 + B2) / 2 |
| POSTFIX | A H B1 B2 + * 2 / = |
| | |
| PREFIX | = M / * P i – 1 / ^ + 1 1 i t |
| INFIX | M = (P * i) / (1 – 1 / (1 + i) ^ t) |
| POSTFIX | M P i * 1 1 1 i + t ^ / – / = |
Regardless of the notation, an expression can be represented by a binary tree as follows:
| PREFIX | operator operand operand |
|---|---|
| INFIX | operand operator operand |
| POSTFIX | operand operand operator |
Observation that the tree representation of an expression eliminates the need for parentheses.
Our world is accustomed to infix notation. However, algorithmically, postfix notation are easier to evaluate than infix notation. Hence, what is of interest to us is the conversion from infix to postfix notation.
Conversion from infix to postfix can be achieved by the use of three stacks namely:
The following illustrates the evaluation of a postfix notation.
Problems: