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.

Output:

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