Avoid using namespace std;
- it's a large namespace, and growing as new C++ standards appear. Bringing all its names into the global namespace completely obviates the benefits of namespaces, and in the worst case, can silently change the meaning of a program. Get used to using the (very short) namespace prefix std::
.
When we call checkParentheses()
, we have to provide a stack for it to use. If we're not using the stack outside of the function, then it could just be a local variable. Alternatively, we could choose to share it with the caller, so we could supply the input in chunks. If we did that, we'd want to pass it by reference, so that the changed stack can be passed into the next call.
We're not modifying the string argument, so it makes sense to pass it as a reference to const. When we use it, we're only interested in its characters in turn, so we can replace the for
loop with a range-based for
, eliminating the variable i
:
for (char c: str) {
if (c == '(' || c == '{' || c == '[') {
s.push(c);
}
else
We can eliminate the flag
variable, as whenever we set it, we immediately return:
if(s.empty()) {
return false;
}
Before we remove it, I'll just make a small observation on the final test of flag
, where we have two branches of an if
test that result in the same behaviour:
else if (flag == 1) {
return false;
}
else {
return false;
}
Obviously, that could just be replaced with
else {
return false;
}
In fact, we can simple replace that if
/else
with a single statement:
return s.empty() && !flag;
With the above changes, we've simplified it a bit:
bool checkParentheses(const std::string& str)
{
std::stack<char> s;
for (char c: str) {
if (c == '(' || c == '{' || c == '[') {
s.push(c);
} else {
if (s.empty()) {
return false;
}
char top = s.top();
if (c == ')' && top == '(') {
s.pop();
} else if (c == '}' && top == '{') {
s.pop();
} else if (c == ']' && top == '[') {
s.pop();
} else {
return false;
}
}
}
return s.empty();
}
We still have some quite repetitive code where we match a closing bracket against its opening one. We can make this simpler and also more flexible (so that we could match «
with »
, for example), by using a fixed map from opening to closing character:
static const std::map<char,char> pairs =
{ {'(', ')'},
{'{', '}'},
{'[', ']'} };
We can use this to replace the chained if
/else if
/else
by storing the expected closing character on the stack and then simply comparing:
if (pairs.count(c)) {
s.push(pairs.at(c));
} else {
if (s.empty() || s.top() != c) {
return false;
}
s.pop();
}
Finally, the presentation can be improved. Please be a bit more generous with space around operators - it really does make the code easier to read! The indentation looks wrong, but perhaps that's an artefact of how it was copied into Stack Exchange. If you used tabs for indentation, that can get corrupted (as SE has tab stops every 4 positions, rather than the normal 8).
Modified code
#include <map>
#include <stack>
#include <string>
bool checkParentheses(const std::string& str)
{
static const std::map<char,char> pairs =
{ {'(', ')'},
{'{', '}'},
{'[', ']'} };
std::stack<char> s;
for (char c: str) {
if (pairs.count(c)) {
s.push(pairs.at(c));
} else {
if (s.empty() || s.top() != c) {
return false;
}
s.pop();
}
}
return s.empty();
}