Given a string containing just the characters
'('
, ')'
, '{'
, '}'
, '['
and ']'
, determine if the input string is valid.
The brackets must close in the correct order,
"()"
and "()[]{}"
are all valid but "(]"
and "([)]"
are not.
Approach: The idea is to use Stack and implement the following algorithm:
- if the current character is an opening bracket (of any type), push it to the stack and continue with the next character
- else if the current character is a closing bracket, following cases apply:
- if stack is empty - return error and exit
- else if the current character and the stack top forms matching parenthesis i.e. opening and closing brackets are of same type, pop the stack top and continue with the next character otherwise return error and exit
- Return error if the stack is not empty after all the characters are exhausted otherwise successful
Here is the link to the ideone solution : http://ideone.com/jzfJnv
0 comments:
Post a Comment