#include <stdio.h>
#include <stdlib.h>



/**
 * Generic tree node
 *
 * If left || right != NULL, then value is operator
 */
typedef struct _TreeNode {
	struct _TreeNode* left;
	struct _TreeNode* right;
	int       value;
} TreeNode;




/**
 * Create a new node
 */
TreeNode* Node_Create(int value)
{
	TreeNode* node = malloc(sizeof(TreeNode));
	node->left  = NULL;
	node->right = NULL;
	node->value = value;
	return node;
}



/**
 * Create a new node with 2 immediate left & right treenodes
 */
TreeNode* Node_Create2(int value, TreeNode* left, TreeNode* right)
{
	TreeNode* node = malloc(sizeof(TreeNode));
	node->left  = left;
	node->right = right;
	node->value = value;
	return node;
}


/** 
 * Destroy an entire tree
 */
void Tree_Destroy(TreeNode* root)
{
	if (root == NULL) return; // nothing to do here
	Tree_Destroy(root->left);
	Tree_Destroy(root->right);
	free(root);
}


/**
 * Evaluate binary operator tree in preorder: Left - Root - Right
 */
int Node_PrefixEval(TreeNode* node)
{
	if (node->left && node->right) // is this an operator?
	{
		int lval = Node_PrefixEval(node->left);
		int rval = Node_PrefixEval(node->right);
		switch (node->value)
		{
			case '/': return lval / rval;
			case '*': return lval * rval;
			case '+': return lval + rval;
			case '-': return lval - rval;
		}
		return 0;
	}
	return node->value; // not an operator, just return the value
}


int main(int argc, char** argv)
{
	// create infix 3 * (7 + 5)
	// prefix order * 3 + 7 5
	TreeNode* root = 

                       Node_Create2('*',
         Node_Create(3),              Node_Create2('+', 
                              Node_Create(7),      Node_Create(5))
	);


	int result = Node_PrefixEval(root);
	printf("eval(* 3 + 7 5) = %d\n", result);
	Tree_Destroy(root); // cleanup

	system("pause");
	return 0;
}