후위 표기법

수식을 표기하는 방법에는 우리가 흔히 사용하는 중위 표기법말고도 전위 표기법과 후위 표기법이라는 것이 있다.

중위 표기법 -> ( 1 + 2 ) * 7
후위 표기법 -> 1 2 + 7 *
전위 표기법 -> * + 1 2 7

이러한 전위, 후위 표기법의 특징은 연산자의 순서에 따라 연산순서가 결정되기 때문에 연산자 우선순위나 소괄호가 필요없다는 점이다.

 

중위 표기법을 후위 표기법으로 바꾸는 법

1.  피연산자가 들어오면 바로 출력한다.
2. 연산자가 들어오면 스택에 들어있는 연산자와 비교해서 스택에 있는 연산자보다 우선순위가 높으면 스택에 쌓고, 낮으면 스택에 있는 들어온 연산자보다 우선순위가 낮은 연산자를 모두 출력하고, 들어온 연산자를 스택에 쌓는다.
   
   연산자 우선순위는
   ㆍ  *, / : 제일 높다
   ㆍ  +, - : 두번째로 높다
   ㆍ  ( : 가장 작다
3. '('는 무조건 스택에 쌓는다.
4. ')'를 만나면 '('를 만날 때까지 스택에서 출력한다.    ( 소괄호는 제외 )

#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include "ListBaseStackCal.h"
 
int GetopPrec(char op)
{
    switch (op)
    {
    case'*':
    case'/':
        return 4;
    case'+':
    case'-':
        return 2;
    case'(':
        return 1;
    }
 
    return -1;
}
 
int WhoPrecOp(char op1, char op2)
{
    int op1Prec = GetopPrec(op1);
    int op2Prec = GetopPrec(op2);
 
    if (op1Prec > op2Prec)
    {
        return 1;
    }
    else if (op1Prec < op2Prec)
    {
        return -1;
    }
    else return 0;
}
 
void ConvToRPNExp(char exp[])
{
    Stack stack;
    int expLen = strlen(exp);
    char* convExp = (char*)malloc(expLen + 1);
 
    int i, idx = 0;
    char tok, popOp;
 
    memset(convExp, 0, sizeof(char) * expLen + 1);
    StackInit(&stack);
 
    for (i = 0; i < expLen; i++)
    {
        tok = exp[i];
        if (isdigit(tok)) convExp[idx++] = tok;
        else
        {
            switch (tok)
            {
            case'(':
                SPush(&stack, tok);
                break;
            case')':
                while (1)
                {
                    popOp = SPop(&stack);
                    if (popOp == '(')
                        break;
                    convExp[idx++] = popOp;
                }
                break;
            case'+':case'-':
            case'*':case'/':
                while (!SIsEmpty(&stack)&&WhoPrecOp(SPeek(&stack),tok)>=0)
                {
                    convExp[idx++] = SPop(&stack);
                }
                SPush(&stack, tok);
                break;
            }
        }
    }
 
    while (!SIsEmpty(&stack))
    {
        convExp[idx++] = SPop(&stack);
    }
 
    strcpy(exp, convExp);
    free(convExp);
}