UVa 112 : Tree Summing

問題リンク：Tree Summing

問題概要：
integer I と２分木がLISP S-expressionでtreeとして与えられる
treeのルートから葉までの値の和がIとなるならyes,ならないならnoと出力せよ

解法：
構文解析を行う
treeの値がマイナスである事があるので注意すること
つまり、(-10()(2()()))みたいなtreeもあり得る

コード：

#include<iostream>
#include<sstream>
#include<cmath>
#include<vector>
#include<algorithm>
#include<cassert>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)

using namespace std;

int I;
bool found;
string tree;
int cur;

void dfs(int cost)
{
  assert(tree[cur] == '(');
  cur++;
  int value = 0;
  bool minus = false;
  if(tree[cur] == '-')
    {
      minus = true;
      cur++;
    }
  while('0' <= tree[cur] && tree[cur] <= '9')
    {
      value = value * 10 + (tree[cur]-'0');
      cur++;
    }
  if(minus)value*=-1;
  assert(tree[cur] == '(');

  bool in = false;
  if(tree.substr(cur,2) != "()")
    {
      in = true;
      dfs(cost+value);
      cur++;
    }
  else cur += 2;

  if(tree.substr(cur,2) != "()")
    {
      in = true;
      dfs(cost+value);
      cur++;
    }
  else cur += 2;

  if(!in)
    {
      if(cost+value == I)
	{
	  found = true;
	}
    }

}

int main()
{
  while(cin >> I)
    {
      cur = 0;
      found = false;
      tree.clear();
      cin.ignore();
      string s;
      int stk = 0;
      while(getline(cin,s))
	{
	  tree += s;
	  rep(i,s.size())
	    {
	      if(s[i] == '(')stk++;
	      else if(s[i] == ')')stk--;
	    }
	  if(stk == 0)break;
	}
      string pre = tree;
      tree.clear();
      rep(i,pre.size())if(pre[i] != ' ')tree += pre[i];
      //cout << "tree : " << tree << endl;

      if(tree == "()")
	{
	  cout << "no" << endl;
	  continue;
	}

      dfs(0);

      cout << (found?"yes":"no") << endl;

    }
  return 0;
}