Balanced.java

import java.util.*;
import java.io.*;
import static java.lang.Math.*;

//2013 Facebook Hacker Cup Qualification Round
//Problem 2: Balanced Smileys https://www.facebook.com/hackercup/problems.php?pid=403525256396727&round=185564241586420

public class Balanced {
    static Scanner in;

    public static void main(String[] args) throws Exception {
		in = new Scanner(new File("Balanced.in"));
		new Balanced().run();
	}

	void run() {
		int t = in.nextInt(), counter = 0;
		in.nextLine();

		for (int i = 0; i < t; i++)
			System.out.printf("Case #%d: %s%n", ++counter, solve(in.nextLine()) ? "YES" : "NO");
	}

	boolean solve(String line) {
		if (line.isEmpty() || (line.indexOf('(') < 0 && line.indexOf(')') < 0))
			return true;

		int matches = 0, smiles = 0, frowns = 0;

		for (int i=0; i<line.length(); i++) {
			char c = line.charAt(i);
			char prev = i > 0 ? line.charAt(i-1) : ' ';

			if (c == '(')
				matches++;

			if (c == ')')
				matches--;

			if (prev == ':' && c == ')')
				smiles++;

			if (prev == ':' && c == '(')
				frowns++;

			if (matches < 0 && smiles < abs(matches))
				return false;
		}

		if (matches > 0 && frowns < matches)
			return false;

		return true;
	}
}