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

#define SIZE 80 //The size of the array

enum ExpType {OPT,OPERAND};

typedef struct _stackNode{
    char item;
    struct _stackNode *next;
}StackNode;

typedef struct _stack{
   int size;
   StackNode *head;
}Stack;

typedef struct _stackNode2{
    char item[SIZE];
    struct _stackNode *next;
}StackNode2;

typedef struct _stack2{
   int size;
   StackNode *head;
}Stack2;

void push(Stack *sPtr, char item);
void push2(Stack2 *sPtr, char item);
int pop(Stack *sPtr);
int pop2(Stack2 *sPtr);
char peek(Stack s);
char peek2(Stack2 s);
int isEmptyStack(Stack s);
int isEmptyStack2(Stack2 s);

typedef struct _listnode
{
    int  item;
    enum ExpType type;
    struct _listnode *next;
} ListNode;

typedef struct _linkedlist{
   int size;
   ListNode *head;
} LinkedList;

void insertNode(LinkedList *llPtr, int item,enum ExpType type);
int deleteNode(LinkedList *llPtr);
void removeAllNodes(LinkedList *llPtr);
int isEmptyLinkedList (LinkedList ll);


void in2PreLL(char* infix, LinkedList *inExpLL);

void printExpLL(LinkedList inExpLL);

int isOperand(char c) {
  return ((c >= 'a' && c <= 'z') || (c >='A' && c <= 'Z')) ? 1 : 0;
}

