[자료구조] 스택 (stack) - 후위 표기 수식 계산(postfix expression evaluation), 중위 표기 수식을 후위 표기로의 변환

y = a * (b-c) + d/c

수식(expression)은 연산자, 피연산자, 괄호로 이루어져 있다.
연산자들은 우선순위가 있어 우선순위가 높은 연산자가 먼저 계산된다.
위의 수식에서는 괄호 내의 식이 가장 우선순위가 높기 때문에, 괄호 안의 뺄셈이 가장 먼저 계산되고, 이어서 곱셈, 나눗셈, 덧셈 순으로 계산된다.


중위표기 수식 : y=a*(b-c)+d/c
후위표기 수식(postfix notation) : y=abc-*dc/+

프로그래머가 수식을 연산자가 피연산자 사이에 위치한 중위표기법으로 작성하면, 컴파일러는 이것을 연산자가 피연산자 뒤에 위치하는 후위표기법으로 변환한 후에 스택을 이용해 계산한다.


후위 표기법을 사용하는 이유는?
1. 괄호가 필요 없다. 괄호를 쓰지 않고도 우선 계산하여야 할 내용을 나타낼 수 있다.
2. 연산자의 우선 순위도 생각할 필요가 없다. 식 자체에서 우선순위가 표현되어 있기 때문이다.
3. 수식을 읽으면서 바로 계산할 수 있다. 중위 표현식의 경우, 괄호가 존재하므로 수식을 끝까지 읽은 후에 계산을 시작해야 하기 때문이다.

---

 

후위 표기 수식의 계산 구현

 

수식을 왼쪽에서 오른쪽으로 스캔하며
1. 피연산자이면 스택에 저장
2. 연산자이면 필요한 수만큼의 피연산자를 스택에서 꺼내 연산을 실행하고, 연산 결과를 다시 스택에 저장


y = 8/2 -3 + 3*2 의 전위 표기법으로 작성된 수식에 대한 계산을 해보자.

우선 위의 수식을 후위 표기 수식으로 변경하면 다음과 같다. => y = 82/3 - 32*+
그리고 위의 방법을 이용하여 연산자, 피연산자의 토큰을 차례대로 스캔한다.
차례대로 스캔하며 계산하는 과정에서의 스택의 내용은 다음과 같다.

토큰	스택				설명
	[0]	[1]	[2]	[3]
8	8				8(피연산자) - 스택에 삽입
2	8	2			2(피연산자) - 스택에 삽입
/	4				/(연산자) - 2(두번째 피연산자)와 8(첫번째 피연산자)를 pop하여 첫번째, 두번째 피연산자에 대한 연산 결과값(8/2==4)을 스택에 다시 삽입
3	4	3			3(피연산자) - 스택에 삽입
-	1				-(연산자) - 3(두번째 피연산자)과 4(첫번째 피연산자)를 pop하여 첫번째, 두번째 피연산자에 대한 연산 결과값(4-3==1)을 스택에 다시 삽입
3	1	3			3(피연산자) - 스택에 삽입
2	1	3	2		2(피연산자) - 스택에 삽입
*	1	6			*(연산자) - 2(두번째 피연산자)와 3(첫번째 피연산자)를 pop하여 첫번째, 두번째 피연산자에 대한 연산 결과값(3*2==6)을 스택에 다시 삽입
+	7				+(연산자) - 6(두번째) 피연산자)와 1(첫번째 연산자)를 pop하여 첫번째, 두번째 피연산자에 대한 연산 결과값(1+6==7)을 스택에 다시 삽입

 

---

후위 표기 수식을 코드로 구현한 것을 살펴보기 전에,
문자형을 정수형으로 변환하는 것을 먼저 살펴보기!
https://dojang.io/mod/page/view.php?id=66

C 언어 코딩 도장: 9.6 연습문제: 정수 숫자를 문자로 변환하기

postfix evaluation(후위 표기 계산) - evalPostfix 함수는 다음과 같다.
수식 문자배열 exp[] 을 매개 변수로 전달 받아 함수를 실행한다.

int eval(char exp[])
{
	int op1, op2, value, i = 0;
	int len = strlen(exp);
	char ch;
	StackType s;

	init(&s);
	for (i = 0; i < len; i++) {
		ch = exp[i];
		if (ch != '+' && ch != '-' && ch != '*' && ch != '/')
		{
			value = ch - '0';	// 입력이 피연산자이면
			push(&s, value);
		}//23+4*9+
		else
		{	//연산자이면 피연산자를 스택에서 제거
			op2 = pop(&s);
			op1 = pop(&s);
			switch (ch) { //연산을 수행하고 스택에 저장 
			case '+': push(&s, op1 + op2); break;
			case '-': push(&s, op1 - op2); break;
			case '*': push(&s, op1 * op2); break;
			case '/': push(&s, op1 / op2); break;
			}
		}
	}
	return pop(&s);
}


// int evalPostfix(char exp[]) { int op1, op2, value, i = 0; int len = strlen(exp); char ch; StackType s; init(&s); for (i = 0; i < len; i++) { ch = exp[i]; // 입력이 피연산자이면 if (ch != '+' && ch != '-' && ch != '*' && ch != '/') { value = ch - '0'; // char형 값에서 '0'을 빼서, 숫자 코드값으로 변환하여 int형 변수 value에 저장 push(&s, value); // 아스키코드 값으로 변환한 피연산자 정수값을 스택에 삽입 } else { //연산자이면 피연산자를 스택에서 제거 op2 = pop(&s); // 두번째 피연산자를 먼저 pop op1 = pop(&s); // 첫번째 피연산자를 다음에 pop switch (ch) { //연산을 수행하고 스택에 저장 case '+': push(&s, op1 + op2); break; case '-': push(&s, op1 - op2); break; case '*': push(&s, op1 * op2); break; case '/': push(&s, op1 / op2); break; } } } return pop(&s); } 

스택(int형 데이터를 저장)을 초기화한 후에,
왼쪽부터 문자열의 길이인 len 만큼 후위 표기 수식 exp 문자배열을 스캔한다.
스캔하면서 각 문자를 ch 변수에 저장한다.

ch 변수가 피연산자인 경우(ch 문자가 +,-,*,/가 아닌 경우로 코드 작성),
아스키코드값이 40인 숫자 '0'의 값을 뺌으로써 문자형이었던 정수값을 정수형으로 변환하여 value에 저장하고, 이를 스택에 삽입한다.

연산자인 경우에는, 두 개의 피연산자를 스택에서 pop한다.
이 때, 왼쪽부터 스캔하여 차례대로 스택에 집어넣었기 때문에 먼저 pop하게 되는 숫자는 두번째 피연산자이고, 다음으로 pop하게 되는 숫자가 첫번째 피연산자이다.
첫번째 피연산자에 대하여 두번째 피연산자의 연산을 실행하고, 이를 스택에 push 삽입한다.
(뺄셈과 나눗셈의 연산같은 경우, 피연산자의 순서가 중요하기 때문에 유의하라!)

---

 

중위 표기 수식을 후위 표기 수식으로 변환 (infix to postfix)

중위 표기법을 후위 표기법으로 변환하는 방법은 두가지가 있다.
1) 왼쪽(여는) 괄호를 무시하고, 오른쪽(닫는) 괄호를 만날 때마다 스택에서 연산자를 pop하는 방법
2) 왼쪽(여는) 괄호를 무조건 스택에 삽입하고, 왼쪽 괄호가 삭제될 때 까지 왼쪽 괄호 위에 쌓여있는 모든 연산자를 출력하는 방법이다.


먼저, 1) 첫번째 방법은 다음과 같다.

1. 왼쪽 괄호를 만나면 무시
2. 피연산자는 출력
3. 연산자는 스택에 삽입
4. 오른쪽 괄호를 만나면 스택을 pop하여 출력
5. 수식이 끝나면 스택이 공백이 될 때 까지 pop하여 출력

{(A*B) - (C/D)} 에 대하여 수식을 변환하는 과정을 살펴보자.

토큰	스택				출력	설명
	[0]	[1]	[2]	[3]
{						여는 괄호 무시
(						여는 괄호 무시
A					A	A(피연산자) - 출력
*	*					*(연산자) - 스택에 삽입
B					AB	B(피연산자) - 출력
)					AB*	닫는 괄호 - 스택에서 연산자 pop하여 출력
-	-					-(연산자) - 스택에 삽입
(						여는 괄호 무시
C					AB*C	C(피연산자) - 출력
/	-	/				/(연산자) - 스택에 삽입
D					AB*CD	D(피연산자) - 출력
)					AB*CD/	닫는 괄호 - 스택에서 연산자 pop하여 출력
}					AB*CD/-	닫는 괄호 - 스택에서 연산자 pop하여 출력

2) 두번째 방법은 다음과 같다.

1. 왼쪽 괄호를 만나면 무조건 스택에 push 삽입
2. 연산자는 push 삽입
3. 피연산자는 출력
4. 오른쪽 괄호를 만나면 왼쪽 괄호를 만날 때까지 왼쪽 괄호 위에 쌓여있는 모든 연산자를 pop하여 출력
5. 수식이 끝나면 스택이 공백이 될 때 까지 pop하여 출력

