*** test series

Question

We want to write a code snippet to find if a given sequence of parentheses containing only ‘(‘ and ‘)’ is balanced one. The input character sequence is given in a character array arr[].

We have a stack which holds character value.
The standard operations in stack are
s.pop() - to pop an element from the top of the stack
s.top() - returns the top element of the stack if stack is not empty else returns an error (This operation does not pop any element )
s.push(x) - pushes values x to the top of stack
s.empty() - returns true if stack is empty else returns false

What are the missing statements that should be in place of S1, S2 and S3?
 a.)S1: s.empty()
S2: s.push(arr[i])
S3: s.pop() 

B)S1: arr[i]==’)’ && s.top()==’)’
S2: s.pop();
S3: s.push(arr[i]) 

 c) S1: arr[i]==’)’ && s.empty()
S2: s.pop()
S3: s.push(arr[i])

D) S1: arr[i]==’) && s.top()==’)’ 
S2: s.push(arr[i])
S3: s.pop()

Answer 1

Answer-C

Logic- For a given string, do foll- 

1. Do push operation on every "(",  until you see  a ")"  then goto step 2.

2. On seeing ")" do pop operation, until you see a "(" then goto step 1.

if(arr[i]==’)’ && s.empty()){

The case when there is nothing to pop[bcz s.empty() returns true] in step 2 and you  see a ")" in original string.

example of such unbalanced string--> "())" or more simple case is when original string is just-->  ")"

}

else if(arr[i]==’)’ && !s.empty()){

s.pop(); // Step 2 performed.

}

else if(arr[i]==’(’){

s.push(arr[i]); // Step 1 performed.

}

Comments

why not B)?

---

Because we are never pushing ")" onto the stack, hence this --> s.top()==’)’ is not possible.

---

what about the string(() how it will bw handled by above code

---

The code given in question doesnt handle this case, also none amongst the given options satisfy this.

Even then, this string will neither print "Balanced" nor "Unbalanced". Thus, the most probable correct answer is Option C which handles all other cases.