This post is completed by 3 users

  • 0
 Add to List
Medium

9. Valid or Well Formed Parentheses | Part - 1

Objective: You have been asked to write an algorithm to find Whether Given the Sequence of parentheses is 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

Examples: 

  {{{{}}}}{}{}{}{{{}}} well formed ? - true
  {{{{}}}}{}{}{}{{{{}}} well formed? - false
  {}{ well formed? - false
  }{ well formed? - false
  {{{{{{{{}}}}}}}} well formed? - true

Click here to read about - Multiple Valid parentheses

Approach:

  1. Idea is to have two counters, one for open parentheses '{' and one for close '}'
  2. Read one character at a time and increment one of the counters
  3. If any given point of time count of close parentheses is greater than the open one, return false
  4. If at the end both counters are equal, return true

 

Output

{{{{}}}}{}{}{}{}{}{}{}{}{}{}{{{}}} well formed ? :true
{{{{}}}}{}{}{}{{}{}{}{}{}{}{}{{{}}} well formed ? :false
{}{ well formed ? :false
}{ well formed ? :false
{{{{{{{{}}}}}}}} well formed ? :true

Related Problems: