Stacks

Stack
• Linear Data Structure
• Access is allowed only at one point of the structure,
normally termed the top of the stack
– access to the most recently added item only
Stack
• Elements are added to and removed from the top of the
stack (the most recently added items are at the top of
the stack).
• Described as a
"Last In First Out" (LIFO) data structure.
OR First In Last Out data structure.
• Operations are limited:
– push (add item to stack)
– pop (remove top item from stack)

3
Last In First Out

E top
D top D D top
C top C C C
B top B B B B
A A A A A
A top
Operation - PUSH
Operation - POP
Applications of Stack
• Recursion
• Parsing
• Infix to Postfix/Prefix Conversion
• Prefix/Postfix Evaluation
• Undo and Redo Operation in Editors
• Matching Paranthesis
• Reverse word/string
Uses of Stacks
• The runtime stack used by a
process (running program) to
keep track of methods in
progress
• Search problems
• Undo, redo, back, forward

Stacks 8
Recursion
Recursion

CIS 068
Recursion
• Sometimes, the best way to solve a
problem is by solving a smaller version of
the exact same problem first

• Recursion is a technique that solves a

problem by solving a smaller problem of
the same type

• A procedure that is defined in terms of

itself

CIS 068
Recursion
What’s behind this function ?

public int f(int a){

if (a==1)
return(1);
else
return(a * f( a-1));
}

It computes f! (factorial)
CIS 068
Tracing the example
public int f(int a){
if (a==1)
RECURSION !
return(1);
else
return(a * f( a-1));
}

CIS 068
Watching the Stack
public int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to L4
a=2
Return to L4
a=3
Return to L4
a=4 a=4
Return to L4 Return to L4
a=5 a=5
… a=5
Initial After 1 recursion After 4th recursion

Every call to the method creates a new set of

CIS 068
local variables !
Watching the Stack
public int factorial(int a){
if (a==1)
return(1);
else
return(a * factorial( a-1));
}

a=1
Return to L4
a=2 a = 2*1 = 2
Return to L4 Return to L4
a=3 a=3 a = 3*2 = 6
Return to L4 Return to L4 Return to L4
a=4 a=4 a=4 a = 4*6 = 24
Return to L4 Return to L4 Return to L4 Return to L4
a=5 a=5 a=5 a=5 a = 5*24 = 120
After 4th recursion Result

CIS 068
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 Expression : 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 Expression: 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
• This is done by assigning operator priorities.
– priority(*) = priority(/) > priority(+) = priority(-)
• 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
Why Postfix/Prefix ?
• Why to use these PREFIX and POSTFIX notations when we have
simple INFIX notation?

• To our surprise INFIX notations are not as simple as they seem

specially while evaluating them. To evaluate an infix expression
we need to consider Operators’ Priority and Associative property.
– For example expression 3+5*4 evaluate to 32 i.e. (3+5)*4
or to 23 i.e. 3+(5*4).

• To solve this problem Precedence or Priority of the operators

were defined. Operator precedence governs evaluation order. An
operator with higher precedence is applied before an operator
with lower precedence.
Infix Expression Is Hard To Parse
• 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

(A+B) * (C + D)

A-B/(C*D^E)
Examples of infix to prefix and post fix
Infix PostFix Prefix

A+B AB+ +AB

(A+B) * (C + D)

A-B/(C*D^E)
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

Token Operator Precedence1 Associativity

() function call 17 left-to-right

[] array element
-> . struct or union member
-- ++ increment, decrement2 16 left-to-right

-- ++ decrement, increment3 15 right-to-left

! logical not
- one’s complement
-+ unary minus or plus
&* address or indirection
sizeof size (in bytes)
(type) type cast 14 right-to-left

*/% mutiplicative 13 Left-to-right

+- binary add or subtract 12 left-to-right

<< >> shift 11 left-to-right

> >= relational 10 left-to-right

< <=
== != equality 9 left-to-right

& bitwise and 8 left-to-right

^ bitwise exclusive or 7 left-to-right

bitwise or 6 left-to-right

&& logical and 5 left-to-right

 logical or 4 left-to-right
?: conditional 3 right-to-left

= += -= assignment 2 right-to-left
/= *= %=
<<= >>=
&= ^= =

, comma 1 left-to-right
I/P Stack
Symbol Preceden Precedenc
ce f e g
+, – 1 2

^ or ⬆ or $
*, / 3 4
6 5

