This post is completed by 1 user
|Add to List|
Valid Brackets – Part 2 | Stack Method
Objective: Given a string containing just the characters ( , ) determine if the input string is valid.
()()(()(()))() valid: true )()()( valid: false ()()) valid: false
Earlier we discussed the solution which keeps the count of open and closed parentheses. In this solution we will solve this problem 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.
is input ()()(()(()))() valid: true is input )()()( valid: false is input ()()) valid: false