#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; }