Infix(중위표기법) -> Postfix(후위표기법), 그리고 스택 계산

중위표기법(Infix) 이란, 우리가 보통 연산을 할때 쓰는 방법이며, 피연산자(operand) 사이에

 

연산자(+,-,*,/)가 존재한다.

 

2 + 3 * 5 라는 식이 있을 때

 

'2', '3', '5' => 피연산자이고,  '+', '*' 는 연산자, 그리고 이 모든것을 포함하여 토큰이라 부른다.

 

연사자도 두가지로 나뉜다.

1. 이항연산자(항을 2개 요구)     2+3 에서 '+'는 이항연산자 라 할 수 있다.
2. 단항연산자(항을 1개 요구)     +6 에서 '+'는 양수임을 나타내는 연산자이며, 단항연산자이다.

 

후위표기법(Postfix) 이란 연산자가 피연산자 뒤에 오는 수식이다. 컴파일러가 사용하는

 

방식으로 스택을 사용하는 방법에 많이 등장한다. 그럼 앞의 2 + 3 * 5 수식을 Infix->postfix로

 

변환해보자. 변환하는 방법은 세단계로 나뉜다. 

 

1. infix수식에 괄호를 친다.  ->   (2 + (3 * 5))

2. 연산자의 오른쪽 괄호 바로 뒤로 연산자를 이동시킨다. ->   (2 (3 5)*)+

3. 괄호를 지워준다. ->   2 3 5 * +

 

---

그럼 이번에는 스택을 이용하여 " 6 + ( 3 - 2 ) * 4 " 라는 수식을 postfix로 바꾸어 출력해보자.

 

출력내용(정답)을 담을 outstack, 연산자를 담아놓을 opstack을 먼저 선언하였다.

 

6은 피연산자로 opstack에 들어갈일 없이 바로 outstack에 들어간다.

 

+는 자기보다 높은 순위의 연산자를 다 빼내고 opstack에 들어가는데, 비어있으므로

 

그냥 들어간다. 그뒤 왼쪽괄호는 우선순위가 가장 낮기 때문에(오른쪽 괄호는 가장 높음),

 

opstack에 push된다. 그 뒤 3은 oustack에 push, -는 우선순위가 높은 연산자들을 다 빼내고

 

opstack에 들어가지만 '('가 들어있기 때문에 push 된다. 2는 바로 outstack에 push 되고,

 

이제 대망의 오른쪽 괄호가 차례인데, 오른쪽 꽐호는 opstack에 왼쪽괄호까지의 연산자들을

 

다 pop 하기 때문에 '-' 연산자가 opstack에서 pop되고 outstack에 push된다. *는 opstack에

 

남아있는 연산자 + 보다 우선순위가 높기 때문에 +를 pop하지않고 opstack에 들어간다.

 

마지막으로 4가 outstack에 push되고, 더이상 볼 토큰이 없어 for문이 끝났지만 opstack에는

 

연산자가 남아있으므로 전부 pop된 후 outstack에 들어간다.

 

그렇게 최종적으로 6 3 2 - 4 * + 가 출력된다.