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

typedef struct Node
{
    char data;
    struct Node *next;
} Node;

typedef struct Nodeint
{
    int data;
    struct Nodeint *next;
} Nodeint;

Nodeint *creeazanodint(int key)
{
    Nodeint *in=malloc(sizeof(Nodeint));
    in->data=key;
    in->next=NULL;
    return in;
}

Node *createnode(char ch)
{
    Node *in=malloc(sizeof(Node));
    in->data=ch;
    in->next=NULL;
    return in;
}

void push(Node **top,char ch)
{
    Node *in=createnode(ch);
    if(in==NULL)
        printf("Stack overflow\n");
    else
    {
        in->next=*top;
        (*top)=in;
    }
}

void pushint(Nodeint **stack,int val)
{
    Nodeint *in=creeazanodint(val);
    if(in==NULL)
        printf("Stack overflow\n");
    else
    {
        in->next=*stack;
        *stack=in;
    }
}

char pop(Node **top)
{
    char x=-1;
    if(*top==NULL)
        printf("Stack underflow\n");
    else
    {
        Node *p=*top;;
        x=p->data;
        (*top)=(*top)->next;
        free(p);
    }
    return x;
}

int popint(Nodeint **stack)
{
    int x=-1;
    Nodeint *d=*stack;
    if(*stack==NULL)
        printf("Stack underflow\n");
    else
    {
        d=*stack;
        x=d->data;
        *stack=(*stack)->next;
        free(d);
    }
    return x;
}

int pair(char one,char two)
{
    if(one=='(' &&two==')')
        return 1;
    else if(one=='[' && two==']')
        return 1;
    else if(one=='{' && two=='}')
        return 1;
    else
        return 0;
}

int isValid(Node **top,char* string)
{
    int i;
    for(i=0; string[i]!='\0'; i++)
    {
        if(string[i]=='(' || string[i]=='[' || string[i]=='{')
            push(top,string[i]);
        else if(string[i]==')' || string[i]==']' || string[i]=='}')
        {
            if(*top==NULL)
                return 0;
            else if(pair(pop(top),string[i])==0)
                return 0;
        }
    }
    if(*top==NULL)
        return 1;
    else
        return 0;
}

int priorityout(char a)
{
    if(a=='+'|| a=='-')
        return 1;
    else if(a=='*' || a=='/')
        return 3;
    else if(a=='^')
        return 6;
    else if(a=='(' || a=='[' || a=='{')
        return 7;
    else if(a==')' || a==']' || a=='}')
        return 0;
    return 0;
}

int priorityin(char a)
{
    if(a=='+'||a=='-')
        return 2;
    else if(a=='*' || a=='/')
        return 4;
    else if(a=='^')
        return 5;
    else if(a=='('||a=='['||a=='{')
        return 0;
    return 0;
}

int verify(char a)
{
    if(isalnum(a))
        return 1;
    else
        return 0;
}

char *post(Node **top,char *infix)
{
    int i=0,j=0;
    int size=strlen(infix);
    char *postfix=malloc((size+1)*sizeof(Node));
    while(infix[i]!='\0')
    {
        if(verify(infix[i]))
            postfix[j++]=infix[i++];
        else
        {
            if(*top==NULL)
            {
                push(top,infix[i++]);
            }
            else
            {
                if(priorityout(infix[i])>priorityin((*top)->data))
                    push(top,infix[i++]);
                else
                {
                    if(priorityout(infix[i])==0 && priorityout((*top)->data)==7)
                    {
                        pop(top);
                        i++;
                    }
                    else if(priorityout(infix[i])==0 && priorityout((*top)->data)!=7 )
                        postfix[j++]=pop(top);
                }
            }
        }
    }
    while(*top)
        postfix[j++]=pop(top);
    postfix[j]='\0';
    return postfix;
}

int Eval(Nodeint **top,char *postfix)
{
    int i=0;
    int x1,x2,r=0 ;

    for(i=0; postfix[i]!='\0'; i++)
    {
        if(verify(postfix[i])==1)
        {
            pushint(top,postfix[i] - '0');
        }
        else
        {
            x2=popint(top);
            x1=popint(top);
            switch(postfix[i])
            {
            case '+':
                r=x1+x2;
                break;
            case '-':
                r=x1-x2;
                break;
            case '*':
                r=x1*x2;
                break;
            case '/':
                r=x1/x2;
                break;
            }
            pushint(top,r);
        }
    }
    return (*top)->data;
}

int main()
{
    FILE *f=fopen("evaluare.in","r");
    FILE *g=fopen("evaluare.out","w");
    Node *top=NULL;
    Nodeint *top1=NULL;
    char* infix="(((3*5)+(6/2))-4)";
    char* postfix;
    postfix=post(&top,infix);
    printf("%s\n",postfix);
    fprintf(g,"%d",Eval(&top1,postfix));
    return 0;
}