Question

Is for study for an exam, thanks.

Some Review Questions/Exercises • • Convert a * b/c - d to posfix notation Provide an algorithm and evaluate the following postfix expression: 8 3 / 4 + Explain how we can use a deque to implement a queue. What are two possible prototypes for the pop() operation? Why is it more difficult to implement a queue with an array than implementing a . stack with an array? •

Answer 1

1. Convert a * b / c - d to postfix notation

Algorithm to convert from infix(Q) to postfix expression (P) :

Step 1: Push "(" on the stack and add ")" to the end of Q

Step 2 : Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the Stack is empty.

Step 3 : If an operand is encountered add it to P.

Step 4: If a left parenthesis ("(") is encountered ,push it on to stack.

Step 5: If an operator is encountered then:

• Repeatedly pop from stack and add to P each operator which has the same precedence as/higher precedence than this particular operator.
• Add operator to stack

Step 6: If a right parenthesis (")") is encountered then

• Repeatedly pop from stack and add to P each operator until a left parenthesis is encountered.
• Remove the left parenthesis

Step 7 : Exit

Q = a * b / c - d )

Q	Stack	P
a	(	a
*	( *	a
b	( *	ab
/	( /	ab*
c	( /	ab*c
-	( -	ab*c/
d	( -	ab*c/d
)		ab*c/d-

Postfix expression : a b * c / d -

2. Evaluation of Postfix expression : 8 3 / 4 +

Algorithm to evaluate a postfix expression(P) :

Step 1 : Add a right parenthesis at the end of P

Step 2: Scan P from left to right and repeat steps 3 and 4 for each element of P until ")" is encountered.

Step 3: If an operand is encountered push it to Stack.

Step 4 (a): If an operator is encountered, remove the top 2 elements of Stack where A is at the top and B is next to top.

(b) Evaluate B operator A

(c) Push the result back to stack

Step 5: Result of the expression is the value at the top of stack

Postfix expression : 8 3 / 4 + )

Iteration 1:

Current element = 8 which is an operand, push it to stack

Stack :

8

Iteration 2:

Current element = 3 which is an operand, push it to stack

Stack :

3

8

Iteration 3:

Current element = / which is an operator, pop the first two top elements from Stack

A = 3

B = 8

Result = B operator A = 8/3 = 2.67

Push the Result back to Stack

Stack :

2.67

Iteration 4:

Current Element = 4 , which is an operand, push it to stack

Stack :

4

2.67

Iteration 5:

Current Element = + which is an operator, pop the first two top elements from Stack

A = 2.67

B = 4

Result = B + A = 4 + 2.67 = 6.67

Push the Result back to stack

Stack :

6.67

Iteration 6:

Current element = ) , end the loop

Result = 6.67

Value of the expression = 6.67

3. Deque (Double ended queue) is a data structure in which elements can be inserted and deleted from either ends i.e from the front as well as from the back. We can use Deque to implement a Queue by restricting its insertion only at the end of Deque and deletion only from the front of Deque which is the case in Queue.

4. pop() operation is used to remove and return the top element of stack. The two possible prototypes of pop() operation are:

• To pass the reference of the variable of type stored in stack to pop as an argument and return the top element in that argument and the function itself returns if the deletion was successful or not: bool pop(int &data) ; where the stack stores elements of type Integer

In this case the value of element deleted will be returned in the argument data passed to function and the function returns the result of the operation was successful or not. In this case if the stack is empty ,we do not need to return any dummy value in data or raise an exception, we can return false from the function to signal failure of the operation.

• To remove and return the top element of the stack from the function: int pop() ; where stack stores elements of type Integer.

In this case the top element of the stack is removed and returned by the function.In case of empty stack, this function must return either a dummy value or raise exception to signal deletion from an empty stack.

5. Stack is a data structure in which both insertion and deletion of elements take place at one end i.e from the top of stack. So in stack , we only need to maintain a single pointer which points to the top of stack.

Queue is a data structure in which insertion take place at the end of the queue and deletion take place from the front of the queue. So we need to maintain 2 pointers pointing to the front and end of queue.

It is more difficult to implement Queue using an array than implementing a Stack using an array , because in Stack both insertion and deletion take place at top of the Stack , so in case of insertion the only operation is to increment the top pointer and place the item and similarly, in case of deletion the only operation is to decrement the top pointer. But in case of Queue since insertion takes place at the end and deletion at the front. In case of insertion , we only need to increment rear pointer and place the element. But in case of deletion, since deletion takes place at the front of the queue, in order to remove the first element all the elements are shifted by one position to the left to remove the front element. So the amount of operation in case of deletion for queue is much more as compared to Stack when implementing using the array.