( 7 0
) 0 -
When do we need to use them… 
• So, what is actually done is expression is
scanned from user in infix form; it is converted
into prefix or postfix form and then evaluated
without considering the parenthesis and
priority of the operators.
Example
Infi x Reverse Polish (Postfi x)
((a+b)/ d^((e-f)+g)) ab+def-g+^/
z+(y*x-(w/ v^u)*t)*s zyx*wvu^/ t*-s*+
(a+b)*(c-d)^e*f ab+cd-e^*f*
(a+b)*(c^(d-e)+f)-g ab+cde-^f+*g-
a+(((b-c)*(d-e)+f)/ g)^(h-j) abc-de-*f+g/ hj-^+
a/ b^c+d*e-a*c abc^/ de*+ac*-
(a+b)*c+d/ (b+a*c)+d ab+c*dbac*+/ +d+
((((m^n^d)-(a^c-b)/ (p-q)*e)+f)-x) mnd^^ac^b-pq-/ e*-f+x-
m+(n-(a^(b-c)*d)/ f) mnabc-^d*f/ -+
Algorithm for Infix to Postfix
1) Examine the one by one character from the input.
2) If it is operand, append in output string.
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 operator has higher priority than the top of stack, push operator on
stack.
iv) Else pop the operator from the stack and append in output string,
repeat step 4

5) If it is a closing parenthesis, pop operators from stack and append them in

output string until an opening parenthesis is encountered. pop and discard
the opening parenthesis.
6) If there is more input characters then go to step 1
7) If there is no more input, pop the remaining operators and append in
output string.
1. [Initialize stack]
TOP ← 1 , PUSH (S, TOP, ’(‘)
2. [Initialize output string]
POLISH ← NULL
3. [Get first input symbol]
NEXT ← NEXTCHAR(INFIX)
4. [Translate the infix expression]
Repeat thru step 7 while NEXT ≠ ' (‘
5. Remove symbols with greater precedence from stack]
Repeat while f(NEXT) < g(S[TOP])
TEMP ← POP(S,TOP)
POLISH ← POLISH ○ TEMP
String Concatenation
6. [Are there matching parentheses?]
If f (NEXT) ≠ g (S[TOP]) then Call PUSH (S,TOP,NEXT)
else POP(S,TOP)
7. [Get next input symbol]
NEXT ← NEXTCHAR(INFIX)
8. Print Output String
Evaluation a postfix expression
Steps:
1. Find the leftmost operator in the expression.
2. Select two operands immediately to the left
of the operator found.
3. Perform the indicated operation.
4. Replace the operator and operands with the
result.
2 3 * 2 1 - / 5 4 1 - * +
Operand1 Operand2 Value Stack
2 2
3 2,3
* 2 3 6 6
2 6,2
1 6,2,1
- 2 1 1 6,1
/ 6 1 6 6
5 6,5
4 6,5,4
1 6,5,4,1
- 4 1 3 6,5,3
* 5 3 15 6,15
+ 6 15 21 21
+ / * 2 3 - 2 1 * 5 - 4 1
Operand1 Operand2 Value Stack
1 1
4 1,4
- 4 1 3 3
5 3,5
* 5 3 15 15
1 15,1
2 15,1,2
- 2 1 1 15,1
3 15,1,3
2 15,1,3,2
* 2 3 6 15,1,6
/ 6 1 6 15,6
+ 6 15 21 21
Algorithm for evaluating a postfix
expression (Cond.)
WHILE more input items exist
{
If symb is an operand
then push (S, Top, symb)
else //symbol is an operator
{
Opnd2=pop(S, Top);
Opnd1=pop(S, Top);
Value = opnd1 operator opnd2 // perform operation as per theoperator
Push(S, Top, value);
} //End of else
} // end while
Result = pop (S, Top);
Evaluate 623+-382/+*2^3+

Symbol opnd1 opnd2 value opndstk

6 6
2 6,2
3 6,2,3
+ 2 3 5 6,5
- 6 5 1 1
3 6 5 1 1,3
Evaluate- 623+-382/+*2^3+
Symbol opnd1 opnd2 value opndstk
8 6 5 1 1,3,8
2 6 5 1 1,3,8,2
/ 8 2 4 1,3,4
+ 3 4 7 1,7
* 1 7 7 7
2 1 7 7 7,2
^ 7 2 49 49
3 7 2 49 49,3
+ 49 3 52 52
Stack Applications
• Recursion
• Conversion (Infix to Postfix, Infix to Prefix)
• Evaluation (Postfix, Prefix)
• Parsing
– Matching Parenthesis
– Match in HTML tags < >
– Matching if else
• Browser
• Editors (undo, redo)
• Other data structures use stack for implementation