Find Whether Given Sequence of parentheses are well formed.

by · July 23, 2014

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Tags:

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

    Wonderful site, thanks for sharing !!

  • Chandra Gopalaiah

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

  • Rahul Batheja

    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

Follow:

Select level

Beginner
Intermediate
Expert

Follow me on Twitter

%d bloggers like this: