Balanced Smileys

問題

:) やら :( やらが含まれる文字列で、カッコの対応が付いているかチェックせよ。

考え方

• 考慮すべきカッコに種類があるわけではない。
• Smiley が関係無い場合、カッコを潜っている段数 n を見るだけでいいテンプレ問題が有るのを思い出す。
  • 途中は n>=0 をキープし、最後に n==0 となれば OK
• カッコの前に : があったら Smiley になる可能性があるから分岐させればいい。
• こんなときは DP すると良さ気。
• 最初のカッコの時だけ : チェックしない例外とか面倒だからスペース入れておこ…

コード

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <string>
using namespace std;

bool Solve() {
  string line;
  getline(cin, line);
  line = ' ' + line;
  set<int> a, b;
  set<int>* st = &a, * st2 = &b;
  st->insert(0);
  for (int i = 0; i < line.size(); ++i) {
    if (line[i] != '(' && line[i] != ')')
      continue;
    st2->clear();
    set<int>::iterator itr;
    if (line[i] == '(') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	st2->insert(*itr + 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    } else if (line[i] == ')') {
      for (itr = st->begin(); itr != st->end(); ++itr)
	if (*itr > 0)
	  st2->insert((*itr) - 1);
      if (line[i - 1] == ':')
	for (itr = st->begin(); itr != st->end(); ++itr)
	  st2->insert(*itr);
    }
    swap(st, st2);
  }

  return (st->find(0) != st->end());
}

int main(void) {
  string line;
  getline(cin, line);
  const int n = atoi(line.c_str());
  for (int i = 0; i < n; ++i) {
    cout << "Case #" << (i + 1) << ": "
	 << (Solve() ? "YES\n" : "NO\n");
  }
  return 0;
}