Expression Tree

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

struct node
{
	int data;
	struct node* llink;
	struct node* rlink;
};
typedef struct node* NODE;


NODE getnode()
{
	NODE x;
	x = malloc(sizeof(struct node));

	return x;
}

NODE create(char postfix[])
{

	// This function creates an expression tree.
	// This tree is then passed to the evaluate function.

	int i,k;
	NODE temp;

	char symbol;
	NODE stack[100];


	// Assing each character in the postfix expression to symbol till it reaches the last(null) character.
	for(i=k=0; (symbol = postfix[i]) != '\0'; i++)
	{
		temp = getnode();
		
		// Initialise
		temp->data = symbol;
		temp->llink = temp->rlink = NULL;

		// If symbol encountered is a alphabet or a character, keep moving.
		if(isalnum(symbol))
		{
			stack[k++] = temp;

		}
		
		// If you encounter an operator(+,-,*,/), add the right node and left node to that operator.
		// We use a stack to keep track of the symbol.
		else
		{
			temp->rlink = stack[--k];
			temp->llink = stack[--k];

			stack[k++] = temp;
		}

	}
	
	// k gets incremented in the last iteration of the loop. Decrement it back.
	return stack[--k];

}

float evaluate(NODE root)
{
	float num;
	
	// left node (operator) right node is the order of evaluation.
	switch(root->data)
	{
		case '+' : return evaluate(root->llink) + evaluate(root->rlink);
		case '-' : return evaluate(root->llink) - evaluate(root->rlink);
		case '*' : return evaluate(root->llink) * evaluate(root->rlink);
		case '/' : return evaluate(root->llink) / evaluate(root->rlink);
		
		// Both ^ and $ are used for power. 
		case'^':
		case'$':
			return pow(evaluate(root->llink),evaluate(root->rlink));

		default: 
				// If alphabets (x,y,z,a,b...) are entered.
				// Ask the user the value of those variables.
				// and continue normal execution by returning.
				
				if(isalpha(root->data))
				{
					printf("%c = \n", root->data);
					scanf("%f",&num);
					return num;
				}
				
				// with ASCII you can just add and subtract 48(ASCII value of 0)
				// to go between integer and character values.
				// Just a smart way to convert int to char.
				else
					return root->data - '0';
	}


}

void display(NODE root,int i)
{
	int j;
	if(root==NULL)return;
	display(root->rlink,i+1);
	for(j=0;j<i;j++)
		printf("	");
	printf("%c	",root->data);
	printf("\n");
		
	display(root->llink,i+1);
}


int main()
{
	char postfix[100], infix[100];
	float res = 0;
	NODE root;
	root = NULL;

	printf("Enter a valid postfix expression: \n");
	scanf("%s",postfix);


	root = create(postfix);
	res = evaluate(root);
	printf("The created tree is : \n");
	display(root, 1);
	printf("Result : %f \n",res);

	return 0;

}