#include <stdio.h>
/* 우리가 평소 사용하는 중위 표기식을 컴퓨터가 계산하기 쉬운 후위 표기식으로 바꾸는 함수 */

/* 예) a + b * c -> 후위변경 -> a + (b*c) -> abc*+ */
/* [핵심] 피연산자는 바로 출력하고, 연산자는 스택에 넣었다가 우선순위를 따져서 적절한 순간에 출력, 스택은 연산자를 잠시 대기시키는 공간 */
/*
① 스택 바닥에 eos를 넣는다.
② 중위 표기식을 왼쪽부터 한 글자씩 읽는다.
③ 피연산자면 바로 출력한다.
④ ')'를 만나면 '('까지 스택의 연산자를 꺼내 출력한다.
   '('는 그냥 버린다.
⑤ 일반 연산자를 만나면
   현재 스택의 연산자와 우선순위를 비교한다.
⑥ 스택 연산자의 우선순위가 더 높거나 같으면
   스택 연산자를 먼저 꺼내 출력한다.
⑦ 현재 연산자를 스택에 넣는다.
⑧ 입력 수식을 모두 읽은 후
   스택에 남은 연산자를 전부 꺼내 출력한다.
⑨ eos를 만나면 끝낸다.
*/

typedef enum {
    lparen,
    rparen,
    plus,
    minus,
    times,
    divide,
    mod,
    eos,
    operand
} precedence;

/* 스택에는 연산자의 종류를 저장 */
precedence stack[MAX_STACK_SIZE];

/*
isp : 스택 안에 있을 때의 우선순위
icp : 새로 들어올 때의 우선순위

enum 순서:
lparen, rparen, plus, minus, times, divide, mod, eos, operand
*/
int isp[] = { 0, 19, 12, 12, 13, 13, 13, 0, 0 };
int icp[] = {20, 19, 12, 12, 13, 13, 13, 0, 0 };

/* 함수 원형 선언 */
precedence get_token(char *symbol, int *n);
void add(int *top, precedence item);
precedence delete(int *top);
void print_token(precedence token);
void postfix(void);

char expr[] = "a+b*c";

/* 스택에 데이터 삽입 */
void add(int *top, precedence item)
{
    if (*top >= MAX_STACK_SIZE - 1) {
        printf("Stack is full\n");
        return;
    }

    stack[++(*top)] = item;
}

/* 스택에서 데이터 삭제 */
precedence delete(int *top)
{
    if (*top < 0) {
        printf("Stack is empty\n");
        return eos;
    }

    return stack[(*top)--];
}

/* 연산자 종류를 실제 문자로 출력 */
void print_token(precedence token)
{
    switch (token) {
        case plus:
            printf("+");
            break;

        case minus:
            printf("-");
            break;

        case times:
            printf("*");
            break;

        case divide:
            printf("/");
            break;

        case mod:
            printf("%%");
            break;

        default:
            break;
    }
}

void postfix(void)
{ 
/*
symbol = 현재 읽은 실제 문자
token  = 그 문자의 종류
n      = 입력 수식에서 현재 읽는 위치
top    = 스택에서 현재 가장 위의 위치
*/
 
    char symbol;
    precedence token;
    int n = 0;
    int top = 0;
    /* 스택의 맨 아래에 eos 저장 */
    stack[0] = eos;
    
  for (token = get_token(&symbol, &n); token != eos;
              token = get_token(&symbol, &n)) { //중위식을 끝까지 읽어라
    
    if (token == operand) // 피연산자면, 후위표기식의 핵심: 피연산자들의 순서는 그대로 유지
       printf("%c", symbol); //값출력
    else if (token == rparen){ //오른쪽 괄호면
    /* 왼쪽 괄호가 나올 때까지 토큰들을 제거해서 출력시킴 */
    while (stack[top] != lparen) // 왼쪽괄호가 아니면
        print_token(delete(&top)); // pop 스택에서 연산자 하나를 꺼내서 출력
    delete(&top); /* 왼쪽 괄호를 버린다. 후위 표기식에는 괄호가 필요 없기 때문 */
    }
    else{ /* 연산자 또는 왼쪽괄 */
      /*
      isp: in-stack precedence: 이미 스택 안에 들어 있는 연산자의 우선순위
      icp: incoming precedence: 새로 들어오려고 하는 연산자의 우선순위 
      isp[stack[top]]: 현재 스택 맨 위 연산자의 우선순위
      icp[token]: 지금 새로 읽은 연산자의 우선순위
      스택에 있던 연산자의 우선순위가 새 연산자보다 높거나 같으면, 스택의 연산자를 먼저 꺼내라.
      */
          while(isp[stack[top]] >= icp[token] ) 
              print_token(delete(&top)); //pop 해서 출력
          add(&top, token); //기존 연산자중 우선처리할것들을 모두 꺼냈기때문에 현재 연산자 token은 스택에 넣는다
    }
  }
  /* delete(&top) 한 값을 token에 넣었는데 그 값이 eos가 아니면 출력 
     token = delete(&top);
     token != eos;
  */
  while ((token = delete(&top)) != eos)
      print_token(token);
  print("\n");
}

/* get_token: 그 문자가 어떤 종류인지 저장. 문자 하나를 읽어오는 함수 */
/* 수식에서 문자 하나를 읽고, 그 문자가 무엇인지 분류 */
precedence get_token(char *symbol, int*n) // &symbol, &n 변수의 주소
{
    /*현재 읽은 실제 문자 하나를 저장 
    후위 증가 연산자이므로 현재 값을 사용한 후 1 증가
    *symbol = expr[*n++]; expr:후위표기식 예) 83/2+
    (*n)++;
    */
    *symbol = expr[(*n)++]; // 현재 읽은 실제 문자 하나를 저장, 후위 증가 연산자이므로 현재 값을 사용한 후 1 증가
    switch (*symbol) { //읽은 문자가 무엇인지 검사
        case '(' : return lparen;
        case ')' : return rparen;
        case '+' : return plus;
        case '-' : return minus;
        case '/' : return divide;
        case '*' : return times;
        case '%' : return mod;
        case '\0' : return eos;
        default   : return operand;
        /*no error checking, default is operand */
    }
}

int main()
{
    printf("중위 표기식 : %s\n", expr);

    printf("후위 표기식 : ");

    postfix();

    return 0;
}