Programming Interview Questions 14: Check Balanced Parentheses

Given a string of opening and closing parentheses, check whether it’s balanced. We have 3 types of parentheses: round brackets: (), square brackets: [], and curly brackets: {}. Assume that the string doesn’t contain any other character than these, no spaces words or numbers. Just to remind, balanced parentheses require every opening parenthesis to be closed in the reverse order opened. For example ‘([])’ is balanced but ‘([)]’ is not.

This is another data structure question, if we use the correct one it’s pretty straightforward. We scan the string from left to right, and every time we see an opening parenthesis we push it to a stack, because we want the last opening parenthesis to be closed first. Then, when we see a closing parenthesis we check whether the last opened one is the corresponding closing match, by popping an element from the stack. If it’s a valid match, then we proceed forward, if not return false. Or if the stack is empty we also return false, because there’s no opening parenthesis associated with this closing one. In the end, we also check whether the stack is empty. If so, we return true, otherwise return false because there were some opened parenthesis that were not closed. Here’s the code:

def isBalanced(expr):
    if len(expr)%2!=0:
        return False
    opening=set('([{')
    match=set([ ('(',')'), ('[',']'), ('{','}') ])
    stack=[]
    for char in expr:
        if char in opening:
            stack.append(char)
        else:
            if len(stack)==0:
                return False
            lastOpen=stack.pop()
            if (lastOpen, char) not in match:
                return False
    return len(stack)==0

This is a simple yet common interview question that demonstrates correct use of a stack.

VN:F [1.9.22_1171]
Rating: 7.8/10 (54 votes cast)
Programming Interview Questions 14: Check Balanced Parentheses, 7.8 out of 10 based on 54 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • ilker

    Arden,

    I think you assumed that the expression always starts with an “opening”. Think about the case where the exp: a * (b+c).

    Then this would return false when it sees the first non-opening char (‘a’) because of statement in else;
    if len(stack)==0:
    return False

    • Arden

      Hi Ilker. I actually assumed that the expression will only consist of parentheses. So no letters or numbers, just opening and closing parentheses.

  • Justin

    Hey, instead of stack, why don’t you simply keep the 3 variables for count of opening parenthesis of the three types, as whenever a closing brace comes, count of the corresponding opening brace encountered before this should be >0 (if not, return false) and then you decrease the count. At the end, the count of all three variables must be zero else return false.

    • http://benblack86.tumblr.com/ Benjamin Black

      That doesn’t make sure the parenthesis are balanced. “([)]” would pass your algorithm.

  • Geethu

    Justin,

    You cannot do that as the expression : [ { ] } is not balanced but if u go by checking the number of parenthesis it will display the output as balanced expression.
    So you should go by stack.

  • Ankit

    Using stack definately serves the purpose…

    But we will require additional space for the stack…

    Instead if we observe, in a valid string , the first half and second half are mirror images of each other…

    Hence we can compare the first character and the last character..They have to be matched i.e ‘(‘ and ‘)’ or ‘[‘ and ‘]’ or ‘{‘ and ‘}’..

    This can be done as follows :

    #include
    #include
    #define true 1
    #define false 0

    int isBalanced(char str[]);

    int main()
    {
    char str[]=”([{}])”; //Change this input as per need
    printf(“%d”,isBalanced(str));
    getch();
    }

    int isBalanced(char str[])
    {
    int len,i,j;
    len=strlen(str);
    if((len%2) == 1)
    {
    return false;
    }

    j=len-1;
    for(i=0;i<len/2;i++)
    {
    if(str[i]=='(' && str[j]!=')')
    {
    return false;
    }
    else if(str[i]=='[' && str[j]!=']')
    {
    return false;
    }
    else if(str[i]=='{' && str[j]!='}')
    {
    return false;
    }
    j–;
    }
    return true;
    }

    • x

      layout of the code makes it difficult to read. Not sure whether your code will handle ()[], which is a valid expression. Also, it is not a mirror image…

  • sudosuhan

    generate all balanced parentheses using :-

    //sudosuhan

    #include

    #include

    #include

    #define MAX_SIZE 200

    void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3);

    void printParenthesis(int n1 , int n2 , int n3 )

    {

    if(n1 > 0 || n2 > 0 || n3 > 0)

    _printParenthesis(0, n1, 0, 0, n2, 0, 0, n3, 0, 0);

    return;

    }

    void _printParenthesis(int pos, int n1, int open1, int close1, int n2, int open2, int close2, int n3, int open3, int close3)

    {

    static char str[MAX_SIZE];

    if(close1 == n1 && close2 == n2 && close3 == n3 )

    {

    printf(“%s n”, str);

    return;

    }

    else

    {

    bool run1 = open1 > close1;

    bool run2 = open2 > close2;

    bool run3 = open3 > close3;

    if(run3)

    {

    str[pos] = ‘)’;

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3, close3+1);

    if(open3 < n3)

    {

    str[pos] = '(';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);

    }

    }

    else if(run2 && !run3)

    {

    str[pos] = '}';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2+1, n3, open3, close3);

    if(open3 < n3)

    {

    str[pos] = '(';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);

    }

    if(open2 < n2)

    {

    str[pos] = '{';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);

    }

    }

    else if(run1 && !run2 && !run3)

    {

    str[pos] = ']';

    _printParenthesis(pos+1, n1, open1, close1+1, n2, open2, close2, n3, open3, close3);

    if(open3 < n3)

    {

    str[pos] = '(';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);

    }

    if(open2 < n2)

    {

    str[pos] = '{';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);

    }

    if(open1 < n1)

    {

    str[pos] = '[';

    _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);

    }

    }

    else if(!run1 && !run2 && !run3)

    {

    if(open3 < n3)

    {

    str[pos] = '(';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2, close2, n3, open3+1, close3);

    }

    if(open2 < n2)

    {

    str[pos] = '{';

    _printParenthesis(pos+1, n1, open1, close1, n2, open2+1, close2, n3, open3, close3);

    }

    if(open1 < n1)

    {

    str[pos] = '[';

    _printParenthesis(pos+1, n1, open1+1, close1, n2, open2, close2, n3, open3, close3);

    }

    }

    }

    }

    /* driver program to test above functions */

    int main()

    {

    int n1, n2, n3;

    n1 = 6;

    n2 = 1;

    n3 = 1;

    printParenthesis(n1, n2, n3);

    return 0;

    }

  • http://erikzaadi.com/ Erik Zaadi

    I don’t really see the value of using set here.
    One variable less and a bit more pythonic (IMHO):

    def test_balanced_parantheses(string_to_check):

    if len(string_to_check) % 2 != 0:

    return False

    pairs = {

    “}”: “{“,

    “]”: “[“,

    “)”: “(“,

    }

    openers = []

    for s in string_to_check:

    if s in pairs.values():

    openers.append(s)

    elif not pairs.has_key(s):

    return False #not valid char

    elif pairs[s] == openers[-1]:

    openers.pop()

    return len(openers) == 0

  • Mythri Nagaraju

    Also doesn’t work for ({[]})

  • Ayushi

    I have written code in C: http://cyberlingo.blogspot.com/2015/08/order-of-parenthesis.html
    It works for all test cases mentioned in comments as well