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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class WellFormedParentheses { | |
| public Boolean isWellFormed(String strParentheses) { | |
| if (strParentheses == null) { | |
| return false; | |
| } | |
| // 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 | |
| int openParenCounter = 0; | |
| int closeParenCounter = 0; | |
| for (int i = 0; i < strParentheses.length(); i++) { | |
| char x = strParentheses.charAt(i); | |
| if (x == '{') | |
| openParenCounter++; | |
| else if (x == '}') | |
| closeParenCounter++; | |
| if (closeParenCounter > openParenCounter) { | |
| return false; | |
| } | |
| } | |
| if (openParenCounter == closeParenCounter) | |
| return true; | |
| else | |
| return false; | |
| } | |
| public static void main(String args[]) { | |
| String x1 = "{{{{}}}}{}{}{}{}{}{}{}{}{}{}{{{}}}"; | |
| String x2 = "{{{{}}}}{}{}{}{{}{}{}{}{}{}{}{{{}}}"; | |
| String x3 = "{}{"; | |
| String x4 = "}{"; | |
| String x5 = "{{{{{{{{}}}}}}}}"; | |
| WellFormedParentheses w = new WellFormedParentheses(); | |
| System.out.println("Is " + x1 + " well formed ??? :" | |
| + w.isWellFormed(x1)); | |
| System.out.println("Is " + x2 + " well formed ??? :" | |
| + w.isWellFormed(x2)); | |
| System.out.println("Is " + x3 + " well formed ??? :" | |
| + w.isWellFormed(x3)); | |
| System.out.println("Is " + x4 + " well formed ??? :" | |
| + w.isWellFormed(x4)); | |
| System.out.println("Is " + x5 + " well formed ??? :" | |
| + w.isWellFormed(x5)); | |
| } | |
| } |
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