ACE-Stack - Questions and answers and practice materials for different lecture topics for PDF

Preview

Summary

Questions and answers and practice materials for different lecture topics for the Algorithm Correctness and Efficiency module....

Description

Stack – Question and Answer 1. Imagine we have two empty stacks of integers, s1 and s2. Draw a picture of each stack after the following operations: i. pushStack(s1, 3); pushStack(s1, 5); pushStack(s1, 7); pushStack(s1, 9); pushStack(s1, 11); pushStack(s1, 13); while (!emptyStack(s1)) { popStack(s1, x); pushStack(s2,x); }//while

Correct ii.

pushStack(s1, 3); pushStack(s1, 5); pushStack(s1, 7); pushStack(s1, 9); pushStack(s1, 11); pushStack(s1, 13); while (!emptyStack(s1)) { popStack(s1, x); popStack(s1, x); pushStack(s2,x); }//while

Correct 2. Change the following infix expressions to postfix expressions using the algorithmic method (a stack): i. D–B+C Input Expression Stack Postfix Expression D D D B DB + + DBC + DB-C DB-C+ (Answer) ii. A*B+C*D Input Expression A * B + C *

iii. (A + B) * C – D * F + C Input Expression ( A + B ) * C D * F +

Stack * * + + +*

Stack ( ( (+ (+ * * -* -* +

Postfix Expression A A AB AB* AB*C AB*C AB*C*+ (Answer)

Postfix Expression A A AB AB+ AB+ AB+C AB+C* AB+C*D AB+C*D AB+C*DF AB+C*DF*-

C

+

iv. (A - 2) * (B + C – D * E) * F Input Expression Stack ( ( A ( (2 () * * ( *( B *( + *(+ C *(+ *(D *(* *(-* E *(-* ) * * * F *

AB+C*DF*-C AB+C*DF*-C+ (Answer)

Postfix Expression

A A A2 A2A2A2A2-B A2-B A2-BC A2-BC+ A2-BC+D A2-BC+D A2-BC+DE A2-BC+DE*A2-BC+DE*-* A2-BC+DE*-*F A2-BC+DE*-*F* (Answer) Note: The stacks are represented horizontally to save writing space....