Infix, Prefix, and Postfix Expressions:
For simplicity, we will consider algebraic expressions with binary operators +, –, *,
and / only.
Infix Notation:
Usual notation in constructing algebraic expression such that operator appears
between two operands; it is ambiguous and requires knowledge of operator hierarchy for
its evaluation. Parentheses can also be used to override operator hierarchy.
Prefix Notation:
A special notation in constructing algebraic expression such that operator appears
before its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Postfix Notation:
A special notation in constructing algebraic expression such that operator appears
after its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Example: The infix expression ((a–b)/c)*((d+e)–f) has the following postfix and prefix
expression.
Postfix: ab–c/de+f –*
Prefix: */–abc–+def
Evaluating Postfix Expression:
scan given postfix expression;
for each symbol in postfix
if operand
then push its value onto a stack S;
if operator
then { pop operand2;
pop operand1;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
1
, Evaluating Prefix Expression:
reverse given prefix expression;
scan the reversed prefix expression;
for each symbol in reversed prefix
if operand
then push its value onto a stack S;
if operator
then { pop operand1;
pop operand2;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
Infix to Postfix Conversion:
given a legal infix string;
create an initially empty postfix string;
create an initially empty operator stack S;
for each symbol ch in the infix string do
if ch is an operand
then
append it to the output postfix string;
else if ch == ‘(‘
then
push ch onto stack S;
else if S == ‘)’
then
pop and append operators to output string until the matching ‘(‘ is encountered;
// discard the two parentheses
else // ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) ≥ precedence(ch)
and top(S) != ‘(‘ do
pop operator;
append it to the postfix string;
end while;
push S
}
end for;
while operator stack is not empty do
pop operator;
append it to the postfix string;
endwhile;
2
For simplicity, we will consider algebraic expressions with binary operators +, –, *,
and / only.
Infix Notation:
Usual notation in constructing algebraic expression such that operator appears
between two operands; it is ambiguous and requires knowledge of operator hierarchy for
its evaluation. Parentheses can also be used to override operator hierarchy.
Prefix Notation:
A special notation in constructing algebraic expression such that operator appears
before its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Postfix Notation:
A special notation in constructing algebraic expression such that operator appears
after its two operands. It is unambiguous and does not require the use of parentheses or
any knowledge of operator hierarchy for its evaluation.
Example: The infix expression ((a–b)/c)*((d+e)–f) has the following postfix and prefix
expression.
Postfix: ab–c/de+f –*
Prefix: */–abc–+def
Evaluating Postfix Expression:
scan given postfix expression;
for each symbol in postfix
if operand
then push its value onto a stack S;
if operator
then { pop operand2;
pop operand1;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
1
, Evaluating Prefix Expression:
reverse given prefix expression;
scan the reversed prefix expression;
for each symbol in reversed prefix
if operand
then push its value onto a stack S;
if operator
then { pop operand1;
pop operand2;
apply operator to compute operand1 op operand2;
push result back onto stack S;
}
return value at top of stack;
Infix to Postfix Conversion:
given a legal infix string;
create an initially empty postfix string;
create an initially empty operator stack S;
for each symbol ch in the infix string do
if ch is an operand
then
append it to the output postfix string;
else if ch == ‘(‘
then
push ch onto stack S;
else if S == ‘)’
then
pop and append operators to output string until the matching ‘(‘ is encountered;
// discard the two parentheses
else // ch must be some other operator
{ while operator stack not empty
and precedence(top(S)) ≥ precedence(ch)
and top(S) != ‘(‘ do
pop operator;
append it to the postfix string;
end while;
push S
}
end for;
while operator stack is not empty do
pop operator;
append it to the postfix string;
endwhile;
2
