UVA 112 Tree Summing (SCU 1016, POJ 1145)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

bool possible;
int n, pos, posl;
string s;

struct node{
    int data;
    struct node* left;
    struct node* right;
};

struct node* newNode(int data)
{
    struct node* node = (struct node*) malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
return(node);
};

int toInt(string s)
{
    int ret;
    istringstream os(s);
    os>>ret;
return ret;
}

void makeTree(struct node* node, int sum)
{
    //left child
    while(s[pos]!='(' && pos<posl)
        pos++;
    pos++;
    string tmp="";
    while(s[pos]!=')' && s[pos]!='(' && pos<posl)
        tmp+=s[pos++];
    if(s[pos]==')') pos++;
    if(tmp.size())
    {
        int data = toInt(tmp);
        node->left = newNode(data);
        makeTree(node->left, sum+data );
    }

    //right child
    while(s[pos]!='(' && pos<posl)
        pos++;
    pos++;
    tmp="";
    while(s[pos]!=')' && s[pos]!='(' && pos<posl)
        tmp+=s[pos++];
    if(s[pos]==')') pos++;
    if(tmp.size())
    {
        int data = toInt(tmp);
        node->right = newNode(data);
        makeTree(node->right, sum+data );
    }
    while(s[pos]==')' && pos<posl) pos++;
    if(sum==n && node->left==NULL && node->right==NULL) possible=true;
return;
}

void deleteNode(node* node)
{
    if(node==NULL) return;
    deleteNode(node->left);
    deleteNode(node->right);
    free(node);
return;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, lftP, rgtP;

    char ch;
    while(cin>>n)
    {
        lftP=rgtP=0;
        s="";
        while(lftP!=rgtP || !lftP)
        {
            cin>>ch;    //space remove
            if(ch=='(') lftP++;
            else if(ch==')') rgtP++;
            s+=ch;
        }
        s+="()";
        posl=s.size();
        //cout<<s<<endl;
        struct node *root=newNode(0); //adding addition root
        possible=false;
        pos=0;
        makeTree(root, 0);
        if(possible && posl>4) cout<<"yes\n";
        else cout<<"no\n";
        deleteNode(root);
    }
return 0;
}