Question

13. You are using a stack to analyze a String, checking for balanced delimiters. Draw the contents of the stock and indicate the current character being considered at the point in the algorithm that in imbalance is detected, for the following string: "(<[(>])"

Answer 1

13.

The algorithm for checking balanced delimiters using a Stack is:

1. Create an empty Stack

2. Scan through the String and for each symbol follow the below rules

2.1 If the character being considered is an opening delimiter (opening paranthesis or brackets) then push this character to the stack

2.2 If the character being considered is a closing delimiter (closing paranthesis or brackets) then pop the top element of the stack to see if it matches the opening delimiter from the stack. If the stack is empty or the top element of stack do not match the closing delimiter, print "Imbalanced detected" and exit . If it matches the delimiters then continue with the next character

2.3 Any other characters are ignored.

3. After scanning the input string , if the Stack is not empty, print "Imbalanced detected" and exit else print "Balanced delimiters".

4. Exit

Given Input string : "(<[()>])"

Let us create a stack s, to be empty

Iteration 1:

Input Character = '('

Since it is an starting delimiter, we push it to the stack

Stack :

top : ( => NULL

Iteration 2:

Input Character = '<'

Since it is an starting delimiter, we push it to the stack

Stack:

top: < => ( => NULL

Iteration 3:

Input character = '['

Since it is an starting delimiter, we push it to the stack

Stack:

top: [ => < => ( => NULL

Iteration 4:

Input character = '('

Since it is an starting delimiter, we push it to the stack

Stack:

top: ( = > [ => < => ( => NULL

Iteration 5:

Input character = ')'

Since it is a closing delimiter, we pop the top element from stack and check if it matches this closing delimiter

Top element = '('

Since Input character and top element matches , we continue

Stack :

top: [ => < => ( => NULL

Iteration 6:

Input character = '>'

Since it is a closing delimiter, we pop the top element from stack and check if it matches this closing delimiter

Top element = '['

Since Input character and Top element of the stack do not match ,we print "Imbalanced is detected" and exit.

Stack:

top: < => ( => NULL

At the time of detection of imbalance, character being considered in input string is '>' and the character being considered from the stack is '['

Stack contents :

top : < => ( => NULL (after removal of the top character)