UVa 112 - Tree Summing

// UVa 112 - Tree Summing

#include <iostream>
#include <stack>
#include <stdio.h>
#include <vector>
using namespace std;

struct node {
	int id;
	int left, right;
	int parent;
	int value;
	bool null;
};

vector<node> v;

int addChild(int parentId) {
	node newNode;
	newNode.id = v.size();
	newNode.parent = parentId;
	newNode.left = -1;
	newNode.right = -1;
	newNode.value = 0;
	newNode.null = true;
	v.push_back(newNode);

	if (parentId != -1) {
		if (v[parentId].left == -1)
			v[parentId].left = newNode.id;
		else
			v[parentId].right = newNode.id;
	}

	return newNode.id;
}

int readTree() {
	v.clear();
	stack<int> parentStack;
	int currentNode = addChild(-1);
	int sign = +1;

	while (true) {
		char c = getchar();
		if (c == '(') {
			sign = +1;
			int newNode = addChild(currentNode);
			parentStack.push(currentNode);
			currentNode = newNode;
		} else if (c == ')') {
			currentNode = parentStack.top();
			parentStack.pop();
			if (parentStack.empty())
				break;
		} else if ('0' <= c && c <= '9') {
			v[currentNode].value = v[currentNode].value * 10 + sign * (c - '0');
			v[currentNode].null = false;
		} else if (c == '-') {
			sign = -1;
		}
	}
	return 0;
}

bool dfs(int nodeId, int sum) {
	sum += v[nodeId].value;

	if (v[nodeId].left != -1) {
		bool b = dfs(v[nodeId].left, sum);
		if (b)
			return true;
	}
	if (v[nodeId].right != -1) {
		bool b = dfs(v[nodeId].right, sum);
		if (b)
			return true;
	}
	if (v[nodeId].left != -1 && v[v[nodeId].left].null && v[nodeId].right != -1 && v[v[nodeId].right].null)
		return sum == 0;
	else
		return false;
}

int main() {
	int goal;
	while (cin >> goal) {
		int rootId = readTree();
		string answer = dfs(rootId, -goal) ? "yes" : "no";
		cout << answer << endl;
	}
	return 0;
}