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



typedef struct __QueryBuff{
  char *data;
  struct __QueryBuff *next;
} _QueryBuff;


typedef struct __QueryBuffHeader{
  struct __QueryBuff *stackTop;
  struct __QueryBuff *queueFront;
  struct __QueryBuff *queueTail;
}_QueryBuffHeader;




_QueryBuff *get_new_query_buff_node();
_QueryBuffHeader *create_query_buff_header();
void reset_query_buff_header(_QueryBuffHeader *);
void *query_buff_push(_QueryBuffHeader *, void *);
void *query_buff_pop(_QueryBuffHeader *);
void *query_buff_insert(_QueryBuffHeader *, void *);
void *query_buff_delete(_QueryBuffHeader *);
char *get_token(char *, char *, char **);
char *str_trim(char *);
int is_operator(char *);
void process_query(_QueryBuffHeader *);



/***************************************************************************
 * 새로운 노드를 하나 할당한다.
 ***************************************************************************/
_QueryBuff *get_new_query_buff_node()
{
  _QueryBuff *newNode;
  newNode = (_QueryBuff *)malloc(sizeof(_QueryBuff));
  newNode->data = NULL;
  newNode->next = NULL;
  return newNode;
}


/***************************************************************************
 * data를 스택에 밀어넣고 해당 포인터를 리턴
 ***************************************************************************/
void *query_buff_push(_QueryBuffHeader *header, void *data)
{
  register _QueryBuff *newTop;

  newTop = get_new_query_buff_node();
 
  newTop->data = data;
  newTop->next = header->stackTop;
  header->stackTop = newTop;
  //printf(\"push(\'%s\')\\n\", (char *)data);
  return newTop->data;
}

/***************************************************************************
 * 스택에서 팝해서 data의 포인터를 리턴.
 ***************************************************************************/
void *query_buff_pop(_QueryBuffHeader *header)
{
  void *data;
  _QueryBuff *newTop; 

  if(header->stackTop == NULL ) return NULL; /* stack enpty */

  if(header->stackTop->data) data = header->stackTop->data;
  else data = NULL;

  newTop = header->stackTop->next;
  free(header->stackTop);
  header->stackTop = newTop;
  //printf(\"pop(\'%s\')\\n\", (char *)data);
  return data;
}


/***************************************************************************
 * 큐에 data를 저장하고 저장된 문자열을 리턴
 ***************************************************************************/
void *query_buff_insert(_QueryBuffHeader *header, void *data)
{
  header->queueTail->data = data;
  header->queueTail->next = get_new_query_buff_node();
  header->queueTail = header->queueTail->next;
  //printf(\"insert(\'%s\')\\n\", (char *)data);
  return data;
}

/***************************************************************************
 * 큐에 data를 지우고 지워진 data를 리턴
 ***************************************************************************/
void *query_buff_delete(_QueryBuffHeader *header)
{
  void *data;
  _QueryBuff *freeNode;

  if(header->queueFront == header->queueTail) return NULL; /* queue empty */

  if(header->queueFront->data) data = header->queueFront->data;
  else data = NULL;

  freeNode = header->queueFront;
  header->queueFront = header->queueFront->next;
  free(freeNode);
  //printf(\"delete(\'%s\')\\n\", (char *)data);
  return data;
}



/***************************************************************************
 * 프로그램 시작할때 한번 호출하여 새로운 해더를 하나 만들고 초기화 한다.
 ***************************************************************************/
_QueryBuffHeader *create_query_buff_header()
{
  _QueryBuffHeader *newNode;
  newNode = (_QueryBuffHeader *)malloc(sizeof(_QueryBuffHeader ));
  newNode->stackTop=NULL;
  newNode->queueFront=NULL;
  newNode->queueTail=NULL;
  return newNode;
}

/***************************************************************************
 * 이전에 쓰던 내용이 있을지도 모르니까 리샛한다.
 ***************************************************************************/
