342 views
0 votes
0 votes

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
image:2q.png
What are the missing statements that should be in place of S1, S2 and S3?( Marks: 0.00 )

  1.  S1: s.empty()
    S2: s.push(arr[i])
    S3: s.pop()
  2.  S1: arr[i]==’)’ && s.top()==’)’
    S2: s.pop();
    S3: s.push(arr[i])
  3.   S1: arr[i]==’)’ && s.empty()
    S2: s.pop();
    S3: s.push(arr[i]);
  4.   S1: arr[i]==’) && s.top()==’)’ 
    S2: s.push(arr[i])
    S3: s.pop()

1 Answer

Best answer
1 votes
1 votes

Option 3 is the Answer.

It is not difficult to see that this problem can be solved using a stack, because in a balanced parentheses sequence, the first ')' always matches with the last '(' before it. While scanning the given sequence from left to right, if we keep storing the '(' in the stack, then whenever we encounter a ')', the '(' stored on the top of stack will always be its matching parentheses.

So, the logic to solve this problem is simple -

Scan the array one character at a time. Until the array is completely scanned, every time we check if the scanned char is '(' or ')'.
If, scanned char is '(', then
{ Push '(' to stack }
When ')' will be scanned, its matching '(' should be on the stack top. So, first we need to check if there even exists a '(' exists in the stack. Hence,
If, scanned char is ')' and stack is not empty, then
{ Pop '(' from stack }
If, scanned char is ')' and stack is empty, then
{ Stop scanning because the scanned ')' does not have a matching '('
   Print (unbalanced sequence)
}
After the array is completely scanned, the sequence can be said to be balanced only if all the '(' have been matched, i.e., all '(' have been popped and the stack is empty. So,
If, stack is empty, then
{ Print (sequence is balanced) }
Else
{ There exists an unbalanced '(' in the stack. 
   Print (unbalanced sequence)
}

Notice the correspondence between the above logic and the given code. The 3 highlighted conditions in the above logic are exactly the 3 conditions in the 'for' loop of the given code, but are in reverse order. By matching the corresponding conditions, we get the following mapping -
S1 = 3rd condition in above logic, i.e, scanned char is ')' and stack is empty OR arr[i] == ’)’ && s.empty().
S2 = body of 2nd condition in above logic, i.e, Pop '(' from stack OR s.pop();
S3 = body of 1st condition in above logic, Push '(' to stack OR s.push(arr[i]);

selected by

No related questions found