[자료구조] 후위 수식(Postfix)

 

이번 포스팅에서는 후위 수식에 대해서 알아보겠습니다.

 

수식을 표현하는 방법은 크게 3가지가 있습니다.

• infix notation : a * b (연산자가 피연산자 사이에 위치합니다.)
• prefix nonation: * a b (연산자가 피연산자들 앞에 위치합니다.)
• postfix nonation: a b * (연산자가 피연산자들 뒤에 위치합니다.)

이 결과들은 모두 a와 b를 곱한 값을 의미합니다.

 

이중에서 우리에게 익숙한 방식은 infix notation일 겁니다.

 

하지만 infix notation은 약간의 단점이 존재합니다.

 

연산자들이 가지는 우선 순위가 있지 때문에 이에 맞춰서 연산을 해야한다는 문제점이 있습니다.

 

따라서 임의로 연산자의 우선순위를 조정하기 위해서는 괄호를 사용해야하는 번거로움이 생깁니다.

 

하지만 postfix notation과 prefix notation은 괄호가 필요 없습니다.

 

그리고 컴퓨터는 postfix notation을 더욱 선호합니다.

 

따라서 이번 시간엔 postfix notaion에 대해서 알아보겠습니다.

 

코드를 통해서 알아볼 것인데 시작하기 앞서 어떤식으로 결과가 출력되도록 할 것인지 설명드리겠습니다.

 

expr이라는 배열에 후위 수식으로 바꾸고 싶은 중위 수식을 저장할 것입니다.

 

그리고 expr에 저장된 피연산자와 연산자를 구분하여 처리할 것입니다. 

 

만약 피연산자라면 바로 출력하도록 할 것이며, 연산자면 우선순위에 따라 스택을 통해 처리할 예정입니다.

 

또한 여는 괄호가 나오면 괄호는 모든 우선순위를 이기는 문자이므로 닫는 괄호가 나올때까지 스택에 저장할 겁니다.

 

이해를 돕기 위해서 간단한 중위 수식을 후위 수식으로 바꿔보는 과정을 보여드리겠습니다.

 

바꿀 중위 수식은 a*(b+c)/d 입니다.

1. a는 피연산자이므로 그냥 출력.

2. *는 연산자이므로 stack에 저장.

3. 여는 괄호가 나왔으므로 스택에 push.

4. b는 피연산자이므로 그냥 출력.

5. 괄호가 열려있기 때문에 +도 스택에 저장.

6. c는 피연산자이므로 그냥 출력

7. 닫는 괄호가 나왔으므로 여는 스택에서 여는 괄호가 나올때 까지 pop 하여 출력 (이때 괄호들은 출력하지 않음).

8. /는 연산자이며 *연산자와 우선순위가 같으므로 *를 pop하여 출력하고 /를 push.

9. d는 피연산자이므로 그냥 출력.

10. expr을 다 돌아서 eos(end of string)이 나왔으므로 stack을 모두 pop하여 출력.

 

이 순서대로 output을 써보면 abc+*d/가 됩니다.

---

코드를 통해서 알아볼 것입니다. 천천히 변수들의 의미부터 차근차근 이해해보겠습니다.

#define MAX_STACK_SIZE 100
#define MAX_EXPR_SIZE 100

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

precedence stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];

static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0}; 
//열거형의 순서대로 우선순위 값입니다. 클 수록 강합니다.

static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};
//열거형의 순서대로 우선순위 값입니다. 클 수록 강합니다.
//모두 enum 변수의 값을 인덱스로 사용하여 우선순위를 가지도록 합니다.
// isp와 icp의 자세한 설명은 코드를 설명하면서 만나는데 그때 제대로 하겠습니다.

 

enum은 열거형으로 제일 앞에 있는 값부터 0, 1, 2, 3...의 값을 차례대로 가집니다. 타입은 precedence가 되겠습니다.

 

그리고 이 값을 저장할 배열을 stack이라고 선언해주었습니다.

 

또한 expr은 우리에게 주어진 수식을 저장할 배열이며, 앞에서부터 하나씩 꺼내서 볼 예정인 문자열입니다.

 

일단 main함수부터 보여드리겠습니다.

void main()
{
  sprintf(expr, "6/2-3+4*2");
  printf("infix  : %s\n", expr);
  printf("postfix: ");
  postfix();
}

별거 없습니다. 우리에게 주어진것은 postfix라는 함수입니다.

 

expr에는 우리가 바꾸고 싶은 infix수식을 저장하였습니다.

 

이 함수를 파해쳐 보겠습니다.

 

변수들부터 하나하나 주석으로 설명하겠습니다.

