COMPUTER SCIENCE LINKED LISTS , STACKS AND QUEUES

DELHI : 2002

3.b) Given the following class, char *msg[ ]={“over flow”,”under flow”};

class Stack
{ int top; //the stack pointer
int stk[5]; //the elements
void err_rep(int e_num)
{ cout<<msg[e_enum];
//report error message
}
public:
void init( )
{ top=0;
} //initialize the stack pointer
void push(int); //put new value in stk
void pop( ); //get the
top value.
};

Define pop outside the Stack. In your definition take care of under flow condition. Function pop should invoke err_rep to report under flow.

4

Solution:

void Stack::pop( )
{ //Dear children, try to complete this function.
}

3.c) Change the following infix expression into postfix expression. (A+B)*C+D/E-F.

3

Ans) Children, Try this answer as an assignment.

DELHI : 2001

3.d) Write an algorithm to convert an infix expression to postfix expression.

Ans)
The following algorithm transforms the infix expression X into its equivalent postfix expression Y. The algorithm uses a stack to temporarily hold operators and left parentheses. The postfix expression Y will be constructed from left to right using the operands from X and the operators which are removed from STACK. We begin by pushing a left parenthesis onto STACK and adding a right parenthesis at the end of X. The algorithm is completed when STACK is empty.

Algorithm:
Suppose X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.

1. Push “(“ onto STACK, and add “)” to the end of X.
2. Scan X from left to right and REPEAT Steps 3 to 6 for each element of X UNTIL the STACK is empty.
3. If an operand is encountered, add it to Y.
4. If a left parenthesis is encountered, push it onto STACK.
5. If an operator is encountered, then:

(a) Repeatedly pop from STACK and add to Y each operator(on the top of STACK) which has the same precedence as or higher precedence than operator.
(b) Add operator to STACK. /* End of If structure */

6. If a right parenthesis is encountered, then:

(a) Repeatedly pop from STACK and add to Y each operator (on the top of STACK) until a left Parenthesis is encountered.
(b) Remove the left parenthesis. (Do not add the left parenthesis to Y). /* End of If structure */

7. End.

 

CBSE Computer Science Solved Revision Tour By Mr. Ravi Kiran ( mrkdata@yahoo.com )