# Valid or Well Formed Parentheses | Part – 1

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:

 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
```

### 3 thoughts on “Valid or Well Formed Parentheses | Part – 1”

1. Wonderful site, thanks for sharing !!

Reply
2. 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();
}

Reply
3. 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

Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.