C++ 후위표기법을 중위표기법으로 변경하는 샘플

중위표기법 (infix)

---

연산자를 연산 대상의 가운데에 쓰는 표기법

일반적인 수학 표기법

경우에 따라 연산의 우선순위를 정확히 표현하기 위해 괄호가 필요함

예: ( 1 + 2 ) * ( 3 + 4 )

전위표기법 (prefix)

---

연산자를 연산 대상의 앞에 쓰는 표기법

예: * + 1 2 + 3 4

후위 표기법 (postfix)

---

연산자를 연산 대상의 뒤에 쓰는 표기법

예: 1 2 + 3 4 + *

/*  후위 표기식으로 바꾼이유        1.연산자 우선순위        2.괄호        */
#include <stdio.h>
#include <stdlib.h>
​
#define MAX_STACK_SIZE 100 //스택의 최대 크기
#define MAX_EXPR_SIZE 100 //수식의 최대 크기
​
typedef enum { //연산자들의 우선순위를 열거형으로 선언
    lparen, rparen, plus, minus, times, divide, mod, eos, operand
        // ( , ) , + , - , * , / , %
}precedence;
​
/****************함수원형******************/void postfix(void);
precedence get_token(char *symbol, int *n);
void print_token(precedence token);
precedence deleted(int* top);
void add(int* top, precedence item);
int eval(void);
void add_i(int* top, int item);
int deleted_i(int* top);
/******************************************/
​
precedence stack[MAX_STACK_SIZE]; //후위표기 전환에 사용되는 stackint stack2[MAX_STACK_SIZE];
​
char expr[MAX_EXPR_SIZE]; //입력 문자열char pexpr[MAX_EXPR_SIZE]; //입력 문자열
​
int isp[]={0, 19, 12, 12, 13, 13, 13, 0}; //isp는 in stack 스택 안에서의 우선순위int icp[]={20, 19, 12, 12, 13, 13, 13, 0}; //icp는 in coming 스택 밖에서의 우선순위// ( ,  ) , + , - , * , / , %, eos//마지막은 eos end of stack
​
void main()
{
    int result;
​
    while(1)
    {
        printf("후위 표기식 입력 : ");
        scanf("%s", &expr);
        result = eval();
        printf("후위표기 계산결과 : %d\n\n", result);
    }
}
​
void postfix(void)
{
    char symbol;
    precedence token; //token은 9개중에 하나
    int n = 0;
    int top = 0;
    stack[0] = eos; //첫번째 원소에 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(deleted(&top));
            deleted(&top); //왼쪽 괄호를 버리는 함수
        }
        else
        {
            while(isp[stack[top]] >= icp[token]) //스택안에 연산자가 높아서 출력되는 경우
            {
                print_token(deleted(&top)); //top포인터가 출력되는 경우
            }
            add(&top, token);
        }
    }
    while((token=deleted(&top)) != eos)
        print_token(token);
    printf("\n");
}
​
precedence get_token(char *symbol, int *n)
{
    *symbol = expr[(*n)++]; //symbol에 0번째 값주고 증가
    switch(*symbol) //symbol값 확인
    {
    case '(': return lparen;    // (
    case ')': return rparen;    // ) 
    case '+': return plus;        // +
    case '-': return minus;        // -
    case '*': return times;        // *
    case '/': return divide;    // /
    case '%': return mod;        // %
    case '\0': return eos;        // end of stack
    default : return operand;    // 피연산자
    }
}
​
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: printf(""); break;
    }
}
​
precedence deleted(int* top)
{
    *top = *top - 1;
    return stack[*top+1];
}
​
void add(int* top, precedence item)
{
    *top = *top + 1;
    stack[*top] = item;
}
​
int eval(void)
{
    precedence token;
    char symbol;
    int op1, op2;
    int n=0;
    int top = -1;
​
    token = get_token(&symbol, &n);
    while( token != eos)
    {
        if(token == operand)
        {
            add_i(&top, ((int)symbol - 48));
        }
        else
        {
            op2 = deleted_i(&top);
            op1 = deleted_i(&top);
            switch(token)
            {
            case plus: add_i(&top, op1+op2);    break;
            case minus: add_i(&top, op1-op2);    break;
            case times: add_i(&top, op1*op2);    break;
            case divide: add_i(&top, op1/op2);    break;
            case mod: add_i(&top, op1%op2);    break;
            }
        }
        token = get_token(&symbol, &n);
    }
    return deleted_i(&top);
}
​
​
void add_i(int* top, int item)
{
    if(*top >= MAX_STACK_SIZE-1)
    {
        printf("STACK is full\n");
        return;
    }
    stack2[++*top] = item;
}
​
int deleted_i(int* top)
{
    if(*top == -1)
    {
        printf("stack2 is empty\n");
        return 0;
    }
    else
    {
        return stack2[(*top)--];
    }
}