Applications of Stack
Parentheses Matching by Stack
position: 0 1 2 3 4 5 6 7
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
Output pairs (u,v) such that the left parenthesis at
position u is matched with the right parenthesis at v.
(2,6) (1,13) (15,19) (21,25) (27,31) (0,32) (34,38)
Parentheses
P
th
M
Matching
t hi
Towers Of Hanoi/Brahma
System Stack
R In
Rat
I AM
Maze
(a+b))*((c+d)
(0,4)
(0
4)
right parenthesis at 5 has no matching left parenthesis
(8,12)
left parenthesis at 7 has no matching right parenthesis
Parentheses Matching
scan expression from left to right
when a left parenthesis is encountered, add its
position to the stack
when a right parenthesis is encountered,
encountered remove
matching position from stack
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
2
1
0
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
6
2
1
0
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
13
1
0
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
15
1
0
(2,6) (1,13)
(2,6)
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
21
1
0
(2,6) (1,13) (15,19)
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
27
1
0
Example
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
(((a+b)*c+d e)/(f+g) (h+j)*(k l))/(m n)
1
0
(2,6) (1,13) (15,19) (21,25)
(2,6) (1,13) (15,19) (21,25)(27,31) (0,32)
and so on
Recursion
Recursion is a fundamental programming
technique
h i
that
h can provide
id an elegant
l
solution
l i for
f
certain kinds of problems.
A recursive definition
f
is one which uses the word
or concept being defined in the definition itself.
Example: Recursive Definition of N!
N!, for any positive integer N, is defined to be the product of all
integers between 1 and N inclusive.
This definition can be expressed recursively as:
0!
1!
N!
=
=
=
1
1 * 0!
N * (N-1)!
The concept of the factorial is defined in terms of another factorial.
Eventually the base case of 0! is reached.
Eventually,
reached
In class Exercise:
Fibonacci Numbers
1, 1, 2, 3, 5, 8, 13, 21,
Using a recursive formula to define Fibonacci
Numbers
Homework
iterative program
input:n
n
Outputfib(0) ~fib(n)
Towers Of Hanoi/Brahma
4
3
2
1
A
B
C
64 gold disks to be moved from tower A to tower C
eachh tower operates as a stackk
cannot place big disk on top of a smaller one
Towers Of Hanoi/Brahma
3
2
1
3
3-disk
disk Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
2
1
33-disk
disk Towers Of Hanoi/Brahma
3
3-disk
disk Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
3
2
33-disk
disk Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
3
2
3
3-disk
disk Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
33-disk
disk Towers Of Hanoi/Brahma
3-disk
3 disk Towers Of Hanoi/Brahma
7 disk moves
3
3-disk
disk Towers Of Hanoi/Brahma
Towers Of Hanoi/Brahma
2
1
Recursive Solution
3
2
1
n > 0 gold disks to be moved from A to C using B
move top n-1 disks from A to B using C
Recursive Solution
Recursive Solution
move top disk from A to C
move top n
n-1
1 disks from B to C using A
Recursive Solution
In Class Exercise
Show that
moves(n) = 2*moves(n-1) + 1 = 2n-1 when n
>0
moves(n) = 0 when n = 0
moves(n) = 2*moves(n-1) + 1 = 2n-1 when n > 0
System Stack
Towers Of Hanoi/Brahma
moves(64) = 1.8 * 1019 (approximately)
Performing 109 moves/second,
moves/second a computer would take
about 570 years to complete.
At 1 disk move/min
move/min, the monks will take about 3.4
3 4 * 1013
years.
Whenever a function is invoked,
invoked the
program creates a structure, referred to as
an acti
activation
ation record or a stack frame,
frame and
places it on top of the system stack.
previous frame pointer
return
t
address
dd
fp
local variables
f
fp
previous frame pointer
return address
Trace System Stack
double f()
{
int a=1,b=1;
return a+b;
}
void main()
{
int c=2, d;
dd=f();
f();
d=d+d;
}
d
c=2
2
previous frame pointer
return address.
Back to OS
main
previous frame pointer
return address
Trace System Stack
double f()
{
int a=1,b=1;
return a+b;
}
void main()
{
int c=2, d;
d=f();
d
f();
d=d+d;
}
b=1
a=1
previous frame pointer
return address.
d
c=2
2
previous frame pointer
return address.
Back to OS
main
Trace System Stack
double f()
{
int a=1,b=1;
return a+b;
}
void main()
{
int c=2, d;
dd=f();
f();
d=d+d;
}
Rat In A Maze
d=2
c=2
2
previous frame pointer
return address.
Back to OS
Rat In A Maze
Move order is: right,
g down, left, up
p
Block positions to avoid revisit.
Rat In A Maze
Move order is: right, down, left, up
Block positions to avoid revisit.
Rat In A Maze
Rat In A Maze
0,0
Move backward until we reach a square from which
a forward move is possible.
Move down.
down
Rat In A Maze
Move left
left.
Rat In A Maze
Move down.
down
Rat In A Maze
Rat In A Maze
Move backward until we reach a square from which
a forward move is possible.
Move backward until we reach a square from which
a forward move is possible.
Move downward.
Rat In A Maze
Rat In A Maze
Move right
right.
Backtrack.
Move downward
downward.
Rat In A Maze
Move right
right.
Rat In A Maze
Move one down and then right
right.
Rat In A Maze
Move one up and then right.
right
Rat In A Maze
Move down to exit and eat cheese.
Path
P th ffrom maze entry
t to
t currentt position
iti operates
t as
a stack.
Remark: Allowable Moves for the
Rat in the Textbook
Homework
N
[i-1][j-1]
[i-1][j]
NE
NW
[i][j-1]
Sec. 3.5 Exercise 1 (b) P157
[i-1][j+1]
[i][j+1]
[i][j]
[i+1][j-1]
[i+1][j]
[i+1][j+1]
SW
SE
Trace the program (find the path on the maze
with stack).
)
E
