USA: +1 (725) 712-1730 
Sign in
Balanced Smileys
Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go 🙁
Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.
A message has balanced parentheses if it consists of one of the following:
– An empty string “”
– One or more of the following characters: ‘a’ to ‘z’, ‘ ‘ (a space) or ‘:’ (a colon)
– An open parenthesis ‘(‘, followed by a message with balanced parentheses, followed by a close parenthesis ‘)’.
– A message with balanced parentheses followed by another message with balanced parentheses.
– A smiley face “:)” or a frowny face “:(”
Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.
Input
The first line of the input contains a number T (1 ≤ T ≤ 50), the number of test cases.
The following T lines each contain a message of length s that you got from John.
Python Solution should be:
def isBalanced(message):
minOpen = 0
maxOpen = 0
for i in xrange(len(message)):
if message[i] == ‘(‘:
maxOpen += 1
if i == 0 or message[i-1] != ‘:’:
minOpen += 1
elif message[i] == ‘)’:
minOpen = max(0, minOpen-1)
if i == 0 or message[i-1] != ‘:’:
maxOpen -= 1
if maxOpen < 0:
break
if maxOpen >= 0 and minOpen == 0:
return “YES”
else:
return “NO”
But its not working in the test harness. Attached is test case.
Expert Answer
#include<stdio.h>
#include<iostream>
#define SIZE 101
using namespace std;
int main()
{
int T;//the number of test cases
int max=0;
int min=0;
char message[SIZE];
scanf(“%d”,&T);
for(int k=1;k<=T;k++)
{
scanf(“%s”,message);
min=0;
max=0;for(int i=0;i<strlen(message);i++)
{
char c=message[i];
if(c=='(‘)
{
max++;
if(i==0 || message[i-1] != ‘:’)
min++;
}
else if(c==’)’)
{
min=max(0,min-1);
if(i==0 || message[i-1] !=’:’)
max–;
if(max<0)
break;
}
}
if(max>=0 && min==0)
cout<<“Case #”<<k<<“: “<<“YES”<<endl;
else
cout<<“Case #”<<k<<“: “<<“NO”<<endl;
}
system(“pause”);
return 0;
}
