Data Structures
Stack Applications
(Infix, Postfix and Prefix Expressions)
Presented by
K. SOMASENA REDDY
Algebraic Expression
• An algebraic expression is a legal combination of
operands and the operators.
• Operand is the quantity (unit of data) on which a
mathematical operation is performed.
• Operand may be a variable like x, y, z or a constant
like 5, 4,0,9,1 etc.
• Operator is a symbol which signifies a mathematical
or logical operation between the operands. Example
of familiar operators include +,-,*, /, ^
• Considering these definitions of operands and
operators now we can write an example of
expression as x+y*z.
Infix, Postfix and Prefix Expressions
• INFIX: From our schools times we have been familiar with the
expressions in which operands surround the operator, e.g. x+y, 6*3 etc
this way of writing the Expressions is called infix notation.
• POSTFIX: Postfix notation are also Known as Reverse Polish Notation
(RPN). They are different from the infix and prefix notations in the
sense that in the postfix notation, operator comes after the operands, e.g.
xy+, xyz+* etc.
• PREFIX: Prefix notation also Known as Polish notation. In the prefix
notation, as the name only suggests, operator comes before the operands,
e.g. +xy, *+xyz etc.
Operator Priorities
• How do you figure out the operands of an
operator?
⮚a + b * c
⮚a * b + c / d
• When an operand lies between two
operators, the operand associates with the
operator that has higher priority.
Tie Breaker
• When an operand lies between two operators
that have the same priority, the operand
associates with the operator on the left.
⮚a + b - c
⮚a * b / c / d
Delimiters
• Sub expression within delimiters is treated as
a single operand, independent from the
remainder of the expression.
⮚(a + b) * (c – d) / (e – f)
Infix Expression Is Hard?
• Need operator priorities, tie breaker, and
delimiters.
• This makes computer evaluation more difficult
than is necessary.
• Postfix and Prefix expression forms do not rely
on operator priorities, a tie breaker, or
delimiters.
• So it is easier to evaluate expressions that are
in these forms.
Examples of infix to prefix and post fix
Infix PostFix Prefix
A+B AB+ +AB
(A+B) * (C + D) AB+CD+* *+AB+CD
A-B/(C*D^E) ABCDE^*/- -A/B*C^DE
Example: postfix expressions
• Postfix notation is another way of writing arithmetic
expressions.
• In postfix notation, the operator is written after the two
operands.
infix: 2+5 postfix: 2 5 +
• Expressions are evaluated from left to right.
• Precedence rules and parentheses are never needed!
Suppose that we would like to rewrite
A+B*C in postfix
• Applying the rules of precedence, we
obtained
A+B*C
A+(B*C) Parentheses for emphasis
A+(BC*) Convert the multiplication, Let D=BC*
A+D Convert the addition
A(D)+
ABC*+ Postfix Form
Postfix Examples
Infix Postfix Evaluation
2-3*4+5 234*-5+ -5
(2 - 3) * (4 + 5) 23-45+* -9
2- (3 * 4 +5) 234*5+- -15
Algorithm for Infix to Postfix
1) Examine the next element in the input.
2) If it is operand, output it.
3) If it is opening parenthesis, push it on stack.
4) If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of stack is opening parenthesis, push operator on
stack
iii) If it has higher priority than the top of stack, push operator on
stack.
iv) Else pop the operator from the stack and output it, repeat
step 4
5) If it is a closing parenthesis, pop operators from stack and output
them until an opening parenthesis is encountered. pop and
discard the opening parenthesis.
6) If there is more input go to step 1
7) If there is no more input, pop the remaining operators to output.
Suppose we want to convert 2*3/(2-1)+5*3 into Postfix form,
Expression Stack Output
2 Empty 2
* * 2
3 * 23
/ / 23*
( /( 23*
2 /( 23*2
- /(- 23*2
1 /(- 23*21
) / 23*21-
+ + 23*21-/
5 + 23*21-/5
* +* 23*21-/53
3 +* 23*21-/53
Empty 23*21-/53*+
Example
• ( 5 + 6) * 9 +10
will be
• 5 6 + 9 * 10 +
Evaluation a postfix expression
• Each operator in a postfix string refers to the
previous two operands in the string.
• Suppose that each time we read an operand we
push it into a stack. When we reach an operator,
its operands will then be top two elements on
the stack
• We can then pop these two elements, perform
the indicated operation on them, and push the
result on the stack.
• So that it will be available for use as an operand
of the next operator.
Evaluating Postfix Notation
• Use a stack to evaluate an expression in postfix
notation.
• The postfix expression to be evaluated is
scanned from left to right.
• Variables or constants are pushed onto the
stack.
• When an operator is encountered, the
indicated action is performed using the top
elements of the stack, and the result replaces
the operands on the stack.
Evaluating a postfix expression
• Initialise an empty stack
• While token remain in the input stream
–Read next token
–If token is a number, push it into the stack
–Else, if token is an operator, pop top two tokens
off the stack,apply the operator, and push the
answer back into the stack
• Pop the answer off the stack.
Example: postfix expressions
(cont.)
Postfix expressions:
Algorithm using stacks (cont.)
Algorithm for evaluating a postfix
expression (Cond.)
WHILE more input items exist
{
If symb is an operand
then push (opndstk,symb)
else //symbol is an operator
{
Opnd1=pop(opndstk);
Opnd2=pop(opndnstk);
Value = result of applying symb to opnd1 & opnd2
Push(opndstk,value);
} //End of else
} // end while
Result = pop (opndstk);
Thank you