C++ program for checking a string for balanced ()s, {}s and []s
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.
user1311736
Updated on June 27, 2022Comments
-
user1311736 almost 2 years
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; }
-
Luc Danton over 11 yearsA default constructed
std::string
is perfectly fine. -
YakovL over 7 yearsHave you tested that for the example in the post (
{ ( [ ] } )
)? Looks like your code doesn't deal with that issue.