Balanced parentheses using standard C++

Question

Here is a small program for checking if the parentheses are balanced or not. I am new to the standard library, and this is my first program. How can I improve it? Any kind of modifications or alternatives and suggestions are welcomed.

#include <iostream>
#include <stack>
#include <string>
using namespace std;
bool checkParentheses(string str, stack<char> s) {
 int flag = 0;
 char top;
 for(int i=0;i<str.length();i++) {
 if(str[i] == '(' || str[i] == '{' || str[i] == '[') {
 s.push(str[i]);
 }
 else {
 if(s.empty()) {
 flag = 1;
 break;
 }
 else {
 top = s.top();
 }
 if(str[i] == ')' && top == '('){
 s.pop();
 }
 else if(str[i] == '}' && top == '{'){
 s.pop();
 }
 else if(str[i] == ']' && top == '['){
 s.pop();
 }
 else {
 flag = 1;
 break;
 }
 }
 }
 if(s.empty() && flag == 0) {
 return true;
 }
 else if (flag == 1) {
 return false;
 }
 else {
 return false;
 }
}
int main() { 
 stack <char> s;
 string str;
 cout << "Enter an expression with brackets: " << endl;
 cin >> str;
 cout << str << endl;
 if(checkParentheses(str, s)) {
 cout << "Expression is valid!" << endl;
 }
 else {
 cout << "Expression is not valid" << endl;
 }
}

• Claus Jørgensen: And since we're doing a code review: Remember consistent indention and bracket style. Just keep focus on it until it's muscle memory.
• dsaharia: @ClausJørgensen what is wrong with bracket style? I'll work on the indentation.

Answer 1

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

• yuri: Is there an actual benefit to using = in conjunction with brace-init or is it just due to habit/readability?
• Toby Speight: Just habit - the = can be omitted for exactly equivalent code.
• dsaharia: I haven't learned about maps yet. But thank you very much, I'll clean up my code. I'll post any doubts.
• dsaharia: I could use using namespace std::cout; right? @T
• Toby Speight: If you mean using std::cout;, then yes, that's less bad (but I'd recommend you reduce its scope to just within main()). It's using namespace that can bring big surprises.

Answer 2

• using namespace std; may seem fine for small projects, but can cause problems later so it's best to avoid it.

• Prefer to output "\n" instead of std::endl. std::endl will also flush the output stream, which is usually unnecessary.

• We should check that reading user input from std::cin didn't fail. We can do this by testing std::cin.fail() after reading the string.

• The stack variable isn't used outside of the checkParentheses function, so it should be declared inside the function.

• The str variable can be passed by const-reference, instead of by value (to avoid an unnecessary copy).

• The flag variable has two possible values signifying true or false. The bool type would thus be more appropriate than an int.

• There is no need to maintain a top variable. We can just use s.top() where necessary. Note that std::stack.top() returns by reference, so there is no need to worry about an extra copy, if that's why you're avoiding it.

• We should use the appropriate index type for indexing into a container (in the for loop). This is std::size_t (or std::string::size_type), not int.

• However, it's actually much easier to use a range-based for loop:

  for (auto const& c : str) { ... }
  

• There is quite a lot of redundancy in the return statements at the end (the else and else if both return false). We could simplify the condition to return (s.empty() && flag = 0);

---

Given the above, we would end up with something more like:

#include <cstdlib>
#include <iostream>
#include <stack>
#include <string>
bool checkParentheses(std::string const& str) {
 std::stack<char> s;
 for (auto const& c : str) {
 if (c == '(' || c == '{' || c == '[') {
 s.push(c);
 }
 else if (c == ')' || c == '}' || c == ']')
 {
 if (s.empty())
 return false;
 if (c == ')' && s.top() == '(') {
 s.pop();
 }
 else if (c == '}' && s.top() == '{') {
 s.pop();
 }
 else if (c == ']' && s.top() == '[') {
 s.pop();
 }
 else {
 return false;
 }
 }
 }
 return s.empty();
}
int main() {
 std::cout << "Enter an expression with brackets: \n";
 std::string str;
 std::cin >> str;
 if (std::cin.fail()) {
 std::cout << "Invalid input!\n";
 return EXIT_FAILURE;
 }
 std::cout << str << "\n";
 std::cout << "Expression is " << (checkParentheses(str) ? "valid!" : "not valid") << "\n";
 return EXIT_SUCCESS; // (done implicitly if this isn't here)
}

• L. F.: Doesn't your code consider a string like ()] balanced?
• Konrad Rudolph: When handling interactive user input you need std::endl instead of "\n" or flush the stream otherwise. Your code may work but it also may not. Of course bettert yet would be not to perform interactive input handling at all, since the C++ standard streams aren’t really suited for that.
• N. Shead: @KonradRudolph According to en.cppreference.com/w/cpp/io/cin: "Once std::cin is constructed, std::cin.tie() returns &std::cout [...] This means that any formatted input operation on std::cin forces a call to std::cout.flush() if any characters are pending for output." So no, the stream flushes automatically if needed.
• Konrad Rudolph: @N.Shead Good to know. I know for sure that stdlibc++ didn’t reliably do this, not so long ago. Must have been a bug then.
• Konrad Rudolph: @dsaharia Use "\n" unless you explicitly want to flush the stream (and, as explained in N. Shead’s comment, this isn’t necessary here). x << std::endl is exactly equivalent to x << '\n' << std::flush;: en.cppreference.com/w/cpp/io/manip/endl — In most code you’ll find in the wild, std::endl is used unnecessarily.