CBSE Computer Science - Revision Tour(Solved)
CBSE Guess > eBooks > Class XII > CBSE Computer Science Link Lists, Stacks And Queues Solved Revision Tour By Mr. Ravi Kiran
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.
- Push “(“ onto STACK, and add “)” to the end of X.
- Scan X from left to right and REPEAT Steps 3 to 6 for each element of X UNTIL the STACK is empty.
- If an operand is encountered, add it to Y.
- If a left parenthesis is encountered, push it onto STACK.
- 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 */
- 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 */
- End.
CBSE Computer Science Solved Revision Tour By Mr. Ravi Kiran ( [email protected] ) |