# Quiz 7

## Problem Statement:

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.

#### Sample Input

`(()())())`

#### Sample Output

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

#### Sample Input

`((()))()`

#### Sample Output

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

## Solution

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;
}
```