Raphael is now back after a long break from his duties. His colleague, a math teacher, has given him a string consisting of parentheses, i.e '(' and ')'. He calls such a string balanced if every opening parenthesis of the string has a corresponding closing parenthesis and vice versa. For example, the string "()()(()())" is balanced, whereas "(()))()()" is not.

Raphael's friend has given him a string of parenthesis. Help him figure out whether this string is balanced or not!

Hint: You may find it helpful to use stacks.

`(()())())`

`(()())()) is not balanced.`

`((()))()`

`((()))() is balanced.`

There are two different ways of tacking this problem. Note that a string of parentheses is balanced if and only if in any initial segment, the number of `(`

's is larger than the number of `)`

's. This solution does not require using stacks.

However, you can achieve exactly what the above solution does using a stack of characters, let's call it `A`

. When you see a `(`

, you do `A.push('(')`

. When you see a `)`

, you try doing `A.pop()`

. If you cannot pop `A`

, that means that in this initial segment, the number of `(`

's was smaller than the number of `)`

's, and so the string is unbalanced. Otherwise if after you completed your traversal of the string, `A`

is still nonempty, this means that you had more `(`

's than `)`

's. And finally, if the stack is empty, then your string is actually balanced. Congrats!

I will write two functions isBalanced1() and isBalanced2() demonstrating these two algorithms.

#include <iostream> #include <stack> bool isBalanced1(string s) { int numOpening = 0; int numClosing = 0; // Counters for number of ('s and )'s. for(auto c:s) // Equivalent to python "for c in s:", note that c iterates through the chars of s, and not the index. { numOpening += (c=='('); // c=='(' is 1 iff c is '('. This is equivalent to saying "if(c=='(') numOpening++;" numClosing += (c==')'); // Same explanation as above if(numOpening < numClosing) return false; } // If we arrive here, that means numOpening >= numClosing for all initial segments. if(numOpening == numClosing) return true; else return false; } bool isBalanced2(string s) { stack<char> A; for(auto c:s) { if(c=='(') A.push(c); else if(A.empty()) // If you encounter a ')' but you cannot pop, then you are not balanced. return false; else A.pop(); } return A.empty(); // If stack is empty here, string is balanced. } int main() { string s; std::cout<<"Enter the string of parentheses: "; std::cin>>s; std::cout<<"isBalanced1(): "<<isBalanced1(s)<<endl; std::cout<<"isBalanced2(): "<<isBalanced2(s)<<endl; return 0; }