스택응용 - infix 2 postfix 변환

이번에는 스택을 이용하여 중위표기식을 후위표기식으로 바꾸는 것을 해보자. 실행결과는 다음과 같이 보여주고 싶다.

사칙연산과 괄호를 가진 수식

비교 및 논리연산자를 포함한 수식

중위표기식에서 후위표기식으로 바꾸기 위해서는 다음과 같은 사항을 고려해야 한다.

(1) 괄호를 처리할 수 있어야 한다. 괄호는 이항연산자가 아니므로 별도로 처리되어야 하고 괄호로 묶인 부분은 최우선으로 실행된다.

(2) 이항연산자의 우선순위가 고려되어야 한다. 일단 우리는 다음과 같은 우선순위를 고려한다.

우선순위	연산자
1	&, |  (and, or)
2	>, =, <
3	+, -
4	*, /

그러면 우선순위에 따라 일어나는 일은 다음과 같다. 

이항연산자는 항상 다음에 올 부분(오른쪽 피연산자)이 먼저 계산된 후에 연산을 수행할 수 있으므로 뒤에 오는 항을 확인해야 한다. 다음에 오는 연산자가 나보다 더 우선순위가 크면 나는 기다려야 한다. 반면에 다음에 오는 연산자가 나보다 우선순위가 작거나 같으면 나는 먼저 계산하면 된다. (여기서는 결합규칙은 고려하지 않는다.)

후위표기식으로 바꾸기 위해서는 연산자가 계산될 순서가 되었을 때, 즉 좌 우의 피연산자 부분이 먼저 출력된 후 출력되면 된다. 뒷부분에 올 피연산자가 먼저 계산되어야 하면 기다려야 한다(즉 나중에 출력되어야 한다). 기다리던 연산자는 뒷부분이 계산되다가 자기보다 더 낮은 연산자가 오면 이제 출력될 수 있다.

예를 들어 a > 2 - b * c ... 라는 수식을 생각해 보자. >는 -보다 낮고 -는 *보다 낮으므로 *가 수행되고 나서 -와 >가 수행될 수 있다. ... 부분에 >보다 더 낮은 우선순위 연산(&나 |)이 오면 드디어 >는 출력될 수 있다.  그 경우 위의 수식은 a 2 b c * - > 순서로 출력된다. 

우리는 기다려야 하는 연산에 대해서는 스택에 넣는다. 다음 연산자가 나왔을 때 스택에 그보다 높은 연산자가 들어있으면 먼저 실행시켜야 한다. 후위표기식으로 바꾸는 알고리듬은 다음과 같다.

1. 입력의 다름 토큰이 숫자나 변수이름이면 바로 출력한다.
2. 연산자 op을 만나면 스택에서 op보다 높은 것을 모두 pop해서 출력하고 그 op을 푸시한다.
3. 여는 괄호는 푸시한다.
4. 닫는 괄호를 만나면 여는 괄호까지 스택에 있는 것을 모두 pop해서 출력한다.
5. 입력의 끝을 만나면 스택에 있는 것을 모두 pop해서 출력한다.

스택에 들어있는 연산자는 항상 우선순위가 오름차순이 될 것이다. 즉 계속해서 나보다 높은 연산자가 들어오면 스택에 쌓이게 되고, 나보다 낮은 연산자가 나와야 스택에서 나갈 수 있다. 여는 괄호는 우선순위가 가장 높고 닫는 괄호는 가장 낮다고 볼 수 있다. 단, 괄호는 출력하지 않는다. 

int infix2postfix(void)
{
	stack_t stack;
	char token[10];
	init_stack(&stack);
	while (1) {
		scanf_s("%s", token, 10);
		if (strcmp(token, "end") == 0)
			break;

		if (is_operand(token))
			printf("%s", token);   // 피연산자는 그냥 출력
		else if (token[0] == '(')
			push(&stack, token);   // (는 푸시
		else if (token[0] == ')') {
			while (strcmp(peek(&stack), "(") != 0)
				printf("%s", pop(&stack));  // (가 나올 때까지 팝해서 출력
			pop(&stack);  // (는 팝하고 출력하지 않음
		} else {
			while (!is_empty(&stack) && prec(token) <= prec(peek(&stack)))
				printf("%s", pop(&stack));   // 스택의 우선순위가 높은 것을 모두 pop해서 출력
			push(&stack, token);  // 이번 연산자는 푸시
		}
	}
	while (!is_empty(&stack))
		printf("%s", pop(&stack)); // 스택에 있는 나머지 연산자를 모두 출력
	printf("\n");
}

이 코드에서 스택의 요소 타입은 char*임을 주의해야 한다. 즉 stack.h에서 typedef char* element;로 바꾸어 주어야 한다. 또한 push에서 scanf해서 읽은 문자열을 가진 포인터를 그대로 스택에 넣으면 안 되고 malloc을 통해 메모리 할당한 후 strcpy해 주어야 한다. 포인터를 요소 타입으로 가지는 자료구조에서 주의해야 하는 부분이다. 넘겨받은 포인터를 넣으면 되는지, 아니면 새로운 객체를 만들어서 데이터를 복사해야 하는지(버퍼로 쓰이는 메모리) 확인해야 한다. 아래 예에서는 입력에서 읽은 버퍼의 주소가 char* item에 전달되므로 그것을 그대로 스택 탑에 지정하면 안되는 경우다. (지역변수인 token 배열의 주소를 스택에 푸시하면 안 됨!)

void push(stack_t* s, elem_t item)
{
	if (is_full(s)) {
		...
	s->data[++(s->top)] = (char*)malloc(strlen(item)+1);
	strcpy_s(s->data[s->top], strlen(item) + 1, item);
}

앞의 화면 스크린샷에서처럼 토큰을 하나씩 읽을 때마다 지금까지 만들어진 후위표기식을 스택의 상태와 함께 보여주기 위해서는 다음과 같은 함수를 이용할 수 있다. 후위표기식을 가진 출력 형태를 out 배열에 strcat으로 쌓고 그것을 단계별로 스택과 함께 보여준다.

void output(char* out, char* token)
{
	strcat_s(out, 200, token);
	strcat_s(out, 200, " ");
}

이것을 print_stack(&stack, out);으로 다음 함수를 호출하면 된다.

void print_stack(stack_t* s, char* out)
{
	printf("%-30s [stack] ", out);
	for (int i = 0; i <= s->top; i++) {
		printf("%s ", s->data[i]);
	}
	printf("\n");
}