토큰	스택				출력	설명
	[0]	[1]	[2]	[3]
{	{					여는 괄호 - 스택에 삽입
(	{	(				여는 괄호 - 스택에 삽입
A	{	(			A	A(피연산자) - 출력
*	{	(	*			*(연산자) - 스택에 삽입
B	{	(	*		AB	B(피연산자) - 출력
)	{	(			AB*	닫는 괄호 - 스택에서 한 개의 연산자(*) pop하여 출력
-	{	-				-(연산자) - 스택에 삽입
(	{	-	(			여는 괄호 - 스택에 삽입
C	{	-	(		AB*C	C(피연산자) - 출력
/	{	-	/			/(연산자) - 스택에 삽입
D	{	-	/		AB*CD	D(피연산자) - 출력
)	{	-			AB*CD/	닫는 괄호 - 스택에서 연산자(/) pop하여 출력
}					AB*CD/-	닫는 괄호 - 스택에서 연산자(-) pop하여 출력

 

---

괄호가 없는 A-B*C 에 대해서는 어떻게 해야할까?

토큰	스택				출력	설명
	[0]	[1]	[2]	[3]
A					A	A(피연산자) - 출력
-	-					-(연산자) - 스택에 삽입
B					AB	B(피연산자) - 출력
*						??
C						??

위에서 스택에 연산자 '-' 이 삽입되어 있고, AB까지 출력된 상황에서
또다른 * 연산자를 만났을 때에 스택에 저장되어 있는 '-' 뺄셈 연산자를 꺼내 출력해야 할지,
'*' 곱셈 연산자를 그대로 1번 인덱스에 저장해야 할지 모르는 상황이 발생한다.
괄호를 사용하여 연산의 우선 순위를 표현하지 않았기 때문이다.


따라서, 스택에 존재하는 연산자와 현재 처리중인 연산자와의 우선순위를 비교하여야 한다.

1. 현재 처리중인 연산자가 스택에 저장된 연산자보다 우선순위가 낮다면,
스택 상단에 연산자를 먼저 출력한 다음에 처리 중인 연산자를 스택에 넣어야 한다.
2. 현재 처리중인 연산자가 우선순위가 더 높다면,
(위의 예시와 같이 현재 처리중인 '*'가 스택에 저장돼 있는 '-'보다 우선순위가 높은 경우),
현재 처리중인 연산자를 스택에 넣는다.
3. 우선순위가 같은 연산자라면,
1번 경우와 같이, 스택 상단의 연산자를 먼저 출력한다.


위의 예시를 우선순위를 고려하여 다시 변환 과정을 끝까지 이어 따라가보면 다음과 같다.

토큰	스택				출력	설명
	[0]	[1]	[2]	[3]
A					A	A(피연산자) - 출력
-	-					-(연산자) - 스택에 삽입
B					AB	B(피연산자) - 출력
*	-	*				*(연산자) - 스택 상단의 '-'와 비교. 우선순위가 높으므로 스택에 삽입
C					ABC	C(피연산자) - 출력
	-				ABC*	요소 pop
					ABC*-	요소 pop

수식이 끝난 후에는, 스택이 공백이 아닐 때까지 스택에 남아있는 요소들(연산자)을 모두 pop하여 출력한다.

---

위의 중위 표기에서 후위 표기 수식으로의 변환하는 계산을 하는 infix_to_postfix 함수는 다음과 같다.

// 우선순위 체크 반환
int prec(char op) {
	switch (op) {
	// 우선순위가 낮은 순으로	
	case '(': case ')': return 0;
	case '+': case '-': return 1;
	case '*': case '/': return 2;
	}
	return -1;
}

// 중위에서 후위 표시로 변환
void infix_to_postfix(char exp[]) {
	int i = 0;
	char ch, top_op;
	int len = strlen(exp);
	
	StackType s;
	init(&s);

	for (i = 0;i < len;i++) {
		ch = exp[i];

		//연산자인 경우 (+, - , *, /)
		switch (ch) {
		case '+': case '-': case '*': case '/':
			// 연산자는 기본적으로 스택에 push
			// 스택에 있는 연산의 우선순위가 더 크거나 같으면 pop하여 출력
			while (!is_empty(&s) && (prec(ch) <= prec(peek(&s))))
				printf("%c", pop(&s));
			push(&s, ch);
			break;
		case '(':
			push(&s, ch);
			break;
		case ')':
			top_op = pop(&s);
			// 왼쪽 괄호 만날 때까지 출력
			while (top_op != '(') {
				printf("%c", top_op);
				top_op = pop(&s);
			}
			break;
		default: // 피연산자(숫자)
			printf("%c", ch);
			break;
		}
	}
	// print remaining operand
	while (!is_empty(&s))
		printf("%c", pop(&s));
}