Two mark Questions...
1. Define stack.
Stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of stack.
2. What is top of stack?
The end of stack, at which the items are added or deleted is called top of stack.
3. Why stack is called LIFO list?
The last element inserted into the stack is the first element to be deleted.For this reason, stack is called Last-In First-Out list.
4.What are the operations that can be performed on a stack?
i) Push- Adding an item to a stack. Push(S,i) adds an item i to the top of stack.
ii) Pop - Removes an item from stack. i=Pop(S) returns the top element to i.
5. What is empty stack?
The stack which contains no items in it is called Empty stack.
6. What causes underflow of stack? How it could be avoided?
If an illegal attempt is made to pop or access an item from empty stack, it causes stack underflow.
To avoid underflow, before any pop(S) or stacktop(S), check whether empty(S) is true or false.
7. What is nesting depth and parenthesis counts in an expression?
Nesting depth is the number of scope that have been opened, but not yet closed at that point.
Parenthesis count is the number of left parenthesis minus number of right parenthesis encountered at a particular point when the expression is scanned from left end.
8. What are the two conditions for admissible pattern of expression?
i. The Parenthesis count at the end of the expression is 0.
ii. The parenthesis count at each point in the expression is nonnegative
9. How an expression is validated if the delimiters are different?
The delimiters in an expression can be (,), [,] and {,}. But the scope ender must be same as scope opener. The number of scopes and type of scopes should be kept on account
Push scope opener to stack. When scope ender is encountered, check if the opener is matching. Otherwise, expression is invalid. At the end of expression, stack must be empty. Otherwise, expression is invalid
10. What are the limitations in the stack, When array used as home of stack?
The Array is finite collection of elements and in stack the number of elements is unlimited. As the stack dynamically changes the attempt to insert more elements than the array size cause overflow
11. Define Modularization?
Modularization is the concept of isolating the complex implementation into set of independent and easily identifiable units, to make the program easily understandable and modifiable.
12. What are the error conditions that could occur in stack implementation? How could they be rectified?
i) Overflow
ii) Underflow
To avoid overflow, the stack should be checked whether it is full or not before every push operation.
To avoid underflow, the stack should be checked for emptiness before every pop operation.
13. What is overflow in stack?
When array is used as home of stack, and when the stack contains as many elements as array, and as attempt is to push another element on stack, it cause overflow.
14. Why infix expression should be converted to Prefix / Postfix?
In Infix, operator precedence can be set only after scanning the expression for several times. But, conversion of Infix to Postfix or Prefix with use of stack, help to set precedence based on order of arrangement in a single scanning
15. Convert ((A+B) * C – (D – E)) $ (F + G) To Postfix and Prefix notation.
Prefix : $ - * + ABC – DE + FG.
Postfix : AB + C * DE -- FG + $
Other Questions:
1. Write the algorithm to check the validity of expression. (6)
2. Write the ADT For Stack (6)
3. Write a Program to implement the stack operations like push, pop and peep using arrays (16)
4. Convert 4$2*3-3+8/4/(1+1) to postfix using stack (10)
5. Write the algorithm to evaluate postfix expression (8)
6. Evaluate the following postfix expression using stack 653*+1-93/+
7. Write a program in C, to evaluate postfix expression (16)
8. Write the algorithm to convert Infix expression to postfix (8)
9. Write C program to convert Infix to Postfix (16)
Works For You........
1. Stack is static object. Is this statement true or False ? Comment the reason for your answer.
2. Write Parenthesis count at each point of the following expressions and check whether it is valid or not?
i) A+ ((( B-C) * (D-E) + F) / G)
ii) (a-b (C+D)) * (a - b)
iii) A- (B-C)(C-D) (D+(E*F)
3. Show contents of stack, at each point of the expression
i) (A+B})
ii) (A+B) -{C+D}-[F+G]
iii) {[A+B]}-[(C+D)]
iv) ((H) * {([J+K])})
v) ((( A ))))
4. Convert the following Infix expression to Postfix and Prefix
i) A+B* C+D/E + F/G
ii) ((X+Y) * (W+Z)) / (A*B) + (C/D)
iii) A+B+C+D+E
5. Evaluate the following Postfix expressions
i) AB + C - BA+ C$-
ii) ABC+* CBA-+*
(Assume A=1, B=2, C=3)
