C++ program for checking a string for balanced ()s, {}s and []s

Question

So here's my problem:

I'm supposed to write a c++ program that checks a string to be balanced. So far I have the code working to make sure that it has the same number of ('s and )'s (the same with ['s and {'s). The problem is that this works for almost everything, but it doesn't work for strings where the {'s, ('s and ['s all get mixed up.

For example: "{ { [ ( ) ] } ( ) }" comes back as balanced (true) as it should. However, "{ ( [ ] } )" comes back true, but it shouldn't.

What are some ideas in the logic and/or code that would check for when they're out of order?

Thanks for any help!

In case it helps, my code follows:

bool ExpressionManager::isBalanced(string expression)
{
//remove whitespace
string edited;
for(int i = 0; i < expression.length(); i++)
{
    if(expression[i] == ' ')
    {
        continue;
    }
    else
    {
        edited += expression[i];
    }
}
expression = edited;

//set up brckets 
string brackets;

for(int i = 0; i < expression.length(); i++)
{
    if (expression.at(i)=='(')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='[')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='{')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)=='}')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)==']')
    {
        brackets += expression.at(i);
    }
    if (expression.at(i)==')')
    {
        brackets += expression.at(i);
    }
}

int parenbal = 0;
int brackbal = 0;
int mustachebal = 0;

    for (int i = 0; i<(brackets.size());i++)
    {

        if(brackets[i]=='(')
            parenbal++;
        if(brackets[i]=='[')
            brackbal++;
        if(brackets[i]=='{')
            mustachebal++;

        if(brackets[i]==')')
            parenbal--;
        if(brackets[i]==']')
            brackbal--;
        if(brackets[i]=='}')
            mustachebal--;
    }

    bool isbalanced = false;

    if ((mustachebal==0)&&(brackbal==0)&&(parenbal==0))
    {
        isbalanced = true;
    }

    //check for brackets mixed up with other stuff.


return isbalanced;
}

Answer 1

If you employ a Stack to store those tokens, then you are always looking for the closing-counterpart corresponding to the one on the top of the stack or an open-token.

The flow would be

• If the token is an open token, push it onto the stack.
• If the token is a close token, check if the top of the stack is the corresponding open-token. If it is, then pop the stack as you found them balanced. If it is not, then it's an error.