INFIX, POSTFIX, AND PREFIX

INFIX
POSTFIX
PREFIX

A major application that illustrates the different types of stacks and the various operations and functions defined upon them.

A + B à Infix
+ AB à prefix
AB+ à postfix

A + (B * C)
A + (BC*)
A(BC*)+
ABC * +

The following is the order of precedence (highest to lowest)

Exponentiation

Multiplication / division
Addition / subtraction

Infix

A+B
A + B – C
(A+B) * (C – D)
A $ B * C – D + E / F / (G + H)

postfix

AB+
AB + C –
AB+ CD- *
AB$C*D-EF / GH + / +

Prefix

+AB
- + ABC
* + AB – CD
+ - * $ ABCD / / EF + GH


Evaluating a postfix Expression

Algorithm:

Opndstk = the empty stack;
While ( not end of input)
{
Symb = next input character;
If ( symb is an operator)
Push(opndstk, symb);
Else
{
Opnd2 = pop(opndstk);
Opnd1 = pop(opndstk);
Value = result of applying symb to opnd1 and opnd2;
Push(opndstk, value);
}
}
Return(pop(opndstk));


Example:

6 2 3 + - 3 8 2 / + * 2 $ 3 +