int isOperator(char c) {
  return (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') ? 1: 0;
}
int prec(char c) {
  switch (c) {
    case '+':
    case '-':
      return 1;

    case '*':
    case '/':
      return 2;
    }
    return -1;
}

void insertNodeToBack(LinkedList *llPtr, int item, enum ExpType type) {
  ListNode *newNode = malloc(sizeof(ListNode));
  ListNode *currNode = llPtr->head;

  newNode->item = item;
  newNode->type = type;
  newNode->next = NULL;

  if (currNode == NULL) {
    llPtr->head = newNode;
    return;
  }
  while (currNode != NULL && currNode->next != NULL) {
    currNode = currNode->next;
  }
  currNode->next = newNode;
}


void reverse(ListNode** head_ref) {
    ListNode *prev = NULL;
    ListNode *current = *head_ref;
    ListNode *next = NULL;
    while (current != NULL) {
        if (current->item == '(') current->item = ')';
        else if (current->item == ')') current->item = '(';
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head_ref = prev;
}



void in2Post(LinkedList *infix, LinkedList *postfix) {
    Stack2 s;
    s.head = NULL;
    s.size = 0;

    int i = 0;
    int j = 0;
    int sum = 0;
    char tempInt[SIZE], c[SIZE];
    ListNode *currentNode = infix->head;
    while(i<SIZE && currentNode != NULL) {
        if (currentNode->type == OPERAND) {
          sprintf(tempInt, "%d", currentNode->item);
        } else {
          tempInt[0] = (char) currentNode->item;
          tempInt[1] = '\0';
        }
        if (tempInt[0] < 1 || tempInt[0] > 255) {
          currentNode = currentNode->next;
          continue;
        }
        switch(tempInt[0])
        {
        case '*': //operators
        case '/':
        case '+':
        case '-':
            while(isEmptyStack2(s)==0 && peek2(s) != '(' && prec(peek2(s)) >= prec(tempInt[0]) )
            {
                insertNodeToBack(postfix,peek2(s),OPT);
                pop2(&s);
            }
            push2(&s,tempInt[0]);
            currentNode = currentNode->next;
            break;
        case '(':
            push2(&s,tempInt[0]);
            currentNode = currentNode->next;
            break;
        case ')':
            while(isEmptyStack2(s)==0)
            {
                if(peek2(s)!='(')
                {
                    insertNodeToBack(postfix,peek2(s),OPT);
                    pop2(&s);
                }
                else
                {
                    pop2(&s);
                    break;
                }
            }
            currentNode = currentNode->next;
            break;
        default: //operand
            insertNodeToBack(postfix,atoi(tempInt),OPERAND);
            currentNode = currentNode->next;

        }
    }

    while(isEmptyStack2(s)==0)
    {
        insertNodeToBack(postfix,peek2(s),OPT);
        pop2(&s);
    }
}

void expressionLL(char* infix, LinkedList *inExpLL) {
  //init variables
  char tempInt[SIZE]; // to store the string of numbers
  int index = 0;

  while (*infix != '\0') {
    tempInt[0] = '\0';
    ListNode *temp = malloc(sizeof(ListNode));

    //handles insertion of ListNode into the linked list
    if (inExpLL->head == NULL) inExpLL->head = temp;
    else {
      ListNode *currNode = inExpLL->head;
      while (currNode->next != NULL) currNode = currNode->next;
      currNode->next = temp;
    }

    //checks where the number ends
    while (*infix>=48 && *infix != '\0') {
      tempInt[index] = *infix;
      infix++;
      index++;
    }
    tempInt[index] = '\0';
    //checks if tempInt is populated with numbers. If not, then insert a node that is an operator
    temp->item = (tempInt[0] == '\0') ? *infix : atoi(tempInt);
    temp->type = (tempInt[0] == '\0') ? OPT : OPERAND;

    //if temp's type is OPERAND, insert the current char from infix bc it will be an operator
    if (*infix != '\0' && temp->type != OPT) {
      ListNode *tempOpt = malloc(sizeof(ListNode));
      tempOpt->item = *infix;
      tempOpt->type = OPT;
      temp->next = tempOpt;
    }
    if (*infix != '\0') {
      infix++;
    } else {
      break;
    }

    //resets vars for next loop
    tempInt[0] = '\0';
    index = 0;
  }
}

int main()
{
    char infix[SIZE];

    //printf("Enter an infix expression:\n");
    gets(infix);

    LinkedList inExpLL;
    inExpLL.head = NULL;
    inExpLL.size = 0;

    in2PreLL(infix, &inExpLL);

    printExpLL(inExpLL);

    removeAllNodes(&inExpLL);
    return 0;
}

void in2PreLL(char* infix, LinkedList *inExpLL)
{
  char tempInt[SIZE];
  LinkedList *infixLL = malloc(sizeof(LinkedList));
  expressionLL(infix,infixLL);
  ListNode *currentNode = infixLL->head;
  while (currentNode != NULL) {
    currentNode = currentNode->next;
  }
  reverse(&(infixLL->head));
  currentNode = infixLL->head;
  while (currentNode != NULL) {
    currentNode = currentNode->next;
  }

  in2Post(infixLL,inExpLL);
  reverse(&(inExpLL->head));
  currentNode = inExpLL->head;
  // while (currentNode != NULL) {
  //   printf("%d ",currentNode->item);
  //   currentNode = currentNode->next;
  // }
  // printf("\n");
}

void printExpLL(LinkedList inExpLL)
{
    ListNode* temp = NULL;
    temp = inExpLL.head;
    while(temp!= NULL){
        if(temp->type == OPERAND)
            printf(" %d ",temp->item);
        else
            printf(" %c ",(char)(temp->item));
        temp = temp->next;
    }
    printf("\n");
}

void insertNode(LinkedList *LLPtr, int item, enum ExpType type) {
    ListNode *newNode;
    newNode = malloc(sizeof(ListNode));
    if(newNode==NULL) exit(0);

    newNode->item = item;
    newNode->type = type;
    newNode->next = LLPtr->head;
    LLPtr->head=newNode;
    LLPtr->size++;
}

int deleteNode(LinkedList *LLPtr) {
    if(LLPtr==NULL || LLPtr->size==0){
        return 0;
    }
    else{
       ListNode *temp = LLPtr->head;
       LLPtr->head = LLPtr->head->next;

       free(temp);
       LLPtr->size--;
       return 1;
    }
}

int isEmptyLinkedList (LinkedList ll) {
    if(ll.size==0) return 1;
    else return 0;
}

void removeAllNodes(LinkedList *LLPtr)
{
    while(deleteNode(LLPtr));
}

void push(Stack *sPtr, char item){
    StackNode *newNode;
    newNode = malloc(sizeof(StackNode));
    newNode->item = item;
    newNode->next = sPtr->head;
    sPtr->head = newNode;
    sPtr->size++;
}

void push2(Stack2 *sPtr, char item){
    StackNode *newNode;
    newNode = malloc(sizeof(StackNode));
    newNode->item = item;
    newNode->next = sPtr->head;
    sPtr->head = newNode;
    sPtr->size++;
}

int pop(Stack *sPtr){
    if(sPtr == NULL || sPtr->head == NULL){
        return 0;
    }
    else{
       StackNode *temp = sPtr->head;
       sPtr->head = sPtr->head->next;
       free(temp);
       sPtr->size--;
       return 1;
    }
}

int pop2(Stack2 *sPtr){
    if(sPtr == NULL || sPtr->head == NULL){
        return 0;
    }
    else{
       StackNode *temp = sPtr->head;
       sPtr->head = sPtr->head->next;
       free(temp);
       sPtr->size--;
       return 1;
    }
}

char peek(Stack s){
    return s.head->item;
}

char peek2(Stack2 s){
    return s.head->item;
}

int isEmptyStack(Stack s){
     if(s.size == 0) return 1;
     else return 0;
}

int isEmptyStack2(Stack2 s){
     if(s.size == 0) return 1;
     else return 0;
}