Justify if a string consists of valid parentheses
You are given an array of strings. Each of these strings is made up of bracket characters only :
'(', ')', '{', '}', '[', ']'.
Programming languages utilize these brackets in balanced pairs, so the following rules are always followed :
- Every opening bracket has a corresponding closing bracket :
'('with')','{'with'}', and'['with']'. - Two brackets form a pair if they have no open bracket of any type between them.
- For example:
'[}]'is invalid,'[{}]'is valid. - The closing bracket of a pair must be of the same type as the opening bracket, e.g.
'( )'is valid, but'[ )'is not valid.
Your task is to determine if of the strings of brackets in the input array are valid or invalid by these criteria.
Sample Input / Output:
"([)]" // false "()" // true
Logic :
- Declare a character stack S.
- Traverse the string expression.
- If the current character is an opening bracket
( or { or [then push it to stack. - 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 - At the end of the traversal, if there is some opening bracket left in stack then the string is “not balanced”. Hence, return false.
Solution :
Approach 1 :
Approach 2 : Using Map data structure. Map is a new data structure introduce in ES6. There is a subtle difference between these two data structures. More details doing the comparison between these two data structures can be found here.