Week # 3 – Exercises
Exercise #1: Suppose a letter means push and an asterisk means pop in the following
sequence. Give the sequence of values returned by the pop operations when this
sequence of operations is performed on an initially empty LIFO stack.
A U E * * I R * * K * *
E A S * Y * Q U E * * * S T * * * I O * N * * *
EURIKA
SYEUQTSAONIE
Exercise #2: Suppose that an intermixed sequence of push and pop operations are
performed. The push operation pushes the integers 0 through 9 in order; the pop
operations print out the return value. Which of the following sequences could not occur?
(a) 4 3 2 1 0 9 8 7 6 5
Push 0, Push 1, Push 2, Push 3, Push 4
Pop 4, Pop 3, Pop 2, Pop 1, Pop 0 => 4 3 2 1 0
Push 5, Push 6, Push 7, Push 8, Push 9
Pop 9, Pop 8, Pop 7, Pop 6, Pop 5 => 9 8 7 6 5
So we can get this output: 4 3 2 1 0 9 8 7 6 5
(b) 4 6 8 7 5 3 2 9 0 1
Push 0, Push 1, Push 2, Push 3, Push 4
Pop 4 => 4
Push 5, Push 6
Pop 6 => 6
Push 7, Push 8
Pop 8, Pop 7, Pop 5, Pop 3, Pop 2 => 8, 7, 5, 3, 2
Push 9
Pop 9, Pop 1, Pop 0 => 9, 1, 0
So we cannot get this output: 4 6 8 7 5 3 2 9 0 1
– 1 –
(c) 2 5 6 7 4 8 9 3 1 0
Push 0, Push 1, Push 2
Pop 2 => 2
Push 3, Push 4, Push 5
Pop 5 => 5
Push 6
Pop 6 => 6
Push 7
Pop 7, Pop 4 => 7, 4
Push 8
Pop 8 => 8
Push 9
Pop 9, Pop 3, Pop 1, Pop 0 => 9 3 1 0
So we can get this output: 2 5 6 7 4 8 9 3 1 0
(d) 4 3 2 1 0 5 6 7 8 9
Push 0, Push 1, Push 2, Push 3, Push 4
Pop 4, Pop 3, Pop 2, Pop 1, Pop 0 => 4 3 2 1 0
Push 5
Pop 5 => 5
Push 6
Pop 6 => 6
Push 7
Pop 7 => 7
Push 8
Pop 8 => 8
Push 9
Pop 9 => 9
So we can get this output: 4 3 2 1 0 5 6 7 8 9
– 2 –
Exercise #3: Convert the following infix expressions to postfix (RPN) expressions using
the Shunting Yard algorithm. With the help of a Stack and using the RPN Expression
evaluation scheme, evaluate them as well.
(a) 4 + ( 6 * 2 ) – 15
Answer: 4 6 2 * + 15 –
(b) 4 * ( 4 + 10 / 2.5 – 8 )
Answer: 4 4 10 2.5 / + 8 – *
(c) 17 + 21 * 3 / 7 + 21
Answer: 17 21 3 * 7 / + 21 +
Exercise #4: Run the above RPN expressions through with a stack to check they
calculate the correct answer.
Answers (a) 1 (b) 0 (c) 47
Exercise #5: Find the bitwise and, or and xor of the following:
(a) 0xC6 with 0x35
(b) 0x19 with 0x24
(c) 0xD3 with 0xC7
(d) 0x17 with 0xFF
First
Operand
Second
Operand
Bitwise
AND
Bitwise
OR
Bitwise
XOR
(a) 0xC6 ==
11000110
0x35 ==
00110101
0x4 ==
00000100
0XF7 ==
11110111
0xF3 ==
11110011
(b) 0x19 ==
00011001
0x24 ==
00100100
0x0 ==
00000000
0x3D ==
00111101
0x3D ==
00111101
(c) 0xD3 ==
11010011
0xC7 ==
11000111
0xC3 ==
11000011
0xD7 ==
11010111
0x14 ==
00010100
(d) 0x17 ==
00010111
0xFF ==
11111111
0x17 ==
00010111
0xFF ==
11111111
0xE8 ==
11101000
– 3 –