BalancedSmileys.cpp

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

typedef long long int int64;
typedef vector<int> VI;
#define REP(i,a,b) for (int i=int(a); i<int(b); ++i)

void solve(int caseNum) {
  char s[1024];
  gets(s);
  int n = strlen(s);

  bool smile = false;
  int mini = 0, maxi = 0;

  REP(i, 0, n) {
    char c = s[i];
    if (c==':') {
      smile = true;
    } else {
      if (c=='(') {
        maxi += 1;
        if (!smile) mini += 1;
      } else if (c==')') {
        mini = max(mini-1, 0);
        if (!smile) {
          maxi -= 1;
          if (maxi<0) break;
        }
      }
      smile = false;
    }
  }
  bool possible = (mini==0&&maxi>=0);
  printf("Case #%d: %s\n", caseNum, possible ? "YES" : "NO");
}

int main() {
  int caseCount;
  cin>>caseCount;
  {char s[1024]; gets(s);} // Eat the line break
  REP(i, 1, caseCount+1)
    solve(i);

  return 0;
}