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

Sample Input

Sample Output

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