Stack Example
Data Structures and Abstractions
Stack Example Animation
Lecture 23
*
Stack Calculator Animation
*
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
8
10
+
+
It is an operator, so pop the last operator of the stack, for comparison
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
8
10
+
Which is done first?
(+ or /) ?
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
2
8
10
/
+
+
Since / is done first, we put + back on the stack, followed by /
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
2
8
10
/
+
/
It is an operator, so pop the last operator of the stack, for comparison
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
2
8
10
+
/
Which is done first?
(- or /) ?
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
2
8
10
+
/
/ is done first, so we pop the last two numbers off the stack
2
8
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
10
+
/
Perform the operation
2
8
/
=
4
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
6
4
10
–
+
/
And put the result and the ‘spare’ operator back on the stacks
2
8
/
=
4
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
6
4
10
+
–
It is an operator, so pop the last operator of the stack, for comparison
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
6
4
10
+
–
Which is done first?
(- or *) ?
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
5
6
4
10
*
–
+
–
Since * is done first, we put – back on the stack, followed by *
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
5
6
4
10
*
–
+
*
5
6
*
=
30
We have reached the end of the equation, so we simply pop operations and numbers until finished
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
30
4
10
–
+
*
5
6
*
=
30
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
30
4
10
–
+
–
30
4
–
=
-26
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
-26
10
+
+
-26
10
+
=
-16
10 + 8 / 2 – 6 * 5
Stack Calculator Animation
*
-16
+
-26
10
+
=
-16
There are no more operations, so if there is one number on the other stack, we have our answer.
More than one number would give an error.
10 + 8 / 2 – 6 * 5
*