Objective: You have been asked to Write an algorithm to find Whether Given the Sequence of parentheses are well formed. This question was asked in the Amazon Interview.
Input: A String contains a sequence of parentheses
Output: true or false on whether parentheses are well formed or not
Approach:
- Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
- Read one character at a time and increment one of the counters
- If any given point of time count of close parentheses is greater than the open one, return false
- If at the end both counters are equal, return true
Example: { { } { } } – Well formed
{ { } { = Not well formed
Complete Code:
Output:
Is {{{{}}}}{}{}{}{}{}{}{}{}{}{}{{{}}} well formed ??? :true
Is {{{{}}}}{}{}{}{{}{}{}{}{}{}{}{{{}}} well formed ??? :false
Is {}{ well formed ??? :false
Is }{ well formed ??? :false
Is {{{{{{{{}}}}}}}} well formed ??? :true
Wonderful site, thanks for sharing !!
My Short and concise solution
public boolean isWellFormed(String strParentheses) {
if (strParentheses == null || strParentheses.length() == 0) {
return false;
}
Stack stack = new Stack();
for (int i=0; i<strParentheses.length();i++) {
Character c = strParentheses.charAt(i);
if (c == '}' && (stack.isEmpty() || stack.pop() != '{')) return false;
if (c == '{') stack.push(c);
}
return stack.isEmpty();
}
given solution is wrong as for the test case “}{ well formed ??? :false” it will return true. so we have to use an stack for this probliem