Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find Whether Given Sequence of parentheses are well formed.

Objec­tive: You have been asked to Write an algo­rithm to find Whether Given the Sequence of paren­the­ses are well formed. This ques­tion was asked in the Ama­zon Interview.

Input: A String con­tains a sequence of parentheses

Out­put: true or false on whether paren­the­ses are well formed or not

Approach:

  • Idea is to have two coun­ters, one for open paren­the­ses ‘{‘ and one for close ’}’
  • Read one char­ac­ter at a time and incre­ment one of the counters
  • If any given point of time count of close paren­the­ses is greater than the open one, return false
  • If at the end both coun­ters are equal, return true

Exam­ple: { { } { } } – Well formed

{ { } { = Not well formed

Com­plete Code:

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

You may also like...

  • http://www.beefruit.net/ 水果禮盒

    Won­der­ful site, thanks for sharing !!

  • Chan­dra Gopalaiah

    My Short and con­cise solu­tion
    pub­lic boolean isWellFormed(String str­Paren­the­ses) {
    if (str­Paren­the­ses == null || strParentheses.length() == 0) {
    return false;
    }
    Stack stack = new Stack();
    for (int i=0; i<strParentheses.length();i++) {
    Char­ac­ter c = strParentheses.charAt(i);
    if (c == ’}’ && (stack.isEmpty() || stack.pop() != ‘{‘)) return false;
    if (c == ‘{‘) stack.push©;
    }
    return stack.isEmpty();
    }

  • Rahul Batheja

    given solu­tion is wrong as for the test case ”}{ well formed ??? :false” it will return true. so we have to use an stack for this probliem