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

struct Node{
	int info;
	struct Node *next;
};

typedef struct Node *nodeptr;

void display(nodeptr *Stack)
{
	nodeptr q = *Stack;
	while(q != 0)
	{
		printf("%d (%c)\n",q->info,q->info);
		q = q->next;
	}
}

void push(nodeptr *s, char x)
{
	nodeptr q = (nodeptr)malloc(sizeof(struct Node));
	q -> info = x;
	if(*s == NULL)
	{
		q -> next = NULL;
		*s = q;
	}
	else
	{
		q -> next = *s;
		*s = q;
	}
}

char pop(nodeptr *s)
{
	if(*s == NULL)
		return;
	else{
		char val = (*s)->info;
		*s = (*s) -> next;
		return val;
	}
}

int is_digit(char c)
{
	if(c >= '0' && c <= '9')
		return 1;
	else
		return 0;
}

int prec(char c)
{
	switch(c){
		case '+':
		case '-':return 1;
		case '*':return 2;
		case '/':return 3;
		case '^':return 4;
		case '(':
		case ')':return 0;
	}
}

char* in_to_pos(char* in)
{
	char *out, c;
	int i,p;
	nodeptr Stack = 0;

	out = (char*)malloc(sizeof(char) * 128);

	i = 0;
	p = 0;
	while((c = in[i++])!='\0')
	{
		if(is_digit(c))
		{
			out[p++] = c;
		}
		else
		{
			if(c != '(' && c != ')')
			{
				out[p++] = ' ';

				if(Stack == 0 || prec(c) > prec(Stack -> info))
				{
					push(&Stack,c);
				}
				else
				{
					out[p++] = ' ';
					out[p++] = pop(&Stack);
					push(&Stack,c);
				}
			}
			else
			{
				if(c == '(')
					push(&Stack, c);
				else if(c == ')')
				{
					while((c = pop(&Stack))!='('){
						out[p++] = ' ';
						out[p++] = c;
					}
				}
			}

		}

	}
	while(Stack != 0)
	{
		out[p++] = ' ';
		out[p++] = pop(&Stack);
	}
	out[p] = '\0';

	return out;

}

int eval(int a,int b,char op)
{
	int c = 1;
	switch(op){
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		case '/': return a/b;
		case '^': while(b>0)
			{
				c *= a;
				--b;
			}
			return c;
	}
}

int pos_eval(char* in)
{
	int i, n, result;
	char c;
	nodeptr Stack = 0;

	i = 0;
	n = 0;
	while((c = in[i++])!='\0')
	{
		if(is_digit(c))
		{
			while(c!=' '){
				n = n*10 + (c - '0');
				c = in[i++];
			}
			push(&Stack, n);
			n = 0;
			++c;
		}
		else if(c == ' ')
			continue;
		else
		{
			result = eval(pop(&Stack),pop(&Stack),c);
			push(&Stack, result);
		}
	}
	return pop(&Stack);
}

int main()
{
	char *in, *pos;
	int res;

	in = (char*)malloc(sizeof(char) * 128);

	printf("Enter Infix Expression:\n");
	scanf("%s",in);

	pos = in_to_pos(in);

	printf("POSTFIX = %s\n", pos);

	res = pos_eval(pos);

	printf("RESULT = %d\n",res);

}