Last Updated: 13 Oct, 2020
Valid Parentheses
Easy
Asked in companies
You're given a string 'S' consisting of "{", "}", "(", ")", "[" and "]" .
Return true if the given string 'S' is balanced, else return false.
For example:
'S' = "{}()".
There is always an opening brace before a closing brace i.e. '{' before '}', '(' before ').
So the 'S' is Balanced.
Input Format:
The first and only input line contains a string 'S'.
Output format :
The only line of output contains 'Balanced' or 'Not Balanced'.
Note:
You are not required to print anything explicitly. It has already been taken care of. Just implement the given function.
Approaches
Approach:
Make use of the stack. Traverse the string and push the current character in the stack if it is an opening brace. Else pop from the stack. If it is the corresponding starting brace for the current closing brace, then move to the next character of the string otherwise, return false.
If after complete traversal, if the stack is empty, then the string is balanced else, it is not balanced.
Algorithm:
- Declare a character stack.
- Now traverse the string.
1- If the current character is a starting bracket ( ‘(’ or ‘{’ or ‘[’ ), then push it to stack.
2- If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ), then pop from stack, and if the popped character is the matching starting bracket, then fine
else parenthesis is not balanced.
- After complete traversal, if there is some starting bracket left in the stack, then “not balanced”.
- Otherwise, the string is balanced.