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

typedef struct s_TNode {
    char Info;
    struct s_TNode *Left;
    struct s_TNode *Right;
} t_TNode;

typedef struct s_Tree {
    t_TNode *Root;
} t_Tree;

typedef struct s_LNode {
    char Info;
    struct s_LNode *Next;
} t_LNode;

typedef struct s_Stack {
    t_LNode *Top;
} t_Stack;

int Pop (t_Stack *Stack, char *Res)
{
    t_LNode *tmp;

    if (!Stack)
    {
        printf("\nNULL pointer to stack.");
        return 0;
    }
    if (!Stack->Top)
    {
        printf("\nStack is empty.");
        return 0;
    }
    *Res = (Stack->Top)->Info;
    tmp = Stack->Top;
    Stack->Top = tmp->Next;
    free(tmp);
    tmp = NULL;
    return 1;
}

int Push (t_Stack *Stack, char Arg)
{
    t_LNode *tmp;
    t_LNode *New;

    if (!Stack)
    {
        printf("\nNULL pointer to stack.");
        return 0;
    }
    tmp = Stack->Top;
    if (!(New = (t_LNode *)malloc(sizeof(t_LNode))))
    {
        printf("\nCouldn't allocate memory for new stack element.");
        return 0;
    }
    Stack->Top = New;
    (Stack->Top)->Next = tmp;
    (Stack->Top)->Info = Arg;
    return 1;
}

int Prior(char Top, char Arg)
{
    if (Top == '+' || Top == '-')
    {
        if (Arg == '+' || Arg == '-' || Arg == ')')
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    if (Top == '*' || Top == '/' || Top == '^')
    {
        if (Arg == '+' || Arg == '-' || Arg == '*' || Arg == '/' || Arg == '^' || Arg == ')')
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    if (Top == '(')
    {
        if (Arg == ')')
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    return 0;
}

void ConvertToRPN(char Arg[], char Res[])
{
    int ArgL = strlen(Arg);
    int j = 0;
    int i = 0;
    int PriorV = 0;
    char Smb = '\0';
    t_Stack Stack; Stack.Top = NULL;

    // пока во входной строке что-то есть
    for (i = 0 ; i < ArgL ; ++i)
    {
        if (Stack.Top)
        {
            PriorV = Prior((Stack.Top)->Info, Arg[i]);
        }
        // если Arg[i] -- операнд, то выводим его в выходную строку
        if (!(Arg[i] == '+' || Arg[i] == '-' || Arg[i] == '*' || Arg[i] == '/' || Arg[i] == '(' || Arg[i] == ')' || Arg[i] == '^'))
        {
            Res[j++] = Arg[i];
        }
        // иначе
        else
        //  пока (на стеке более приоритетная операция)
        {
            while (PriorV)
            //  вытаскиваем smb со стека, smb != "(" и отправляем в вых строку
            {
                Pop(&Stack, &Smb);
                if (Smb != '(')
                {
                    Res[j++] = Smb;
                }
                if (Stack.Top)
                {
                    PriorV = Prior((Stack.Top)->Info, Arg[i]);
                }
                else
                {
                    PriorV = 0;
                }

            }
            //  push(Arg[i])
            if (Arg[i] != ')')
            {
                Push(&Stack, Arg[i]);
            }
        }
    }
    //а теперь выталкиваем все, что осталось в стеке
    while (Stack.Top)
    {
        Pop(&Stack, &Smb);
        if (Smb != '(')
        {
            Res[j++] = Smb;
        }
    }
    return;
}

void BuildTreeNode (t_TNode *Node, char RPN[])
{
    int Len = strlen(RPN) - 1;

    if (!Node)
    {
        printf("\nNULL pointer to tree node.)");
        return;
    }
    //если передали пустую вершину, то засунем в нее последний символ строки
    if (Node->Info == '\0')
    {
        Node->Info = RPN[Len];
        RPN[Len] = '\0';
        Len = strlen(RPN) - 1;
    }
    //начинаем с правого поддерева
    if (!(Len + 1))
    {
        return;
    }

    if (!(Node->Right = (t_TNode *) malloc(sizeof(t_TNode))))
    {
        printf("\nCouldn't allocate memory for right tree node.");
        return;
    }

    Node->Right->Info = RPN[Len];
    Node->Right->Left = NULL;
    Node->Right->Right = NULL;

    if (!(RPN[Len] == '+' || RPN[Len] == '-' || RPN[Len] == '*' || RPN[Len] == '/' || RPN[Len] == '(' || RPN[Len] == ')' || RPN[Len] == '^'))
    {
        RPN[Len] = '\0';
    }
    else
    {
        RPN[Len] = '\0';
        BuildTreeNode(Node->Right, RPN);
    }

    //продолжаем левым поддеревом
    Len = strlen(RPN) - 1;

    if (!(Len + 1))
    {
        return;
    }

    if (!(Node->Left = (t_TNode *) malloc(sizeof(t_TNode))))
    {
        printf("\nCouldn't allocate memory for left tree node.");
        return;
    }

    Node->Left->Info = RPN[Len];
    Node->Left->Left = NULL;
    Node->Left->Right = NULL;

    if (!(RPN[Len] == '+' || RPN[Len] == '-' || RPN[Len] == '*' || RPN[Len] == '/' || RPN[Len] == '(' || RPN[Len] == ')' || RPN[Len] == '^'))
    {
        RPN[Len] = '\0';
    }
    else
    {
        RPN[Len] = '\0';
        BuildTreeNode(Node->Left, RPN);
    }

}

void BuildTreeFromRPN (t_Tree *Tree, char RPN[])
{
    BuildTreeNode(Tree->Root, RPN);
}

void DirectTreeTraversal(t_TNode *Root)
{
    printf("%c ",Root->Info);
    if (Root->Left)
    {
        DirectTreeTraversal(Root->Left);
    }
    if (Root->Left)
    {
        DirectTreeTraversal(Root->Right);
    }
}

void InorderTreeTraversal (t_TNode *Root)
{
    if (Root->Left)
    {
        InorderTreeTraversal(Root->Left);
    }
    printf("%c ",Root->Info);
    if (Root->Right)
    {
        InorderTreeTraversal(Root->Right);
    }
}
void main ()
{
    char Exp[30] = {'\0'};
    char Res[30] = {'\0'};
    int i = 0;
    int LRes;
    char ch;
    t_Tree Tree;

    printf("Enter Infix expression\n");
    while (Exp[i++] = getchar())
    {
        if (Exp[i-1] == '\n')
        {
            Exp[i-1] = '\0';
            break;
        }
    }
    ConvertToRPN(Exp, Res);
    LRes = strlen(Res);
    for (i = 0 ; i < LRes ; ++i)
    {
        printf("%c", Res[i]);
    }
    printf("\n");
    if (!((Tree.Root) = (t_TNode *) malloc(sizeof(t_TNode))))
    {
        printf("Couldn't allocate memory for tree.");
        return;
    }

    Tree.Root->Info = '\0';
    BuildTreeFromRPN(&Tree, Res);
    printf("\nDirect tree traversal: ");
    DirectTreeTraversal(Tree.Root);
    printf("\nInorder tree traversal: ");
    InorderTreeTraversal(Tree.Root);
    printf("\n");
}