void postfix()
{
  precedence token; //어떤 문자인지 확인하고(괄호인지, +인지, *인지)
 	 	   //enum 변수의 값을 가지는 변수, 밑에 getToken함수 설명을 보면 알 수 있음.
  char symbol; //expr에서 우리가 볼 문자
  int n = 0; //expr에 접근하기 위해 인덱스를 나타내도록 설정한 변수
  top = 0; 
  stack[0] = eos; //위에서 정한 top = 0;의 연장선
	   	  //stack의 제일 밑에는 \0(end of string)을 미리 넣어두고 
		 //나중에 이 문자를 만나면 코드의 실행을 멈추도록 하기위해 설정한 것입니다.

  for(token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n))
  {
    if(token == operand) printf("%c", symbol);
    else if(token == rparen)
    {
      while(stack[top] != lparen) printToken(pop());
      pop();
    }
    else
    {
      while(isp[stack[top]] >= icp[token]) printToken(pop());
      push(token);
    }
  }

  while((stack[top] != eos)) printToken(pop());
}

 

for문을 보면 getToken이라는 함수가 symbol과 n의 주소를 매개변수로 삼고 있습니다.

 

getToken을 살펴보고 돌아오겠습니다.

precedence getToken(char* symbol, int *n)
{
  *symbol = expr[(*n)++];

  switch(*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;
    default: return operand;
  }
}

 

단순합니다. call by reference로 symbol과 n이 선언된 함수 밖에서 symbol과 n의 값을 변경시키고 싶기 때문에 주소를 넘겨준 것입니다.

 

symbol은 expr에 입력된 문자를 앞에서 부터 하나씩 받아옵니다.

 

이 받아온 문자를 switch-case문을 통해서 어떤 문자인지 확인합니다.

 

이후에는 그에 맞는 enum 변수를 반환합니다.

 

만약 문자가 아니라면 피연산자이기 때문에 oprand를 반환하도록 하였습니다.

 

따라서 반환된 값은 precedence 타입의 enum 변수이 token에 이 값이 저장되었습니다.

 

이제 다시 for문을 살펴보겠습니다.

for(token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n))
  {
    if(token == operand) printf("%c", symbol);
    else if(token == rparen)
    {
      while(stack[top] != lparen) printToken(pop());
      pop();
    }
    else
    {
      while(isp[stack[top]] >= icp[token]) printToken(pop());
      push(token);
    }
  }

for문의 조건은 getToken을 통해 얻어낸 token이 eos가 아닐때 반복입니다. 만약 eos가 나왔다면 expr을 다 훑었다는 의미이므로 더 이상의 반복을 없도록 한 것입니다. 

 

그 뒤에 다시 token = getToken(&symbol, &n)을 작성하였는데 이는 다음 단계를 의미합니다.

 

처음에 써주었던 token = getToken(&symbol, &n) 는 최초의 선언이고, 마지막에 써주었던 token = getToken(&symbol, &n) 는 다음 반복에서 사용할 token을 의미합니다.

 

이제 내부의 조건문을 살펴보겠습니다.

 

만약 얻어낸 토큰이 oprand 라면 그대로 작성하여줍니다.

 

그게 아니라 닫는 괄호를 만났다면??

 

스택의 탑을 확인하고 이 문자가 여는 괄호가 아니라면 printToken을 통해서 pop한 연산자를 출력합니다.

 

(printToken 함수는 일단 문자를 출력한다고만 생각해주시기 바랍니다 아주 아주 간단하기 때문에 맨 밑에서 다루겠습니다.)

 

그리고 pop을 계속하다가 마침내 스택의 탑이 여는 괄호라면 while문을 빠져나오고 여는 괄호를 빼주기 위해 pop()을 실행합니다.

 

또 그게 아니라면 isp[stack[top]]과 icp[token]을 비교합니다.

 

만약 isp값이 더 크거나 같다면 while문을 통해서 조건이 틀릴때까지 pop한 문자를 printToken해줍니다.

 

이 비교가 무슨 의미인지 설명드리겠습니다.

static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0};
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};

먼저 isp는 in stack precedence로 스택 안에있는 값의 우선순위입니다.

 

그리고 icp는 지금 확인하고 있는 문자의 우선 순위입니다. 두 배열을 보면 다  배열의 첫번째 인덱스의 값을 제외하고는 다 같다는 것을 알 수 있습니다.

 

위에서 이 배열은 enum배열에 저장된 변수들이 가지는 우선순위로 사용한다고 말씀드렸습니다.

 

배열안에 있는 여는 괄호는 우선순위가 제일 낮은 반면에 지금 막 확인하고 있는 따끈따끈한 토큰이 여는 괄호라면 제일 높은 우선 순위를 가집니다.

 

