CS计算机代考程序代写 scheme algorithm Week # 3 – Exercises

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 –