[자료구조] 스택(stack)을 이용하여 중위 표기식을 후위 표기식으로 변환해보자

프로그래밍 언어나 컴파일러 이론을 공부하다 보면 후위 표기식(Postfix notation)이라는 개념이 자주 등장하는 것을 볼 수 있습니다.

컴퓨터가 수식을 계산하는 방식은 우리가 흔히 사용하는 중위 표기식(Infix notation)과는 조금 다릅니다. 중위 표기식은 연산자가 피연산자 사이에 위치해 있어 사람에게는 직관적이지만, 컴퓨터가 처리하기 위해서는 연산자 우선순위와 괄호 등을 복잡하게 고려해야 하죠.

이러한 문제를 해결하기 위해 사용되는 것이 바로 후위 표기식(Postfix notation)입니다. 후위 표기식은 연산자가 피연산자 뒤에 위치하며, 괄호가 필요 없고 연산자 우선순위를 고려하지 않고도 순서대로 계산할 수 있다는 장점이 있습니다.

그렇다면 중위 표기식을 후위 표기식으로 어떻게 변환할까요? 이 과정에서 스택(Stack)은 필수적인 자료구조입니다. 스택은 가장 마지막에 들어온 것이 가장 먼저 나오는(LIFO) 특성을 갖고 있어, 연산자의 우선순위를 임시로 저장하고 관리하는 데 매우 유용하기 때문이죠.

중위 표기식을 후위 표기식으로 바꿀 때 스택에서 일어나는 일

* 스택에 데이터를 추가하는 것을 푸시(push), 스택에서 데이터를 제거하는 것을 팝(pop)이라고 합니다.

 

중위 표기식을 후위 표기식으로 변환하는 과정을 단계별로 자세히 살펴볼까요? 이 과정은 입력된 식을 왼쪽에서 오른쪽으로 한 글자씩 읽어 들이는 토큰화(Tokenization) 과정과 스택을 이용한 연산자 관리로 이루어집니다.

1. 피연산자(Operand)가 들어오면 바로 출력하여 후위 표기식에 추가합니다.
2. 연산자(Operator)가 들어오면 우선순위를 따져 스택에 푸시(push)하거나 팝(pop)하는 작업을 합니다.
   • 스택이 비어 있거나 스택의 맨 위 연산자가 현재 들어온 연산자보다 우선순위가 낮으면 현재 연산자를 스택에 push합니다.
   • 스택의 맨 위(top) 연산자가 현재 들어온 연산자보다 우선순위가 같거나 높으면 스택의 맨 위 연산자를 pop하여 후위 표기식에 추가하고, 이 과정을 반복하여 현재 연산자보다 우선순위가 낮거나 스택이 빌 때까지 진행합니다. 그 후 현재 연산자를 스택에 push합니다.
3. 여는 괄호 '('는 연산자의 우선순위를 무시하고 스택에 푸시됩니다. 이는 새로운 괄호 묶음이 시작되었음을 알리고, 그 안의 연산자들이 먼저 처리되어야 함을 나타냅니다.
4. 닫는 괄호 ')'가 나오면 스택에서 가장 가까운 여는 괄호 '('를 만날 때까지 스택에 있는 모든 연산자를 팝하여 후위 표기식에 추가합니다. 이렇게 함으로써 괄호 안의 연산자들이 먼저 처리될 수 있도록 보장합니다. 팝된 연산자들은 후위 표기식에 추가되지만, '('와 ')'는 후위 표기식에 포함되지 않고 버려집니다.
5. 모든 토큰을 처리한 후, 스택에 남아있는 모든 연산자를 pop하여 후위 표기식에 추가합니다.

이제 실제 예제를 통해 각 토큰별 동작을 확인해 보겠습니다.

 

예제: 중위 표기식 A-B/C-D*E를 후위 표기식으로 바꿔보자

읽은 토큰	동작	스택의 변화	후위 표기식
A	피연산자 A를 출력합니다.	[ ]	A
-	스택이 비어 있으므로 '-'를 push합니다.	[-]	A
B	피연산자 B를 출력합니다.	[-]	AB
/	스택의 top(맨 위) 연산자(-)보다 우선순위가 높으므로 '/'를 push합니다.	[-, /]	AB
C	피연산자 C를 출력합니다.	[-, /]	AB C
-	스택의 맨 위 연산자'/'의 우선순위가 '-'보다 높기 때문에 연산자 '/'를 pop하고 출력합니다. '/'가 삭제된 자리에 '-'를 저장해야 하지만, 이제 스택 top에 있는 연산자는 '-'입니다. 같은 우선순위의 연산자끼리 만났기 때문에, 이미 스택 top에 있는 연산자의 계산이 먼저 되어야 합니다. 따라서 스택 top에 저장되어 있는 '-' 연산자를 pop하고 출력합니다. 그리고 현재 들어온 '-' 연산자를 push합니다.	[-]	AB C / -
D	피연산자 D를 출력합니다.	[-]	AB C / - D
*	스택의 top 연산자(-)보다 우선순위가 높으므로 '*'를 push합니다.	[-, *]	AB C / - D
E	피연산자 E를 출력합니다.	[-, *]	AB C / - D E
(끝)	모든 토큰을 처리한 후, 스택에 남아있는 모든 연산자(*, -)를 pop하여 출력합니다.	[ ]	AB C / - D E * -

 

위 과정을 요약해보면, 피연산자는 바로 출력하고, 연산자는 우선순위를 비교하여 스택에 푸시하거나 팝하는 작업을 반복하는 것입니다. 이 과정을 통해 사람이 이해하기 쉬운 중위 표기식을 컴퓨터가 쉽게 처리할 수 있는 후위 표기식으로 변환할 수 있습니다.