1. 


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #112 (Tree Summing)
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=48
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.4, 06/29/2009
*
* Status : Accepted
* Runtime: 0.496
*/

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

class Main
{
public static void main(String[] args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder builder = new StringBuilder();

for(String line = reader.readLine(); line != null; line = reader.readLine()) //read all the user lines
builder.append(line);

String file = builder.toString();
file = file.replaceAll(" ", ""); //delete all user blanks

builder = new StringBuilder();

for(int i=0; i<file.length();) //get all the statements
{
int start = i;
while(isDigit(file.charAt(i++))); //search number we're looking for in tree first argument for each user input

Digit.wanted = Integer.parseInt(file.substring(start,--i));
Digit.isFound = false;

start = i;
i++;

int bracket = 1;

while(bracket > 0) //search user bracket construction by counting the brackets
{
char a = file.charAt(i++);
if(a == '(')
bracket++;
if(a == ')')
bracket--;
}

Digit root = parseTree(file.substring(start,i),Digit.wanted<0); //parse Tree in an object modeled tree
Digit.wanted = Math.abs(Digit.wanted);
if(root != null && root.SumUp(root.getValue()) == Digit.wanted) //call SumUp from root to find the sum to the leaves of tree
builder.append("yes\n");
else
builder.append("no\n");

}

System.out.print(builder.toString());

}

public static Digit parseTree(String word, boolean negative)
{
int marker = 0;
Stack<Digit> work = new Stack<Digit>(); //Stack for parsing
Digit root = null;
for(int a = 0; a < word.length(); a ++)
{
char ch = word.charAt(a);
if(ch == '(') //find first bracket
{
ch = word.charAt(++a);

if(isDigit(ch)) //next must be a number
{
marker = a;
while(isDigit(ch)) //have more than one digit??
ch = word.charAt(++a);

int num = Integer.parseInt(word.substring(marker,a)); //value of knot
Digit val;

if(negative) //build new knot with the absolute value of knot
val = new Digit(-1*num);
else
val = new Digit(num);

if(!work.empty()) //if is not root? Append new knot at the last knot on stack
{
Digit last = work.pop();
last.append(val);
work.push(last);
}
else
root = val;
work.push(val); //push new knot on stack
a --;
}
}
if(word.charAt(a-1) != '(' && ch == ')' && !work.isEmpty())
{
work.pop(); //go to backwards to an higher level implemented by dropping one element of stack
}
}

return root;
}

public static boolean isDigit(char a)
{
return ((a >= '0' && a <= '9') || a == '-');
}
}

class Digit //Class for object modeled tree
{
private final int value;
private final ArrayList<Digit> Members;
public static int wanted = 0;
public static boolean isFound = false;
public Digit(int value)
{
this.value = value;
this.Members= new ArrayList<Digit>();
}

public int getSize()
{
return this.Members.size();
}

public boolean isEmpty()
{
return this.Members.isEmpty();
}

public int getValue()
{
return this.value;
}
public void append(Digit next)
{
this.Members.add(next);
}

public String toString() //prints the tree complete in recursive way
{
StringBuilder bu = new StringBuilder();
bu.append(this.value);
bu.append(" knows: [");
for(Digit a : this.Members)
bu.append(a.toString());
bu.append("]\n");
return bu.toString();
}

public int SumUp(int sum) //sum up all the knot values of this knot to the leave. If found wanted, method will return
{
int new_sum = sum;
if(this.isEmpty() && sum == wanted)
return sum;
for(Digit part: Members)
{
new_sum = sum + part.getValue();
if(!part.isEmpty() || new_sum != wanted)
new_sum = part.SumUp(new_sum);
if((part.isEmpty() && new_sum == wanted) || Digit.isFound)
{
Digit.isFound = true;
return new_sum;
}
}
return new_sum;
}
}