Valid Brackets – Part 2 | Stack Method

Objective: Given a string containing just the characters ( , ) determine if the input string is valid.

Example:

()()(()(()))() valid: true
)()()( valid: false
 ()()) valid: false

Approach:

Earlier we discussed the solution which keeps the count of open and closed parentheses. In this solution we will solve this problem using stack.

Using Stack:

  • Initialize a Stack.
  • Iterate the input string, one character at a time.
  • Check if character is open bracket ‘(‘, if yes then push closed bracket ‘)’ to stack.
  • Else check if character is close bracket ‘)‘, if yes then
    • Check if stack is empty, if yes return false.
    • Else if stack is not empty, pop from stack and move to next character in input.
  • If at the end stack is empty, return true else return false.
  • See the image below for more understanding.
Valid Parentheses using stack.png

Complete Code:

Output:

is input ()()(()(()))() valid: true
is input )()()( valid: false
is input ()()) valid: false

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: