This post is completed by 2 users

  • 0
Add to List
Beginner

346. 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-Multiple-Parentheses-using-stack.png

Output:

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