UNIT 5
QUESTIONS
Q1What is stack and its advantages?
Stack
- Infix
- Prefix
- Postfix
Applications of stacks
Stacks as abstract data types
Applications of Stack
Stack operations
Algorithms for Stack Operations – PUSH, POP, PEEP
Q2 What are basic operations in stack write algorithm
Algorithms for Stack Operations – PUSH, POP, PEEP
A pointer TOP keeps track of the highest element within the stack. Initially, when the stack is empty, TOP features a value of “one” then on.
Each time a replacement element is inserted within the stack, the pointer is incremented by “one” before, the element is placed on the stack. The pointer is decremented by “one” whenever a deletion is formed from the stack.
Procedure: PUSH (S, TOP, X)
This procedure inserts a component x to the highest of a stack which is represented by a vector S containing N elements with a pointer TOP denoting the highest element within the stack.
1. [Check for stack overflow]
If TOP ≥ N
Then write (‘STACK OVERFLOW’)
Return
2. [Increment TOP]
TOP ←TOP + 1
3. [Insert Element]
[STOP] ←X
4. [Finished]
Return
Function: POP (S, TOP)
This function removes the highest element from a stack which is represented by a vector S and returns this element. TOP may be a pointer to the highest element of the stack.
1. [Check for underflow of stack]
If TOP = 0
Then Write (‘STACK UNDERFLOW ON POP’)
Take action in response to underflow
Return
2. [Decrement Pointer]
TOP ← TOP – 1
3. [Return former top element of stack]
Return (S[TOP + 1])
Function: PEEP (S, TOP, I)
This function returns the worth of the ith element from the highest of the stack which is represented by a vector S containing N elements. The element isn't deleted by this function.
1. [Check for stack Underflow]
If TOP - I +1 ≤ 0
Then Write (‘STACK UNDERFLOW ON PEEP’)
Take action in response to Underflow
Exit
2. [Return Ith element from top of the stack
Return (S[TOP – I + 1])
Q3 What is polish notations write algorithm
Polish operations
Postfix notation
- Prefix notation- operator are infixed to operands e.g.- +ab
- Infix notation - simplest way of writing e.g.a+b
- postfix operators is prefixed to operands e.g.- ab+
Sr.No. | Infix Notation | Prefix Notation | Postfix Notation |
1 | a + b | + a b | ab+ |
2 | (a + b) ∗ c | *+abc | a b + c ∗ |
3 | a ∗ (b + c) | ∗ a + b c | a b c + ∗ |
4 | a / b + c / d | + / a b / c d | a b / c d / + |
5 | (a + b) ∗ (c + d) | ∗ + a b + c d | a b + c d + ∗ |
6 | ((a + b) ∗ c) - d | - ∗ + a b c d | a b + c ∗ d - |
Precedence
When an operator is between two operands precedence decides which operator will be first evaluated
a+b*c a+(b*c)
Associativity
Associativity is the rule where operators with the same precedence appear in an expression
S no | Operator | Operator | Precedence | Associativity |
1 | Exponentiation | ^ | Highest | Right associative |
2 | Multiplication and division | ‘*’ and ‘/’ | Second highest | Left associative |
3 | Addition and subtraction | + and - | Lowest | Left associative |
Postfix evaluation algorithm
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack
Step 3 − if it is an operator pull operand from stack and perform operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation
Algorithm to convert infix to postfix
Algorithm: REVPOL
Given an input string INFIX containing an infix expression which has been padded on the proper with ‘)’ and whose symbol have precedence value given by above table, a vector S used as a stack and a NEXTCHAR which when invoked returns subsequent character of its argument. This algorithm converts INFIX into reverse polish and places the end in the string POLISH. The integer variable TOP denotes the highest of the stack.
Algorithm PUSH and POP are used for stack manipulation. The integer variable RANK accumulates the rank
of expression. Finally the string variable TEMP is employed for temporary storage purpose.
1. [Initialize stack]
TOP ←1
S[TOP] ‘(‘
2. [Initialize output string and rank count]
POLISH ←‘ ‘
RANK ←0
3. [Get first input symbol]
NEXTNEXTCHAR (INFIX)
4. [Translate the infix expression]
Repeat thru step 7 while NEXT != ‘ ‘
5. [Remove symbols with greater precedence from stack]
IF TOP < 1
Then write (‘INVALID’)
EXIT
Repeat while G (S[TOP]) >F(NEXT)
TEMP ←POP (S, TOP)
POLISH ←POLISH O TEMP
RANK ←RANK + R(TEMP)
IF RANK <1
Then write ‘INVALID’)
EXIT
6. [Are there matching parentheses]
IF G(S[TOP]) != F(NEXT)
Then call PUSH (S,TOP, NEXT)
Else POP (S,TOP)
7. [Get next symbol]
NEXT ←NEXTCHAR(INFIX)
8. [Is the expression valid]
IF TOP != 0 OR RANK != 1
Then write (‘INVALID ‘)
Else write (‘VALID ’)
Q4 Translate the following string into Polish notation and trace the content of
Stack: (a + b ^ c ^ d) * ( e + f / d )
Step-1: reverse infix expression
) d / f + e ( * ) d ^ c ^ b + a (
Step-2: convert ‘(‘ to ‘)’ and ‘)’ to ‘(‘ and append extra ‘)’ at last
(d / f + e ) * (d ^ c ^ b + a) )
Step-3: Now convert this string to postfix
Step 4: Reverse this postfix expression
* + a ^ ^ b c d + e / f d
Q5 Convert the following string into prefix: A-B/(C*D^E)
Step-1: reverse infix expression
) E ^) D * C ((/ B - A
Step-2: convert ‘(‘to ‘)’ and ‘)’ to ‘(‘and append extra ‘)’ at last
(E ^ (D * C)) / B - A
Step-3: Now convert this string to postfix
Step 4: Reverse this postfix expression
- A / B ^ * C D E
Q6 How stacks can be implemented as other data types?
REPRESENTATION OF A STACK
- using a one-dimensional array
- one linked list.
Array Representation of Stacks
Linked List Representation of Stacks
Q7 How to implement multiple stacks?
Multiple stacks
push(int x, intsn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1
pop(intsn) –> pops a component from stack number ‘sn’ where sn is from 0 to k-1
Method 1 (Divide the array in slots of size n/k)
Method 2 (A space-efficient implementation)
Time complexities of operations push() and pop() is O(1).
The best a part of implementing multiple stacks is, if there's a slot available in stack, then an item are often pushed in any of the stacks, i.e., no wastage of space.
Q8 What is back tracking?
Backtracking algorithmic strategy
Problems in backtracking
Backtrack algorithm
Backtrack(x)
if x is not a solution
return false
if x is a new solution
add to list of solutions
backtrack(expand x)
Example- Find all the possible ways of arranging 2 boys and 1 girl on 3 benches. Constraint: Girl should not be on the middle bench.
Solution There are a total of 3! = 6 possibilities. We will try all the possibilities and get the possible solutions. We recursively try all the possibilities.
Possible condition
Q9 Trace the conversion of infix to postfix form in tabular form
( A + B ) * C + D / ( B + A * C ) + D
Q10 Explain how stack can be used in backtracking?
Backtracking
Backtracking using stack rat maze problem
Recursion uses a call stack to stay the shop each recursive call then pop because the function ends. We’ll eliminate recursion by using our own stack to try to to an equivalent thing.
A node structure is employed to store the (i, j) coordinates and directions explored from this node and which direction to undertake out next.
Structure Used:
Procedure
Maze[4][5] = {
{1, 0, 1, 1, 0},
{1, 1, 1, 0, 1},
{0, 1, 0, 1, 1},
{1, 1, 1, 1, 1}
}
fx = 2, fy=3
Path Found!
The path can be: (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) -> (2, 3)