void reset_query_buff_header(_QueryBuffHeader *headNode)
{
  register _QueryBuff *nowNode, *agoNode;
 
  nowNode = headNode->stackTop;
  while(nowNode){
    agoNode = nowNode;
    nowNode = nowNode->next;
    if(agoNode->data) free(agoNode->data);
    free(agoNode);
  } /* while(nowNode){ */

  nowNode = headNode->queueFront;
  while(nowNode){
    agoNode = nowNode;
    nowNode = nowNode->next;
    if(agoNode->data) free(agoNode->data);
    free(agoNode);
  } /* while(nowNode){ */

  /* 비어있는 노드 하나 만들어둔다. */
  headNode->queueFront = headNode->queueTail = get_new_query_buff_node();
}



/***************************************************************************
 * buff의 앞 뒤에 붙어 있는 공백 등을 모두 빼낸다.
 **************************************************************************/
char *str_trim(char *buff)
{
  register char *sP, *eP;
  char *temp;

  temp = (char *)malloc(strlen(buff)+3);

  sP = buff;            /* 앞쪽검사 */
  while(*sP){
    if( !(*sP == \' \') &&
    !(*sP == \'\\n\') &&
    !(*sP == \'\\r\') &&
    !(*sP == \'\\t\')){
      break;
    }
    sP++;
  }

  if(*sP == \'\\0\'){        /* 빈줄이다. */
    buff[0] = \'\\0\';
    return buff;
  }

  eP = &buff[strlen(buff)-1];    /* 뒤쪽 검사 */
  while(*eP){
    if( !(*eP == \' \') &&
    !(*eP == \'\\n\') &&
    !(*eP == \'\\r\') &&
    !(*eP == \'\\t\')){
      break;
    }
    eP--;
    if(eP == sP){
      break;
    }
  }
 
  *(eP+1) = \'\\0\';
  strcpy(temp, sP);
  strcpy(buff, temp);
  free(temp);

  return buff;
}


/***************************************************************************
 * 피가 연산자인지 검사해서 연잔사면 연산자의길이를 리턴 그렇지 안니하면 0
 * 또. 리턴할때 해당 연산자의 우선순위를 리턴한다.
 * 연산자의 길이를 알고싶으면 리턴값에 %1000
 * 연산자 우선순위를 알고싶을때 리턴값에 /1000
 ***************************************************************************/
int is_operator(char *p)
{
  if(p == NULL) return 0;
  else if (!strncmp(p, \"(\", 1)) return 1 + 999000;
  else if(!strncmp(p, \")\", 1)) return 1 + 999000;
  else if(!strncmp(p, \"+\", 1)) return 1 + 11000;
  else if(!strncmp(p, \"-\", 1)) return 1 + 11000;
  else if(!strncmp(p, \"*\", 1)) return 1 + 22000;
  else if(!strncmp(p, \"/\", 1)) return 1 + 22000;
 
  return 0;
}


/***************************************************************************
 * string1에서 하나의 토큰을 잘라서 그 주소를 리턴하고 다음에 시작할 위치를
 * string2에 저장한다.
 ***************************************************************************/
char *get_token(char *tokenBuff, char *string1, char **string2)
{
  register char *p;
  char *tokenP;
  int operLen = 0;

  if((strlen(string1)) == 0) return NULL;

  str_trim(string1);    /* 앞뒤로 공백잘라내기. */

  tokenP = p = string1;
  while((*p != \' \')&&(*p != \'\\t\')&&(*p != \'\\n\')&&(*p != \'\\r\')&& *p){
    operLen = is_operator(p) % 1000;
    if(operLen) break;
    p++;
  } /* while(*p == \' \' || *p == \'\\t\' || *p == \'\\n\' || *p == \'\\r\'){ */

  if(operLen){            /* 연산자가 발견되면 */
    if(p == tokenP){        /* 앞에 나온경우 */
      strncpy(tokenBuff, p, operLen);
      tokenBuff[operLen] = \'\\0\';
      *string2 = p+operLen;
      return tokenBuff;
    }else{            /* 연산자가 끝에 나왔다. */
      strncpy(tokenBuff, tokenP, p-tokenP);
      tokenBuff[p-tokenP] = \'\\0\';
      *string2 = p;
      return tokenBuff;
    } /* if(p == tokenP){ */
  } /* if(isOper){ */

  *string2 = p;
  strncpy(tokenBuff,tokenP, p-tokenP);
  return tokenBuff;
}


/***************************************************************************
 * 입력된 쿼리를 계산할 준비 다했으니 쭈~ㄱ 따라가면서 계산만 하면 된다.
 ***************************************************************************/
void process_query(_QueryBuffHeader *queryBuffHead)
{
  register char *data1, *data2, *data3;
  char string[512];
  int result;

  while((data1 = (char *)query_buff_delete(queryBuffHead))){
    //    printf(\"[%s]\\n\",data1);
    if(is_operator(data1)){    /* 연산자이면 두개 팝해서 계산하고 푸시 */
      data3 = (char *)query_buff_pop(queryBuffHead); /* 나중값을 먼저팝 */
      data2 = (char *)query_buff_pop(queryBuffHead);
     
      if(data1[0] == \'+\') result = atoi(data2) + atoi(data3);
      else if(data1[0] == \'-\') result = atoi(data2) - atoi(data3);
      else if(data1[0] == \'*\') result = atoi(data2) * atoi(data3);
      else if(data1[0] == \'/\') result = atoi(data2) / atoi(data3);
      sprintf(string, \"%d\",result);
      //      printf(\"중간 결과값 : %d\\n\", result);
      query_buff_push(queryBuffHead, strdup(string));
      free(data1);
      free(data2);
      free(data3);
    }else{
      query_buff_push(queryBuffHead, data1);
    } /* if(is_operator(data1)){ */
  } /* while((data1 = (char *)query_buff_delete(queryBuffHead))){ */

  data1 = (char *)query_buff_pop(queryBuffHead);
  printf(\"query result is [%s]\\n\", data1);
  free(data1);
}



#define single_test
#ifdef single_test
/***************************************************************************
 *
 ***************************************************************************/
int main()
{
  _QueryBuffHeader *queryBuffHead;
  int i=0;

  /* 쿼리파싱할때 사용할 저장곤간을 만들고 초기화 */
  queryBuffHead = create_query_buff_header();
  reset_query_buff_header(queryBuffHead);


  while(1){/* 계산기를 한번 만들어 본다. */
    char string[512];
    char *strBuff1, *strBuff2;
    char tokenBuff[512];
    char *data1, *data2 = NULL;


    printf(\"%d:input string -> \",i++);
    gets(string);
    //    getchar();
    //    strcpy(string,\"12+13+(34/5*4*54-45)+3243\");

    printf(\"org string [%s]\\n\", string);
    strBuff2 = strBuff1 = string;    /* 앞뒤로 공백잘라내기. */


    while(get_token(tokenBuff, strBuff1, &strBuff2)){ /* 토큰분리 */
      if(!is_operator(tokenBuff)){        /* 연산자가 아니면. */
    //    printf(\"token -> [%s]\\n\", tokenBuff);
    query_buff_insert(queryBuffHead, strdup(tokenBuff));
      } else {
    //    printf(\"token -> [%s] _oper\\n\", tokenBuff);
    if(tokenBuff[0] == \')\'){
      data1 = (char *)query_buff_pop(queryBuffHead);
      //printf(\"1111 -> [%s] _oper\\n\", data1);
      while(data1[0] != \'(\'){ /* 여는괄로가 나올때까지 팝해서 인서트 */
        //printf(\"1112 -> [%s] _oper\\n\", data1);
        query_buff_insert(queryBuffHead, data1);
        //printf(\"1113 -> [%s] _oper\\n\", data1);
        data1 = (char *)query_buff_pop(queryBuffHead);
        //printf(\"1114 -> [%s] _oper\\n\", data1);
      } /* while(data1[0] != \'(\'){ */
      free(data1);        /* 여는괄로 프리하기. */
    }else{
      data1 = tokenBuff;
      if(data1[0] == \'(\'){    /* 괄호열리면 무조건푸시 */
        data2 = NULL;
        query_buff_push(queryBuffHead, strdup(data1));
        goto endIf;
      } /* if(data1[0] == \'(\'){ */
      if(data2){        /* 앞서 푸시된 연산자가 있으면. */
        int a,b;        /* 곱하기나 나누기는 2, 더하기나 빼기는 1 */
       
        a = is_operator(data1); /* 연산자 우선순위를 알아온다. */
        if((a/1000)==999) a = -1; /* 괄로는 스택안에 들어가면 우선순위가 가장 낮아진다. */
        else a /= 1000;
      reCmp:
        b = is_operator(data2); /* 연산자 우선순위를 알아온다. */
        if((b/1000)==999) b = -1; /* 괄로는 스택안에 들어가면 우선순위가 가장 낮아진다. */
        else b /= 1000;

        if(a > b){         /* 이전 연산자보다 우선순위가 높다. */       
          data2 = (char *)query_buff_push(queryBuffHead, strdup(data1));
        }else{        /* 이전 연산자보다 우선순위가 낮다. */
          data2 = (char *)query_buff_pop(queryBuffHead);
          query_buff_insert(queryBuffHead, data2);
          data2 = (char *)query_buff_pop(queryBuffHead);
          if(data2){    /* 다시 비교 */
        query_buff_push(queryBuffHead, data2);
        goto reCmp;
          }else {        /* 더이상 팝할꺼 없으면 신규 푸시 */
        data2 = (char *)query_buff_push(queryBuffHead, strdup(data1));
          }    /* if(data2){ */
        } /* if(a > b){ */
      }else{
        data2 = query_buff_push(queryBuffHead, strdup(data1));
      } /* if(data2){ */
    } /* if(tokenBuff[0] == \')\'){ */
      }    /* if(strBuff1){ */
    endIf:
      strBuff1 = strBuff2;
    } /* while(token = get_token(strBuff1, &strBuff2)){ */

    /* 스택에 남아있는거 붙인다. */
    while((data2 = (char *)query_buff_pop(queryBuffHead)))
      query_buff_insert(queryBuffHead, data2);

    /* 쭈~ㄱ 따라가면서 함 찌거본다. */
    puts(\"result is.....\");

    process_query(queryBuffHead);
    //    return 0;
  }/* 계산기를 한번 만들어 본다. */




  {/*스택하고 큐하고 잘 동작 하는지 확인하는거  */
    char job[10];
    char string[50];
    char *data;
  restart:
    printf(\"input job ->  1:stack, 2:queue  :: \");
    gets(job);

    while(1){
      if(job[0] == \'1\'){
    printf(\"input action (push:1, pop:2) -> \");
    gets(string);
    if(string[0] == \'1\'){
      printf(\"input string : \");
      gets(string);
      query_buff_push(queryBuffHead, strdup(string));
    }else{
      data = (char *)query_buff_pop(queryBuffHead);
      printf(\"pop : [%s]\\n\", data);
      free(data);
    }    /* if(string[0] == 1){ */
      }else if(job[0] == \'2\'){
    printf(\"input action (insert:1, delete:2) -> \");
    gets(string);
    if(string[0] == \'1\'){
      printf(\"input string : \");
      gets(string);
      query_buff_insert(queryBuffHead, strdup(string));
    }else{
      data = (char *)query_buff_delete(queryBuffHead);
      printf(\"delete : [%s]\\n\", data);
      free(data);
    }    /* if(string[0] == 1){ */
      }else{
    puts(\"job error\");
    goto restart;
      } /* if(job[0] == \'1\'){ */
    } /* while(1){ */
  }/*스택하고 큐하고 잘 동작 하는지 확인하는거  */

  return 0;
}
#endif