이유는 간단합니다.

 

expr을 순차적으로 확인하다가 여는 괄호를 만나면 이 여는 괄호 안에 있는 연산자들은 그 어떤 연산자들보다 당연히 우선시 되어여 할 것입니다.

 

따라서 여는 괄호가 20이라는 우선순위를 가지게 됩니다.

 

그리고 ''만약 isp값이 더 크거나 같다면 while문을 통해서 조건이 틀릴때까지 pop한 문자를 printToken해줍니다.'' 이 문장에 의하여 스택 안에 있는 문자의 우선순위가 더 높다면 팝된 문자가 출력될 것입니다.

 

여는 괄호는 닫는 괄호가 나오기 전까지 stack에서 나오면 안됩니다.

 

따라서 일반적인 연산자들을 만났을 때 나오는 일이 없어야 하기 때문에 우선순위가 가장 낮게 설정되었다고 볼 수 있습니다.

 

다시 본론으로 돌아가서 isp로 스택에 저장된 연산자와 icp로 현재 보고있는 연산자를 비교하여 스택안에 있는 연산자의 우선순위가 높다면 계속해서 출력을 해줍니다.

 

그러다가 현재 확인하고 있는 문자의 우선순위가 높아지는 순간이 오면 while문을 빠져나오고 현재 확인하고 있는 문자를 push를 통해서 스택에 저장해줍니다.

 

그리고 postfix 내부에 맨 밑에 있는 코드입니다. 

while((stack[top] != eos)) printToken(pop());

expr을 다 돌아버린 상태에서 실행되는 코드로  for문을 실행하는 동안 출력되지 못하고 스택에 쌓인 문자들을 모두 출력해주는 코드입니다.

 

이렇게 하면 모든 과정이 마무리 되었습니다.

 

그리고 아주 간단해서 설명하지 않았단 printToken함수를 설명하고 전체 코드를 첨부한 다음 포스팅을 끝내겠습니다.

void printToken(precedence token)
{
  switch(token)
  {
    case lparen: printf("("); break;
    case rparen: printf(")"); break;
    case plus: printf("+"); break;
    case minus: printf("-"); break;
    case times: printf("*"); break;
    case divide: printf("/"); break;
    case mod: printf("%%"); break;
  }
}

정말 정말 간단합니다.

 

token을 매개변수로 받아와서 그 토큰을 switch case를 통해서 어떤 문자인지 확인하고 그 문자를 출력합니다.

---

<전체 코드> (스택을 이미 알고 있는 전제 하에 설명한 글이므로 스택은 설명하지 않았습니다.)

#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;
precedence stack[MAX_STACK_SIZE];
char expr[MAX_EXPR_SIZE];
int top = -1;

static int isp[] = {0, 19, 12, 12, 13, 13, 13, 0};
static int icp[] = {20, 19, 12, 12, 13, 13, 13, 0};

void postfix();
precedence getToken(char *, int *);
void push(precedence);
precedence pop();
void stackFull();
precedence stackEmpty();
void printToken(precedence);

void main()
{

  sprintf(expr, "6/2-3+4*2");
  // sprintf(expr, "a*(b+c)/d");
  printf("infix  : %s\n", expr);
  printf("postfix: ");
  postfix();
}

void postfix()
{
  precedence token;
  char symbol;
  int n = 0; 
  top = 0;
  stack[0] = eos;

  for(token = getToken(&symbol, &n); token != eos; token = getToken(&symbol, &n))
  {
    if(token == operand) printf("%c", symbol);
    else if(token == rparen)
    {
      while(stack[top] != lparen) printToken(pop());
      pop();
    }
    else
    {
      while(isp[stack[top]] >= icp[token]) printToken(pop());
      push(token);
    }
  }

  while((stack[top] != eos)) printToken(pop());
}

precedence getToken(char* symbol, int *n)
{
  *symbol = expr[(*n)++];

  switch(*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;
    default: return operand;
  }
}

void printToken(precedence token)
{
  switch(token)
  {
    case lparen: printf("("); break;
    case rparen: printf(")"); break;
    case plus: printf("+"); break;
    case minus: printf("-"); break;
    case times: printf("*"); break;
    case divide: printf("/"); break;
    case mod: printf("%%"); break;
  }
}

void push(precedence item)
{
  if(top >= MAX_STACK_SIZE) stackFull();
  stack[++top] = item;
}

precedence pop()
{
  if(top == -1) return stackEmpty();
  return stack[top--];
}

void stackFull()
{
  exit(1);
}

precedence stackEmpty()
{
  exit(1);
}

 

 

고생하셨습니다~~!!