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

#define TYPE int
#define SIZE 1000

typedef struct{
    int top;
    TYPE stuff[SIZE];
}Stack;

void error()
{
    printf("Something is just not right. Try Again!\n");
    exit(-1);
}

int isfull(Stack *s)
{
    return s->top<SIZE?0:1 ;
}

void initialize(Stack *s)
{
    int i=0;
    s->top=0;
    for(i=0;i<SIZE;i++)
        s->stuff[i]=0;
}

int isEmpty(Stack *s)
{
    return s->top==0?1:0 ;
}

int top(Stack *s)
 {
    if(!isEmpty(s))
        return s->stuff[s->top-1];
 }

void push(Stack *s,TYPE value)
 {
     if(!isfull(s))
     {
         s->stuff[s->top]=value;
         s->top++;
     }
     else error();

 }

int pop(Stack *s)
 {
    if(isEmpty(s))
    {
        error();
    }
    else
    {
         s->top--;
        return s->stuff[s->top];
    }
    return -1;
 }

int Precedence(char c)
{
    switch (c)
    {
    case '+':
        return 1;
    case '-':
        return 1;

    case '*':
        return 2;
    case '/':
        return 2;

    case '^':
        return 3;
    }
    return -1;
}

int evaluatePostfix(char postfix[],Stack *s)
{
    printf("Postfix= %s.\n",postfix);
    int i=0,flag=0,temp=0, calc;
    char ch;
    while((ch=postfix[i++])!= '\0')
    {
        if (ch==' ')
        {
            flag=0;
            continue;
        }
        if (isdigit(ch))
            {
                temp=ch-48;
                if(flag==1)
                {
                    temp+=pop(s)*10;
                }
                push(s,temp);
                flag=1;
            }
        else if(ch=='+' || ch=='*' || ch=='-' || ch=='/'|| ch=='^')
            {
                flag=0;
                int val1,val2;
                if (isEmpty(s))
                    error();
                else
                    val1=pop(s);
                if (isEmpty(s))
                    error();
                else
                    val2=pop(s);
                switch (ch)
                    {
                    case '+':
                        calc= val2+val1;
                        push(s,calc);
                        break;
                    case '*':
                        calc= val2*val1;
                        push(s,calc);
                        break;
                    case '-':
                        calc= val2-val1;
                        push(s,calc);
                        break;
                    case '/':
                        calc= val2/val1;
                        push(s,calc);
                        break;
                    case '^':
                        calc= pow(val2,val1);
                        push(s,calc);
                        break;
                    }
            }
    }
    return pop(s);
}

char nextchar(char* pt)
{
    int i=0;
    while(pt[i])
    {
        if(pt[i]==' ')
            continue;
        else
            return pt[i];
    }
    return '\0';
}

void infixTopostfix(char infix[], char *postfix[])
{
    printf("Infix=%s.\n",infix);
    int i=0,j=0;
    Stack s1;
    initialize(&s1);
    char swap,ch,ch1,*pt=infix,*temp=malloc(sizeof(infix));
    while(ch=pt[j++])
    {
        if (ch>='0' && ch<='9')
        {
            temp[i]=ch;
            i++;
        }
        if (ch==' ')
        {
            temp[i]=ch;
            i++;
        }
        else
            switch(ch)
            {
            case '(':
            case '^':
            case '+':
            case '-':
            case '*':
            case '/':
                if(Precedence(ch) < Precedence(top(&s1)) && nextchar(pt)!='(')
                {
                    swap=pop(&s1);
                    push(&s1,ch);
                    push(&s1,swap);
                }
                else
                push(&s1,ch);
                break;
            case ')':
                while(!isEmpty(&s1))
                {
                ch1=pop(&s1);
                if (ch1=='(')
                    break;
                temp[i]=ch1;
                i++;
                }
                break;
        }
    }
    while(!isEmpty(&s1))
            {
                ch1=pop(&s1);
                if (ch1=='(')
                    break;
                temp[i]=ch1;
                i++;
            }
    temp[i]='\0';
    *postfix=temp;
}

int main()
{
    Stack s;
    char *infix=malloc(sizeof(char)*50);
    char *postfix=malloc(sizeof(char)*50);
    initialize(&s);
    printf("Please enter an infix expression:\n");
    fflush(stdin);
    fgets(infix,50,stdin);
    infix[strlen(infix)-1]='\0';
    infixTopostfix(infix,&postfix);
    printf("Result = %d",evaluatePostfix(postfix,&s));
    return 0;
}