[자료구조] 스택 응용 전위표기(prefix), 후위표기(postfix), 중위표기(infix)

중위 표기법(Infix)

중위 표기라는 것은 우리한테 상당히 익숙한 식입니다. 우리는 수식을 쓸때 피연산자 사이에 연산자를 포함시켜 계산을 하게 되죠.

바로 이렇게요.

1+3*2+4/2

이렇게 피연산자(숫자) 사이에 연산자(덧셈, 곱셈, 뺄셈, 나눗셈)가 있는 식을 우리는 중위표기, 바로 Infix라고 부릅니다.

하지만 우리는 왜 prefix라던가 postfix를 쓰는 것일까요?

우리가 계산하는 방식과 컴퓨터가 계산하는 방식이 다르기 때문이지요.

만약 위의 식을 우리가 계산한다면 1+6+2=9라는 것을 금방 알 수 있습니다. 하지만 컴퓨터는 1+3 이후 다음 연산자를 보고 결정해야하기 때문에 계산하기 어려워져 전위표기법이나 후위표기법을 사용합니다.

전위 표기법(Prefix)

이름에서도 알 수 있듯이 전위표기는 연산자가 피연산자 앞에 나오는 방식입니다. 이를테면 3+4는 +34라고 표현할 수 있게 되는 것이죠.

전위 표기식부터는 조금 헷갈릴 수 있으므로 조금 예를 들어 설명하도록 하는 것이 좋겠습니다.

1+2*3+1+2/2는 다음과 같은 변환을 합니다.

우선 연산자 우선순위에 맞게 괄호를 쳐줍니다.

((1+(2*3))+(1+(2/2)))

이제 이 괄호안에 있는 연산자들을 앞으로 빼줍니다.

+((+1*(23))(+1/(22)))

이제 괄호를 모두 없애줍니다.

++1*23+1/22

이렇게 나온 식이 전위표기법으로 나타낸 식입니다.

후위표기법(Postfix)

마찬가지로 연산자가 뒤에 오는 수식입니다. 피연산자는 그대로 쓰면되는 것이죠.

후위표기법은 컴파일러가 사용하는 것으로 스택을 사용하는 예들 중 가장 빈번하게 등장하지요. 따라서 저는 사용빈도가 매우 높은 postfix를 집중적으로 설명하려고 합니다.

우선 1+2*3+(4+2)/2를 마찬가지로 후위표기식으로 바꾸어봅시다.

다시 연산자 우선순위에 맞게 괄호를 처줍니다.

((1+(2*3)+((4+2)/2)))

이제 이 괄호에 있는 연산자를 괄호뒤로 빼줍니다.

((1(23)*)+((42)+2)/))+

이제 괄호를 모두 없애면 후위 표기로 바뀌게 되는 겁니다.

123*+42+2/+

또한 이런 스택을 사용해서도 위의 식을 표현해 낼 수 있습니다.

이제 스택을 이용해서 위의 식을 구해보도록 하지요.

다음과 같은 원칙을 지키면서요. 

1. 숫자가 나오면 그대로 출력한다.

2. (나오면 스택에 push한다.

3. * / 나오면 스택에 push한다.

4. + - 연산이 나오면 여는 괄호('('), 여는 괄호가 없다면 스택의 끝까지 출력하고 그 연산자를 스택에 push한다.

5. 닫는 괄호(')')가 나오면 여는 괄호('(')가 나올때까지 pop하여 출력한다.

          

우선 1이 나오니까 그대로 출력시킵니다. 이제 +가 나오지요. 이것은 연산자이므로 스택에 push하는데 스택에 남아있는 연산자가 없으므로 +만 그냥 push하도록 합니다.

          

이제 2나 나오는 군요. 2는 숫자이므로 그대로 출력합시다. 그 이후에는 *연산자가 나오는데 이것은 규칙 3에 의해 스택에 push합니다.

 

          

 

이제 다시 3을 만났습니다. 숫자니까 그냥 출력합시다.

다음은 +연산자인데요. 규칙4에 의해서 *+를 순서대로 pop하여 출력합니다. 그 후 방금 나온 +연산자를 스택에 집어 넣지요.

          

이제 여는 괄호를 만났군요. 그냥 스택에 집어넣습니다. 

이 후 피연산자 4는 그대로 출력하게 됩니다.

          

이제 +연산자를 스택에 집어넣기 전에 ( 위에 있는 모든 연산자를 출력합니다. 하지만 보시다시피 (이전에 연산자는 없었으니 그냥 +만 push하면 됩니다.

이제 피연산자 2는 그대로 출력해줍니다.

            

닫는 괄호 )를 만나는 군요. 이제 (까지 모든 연산을 비워줍니다. 그러니까 출력에 +를 출력해주는 것이죠.

이 후 나눗셈 연산(/)를 스택에 집어넣습니다. 규칙 3에 의해서요. 

         

2는 그저 숫자이므로 규칙 1에 의해 출력합니다. 이제 식은 끝났습니다. 그렇다면 스택에 남아있는 연산자들은 어떻게 할까요?

식이 끝나게 되면 스택에 있는 연산자들은 모조리 pop하면 됩니다.

그 결과 123*+42+2/+가 되는 것이죠. 위에서 우리가 구한 후위표기식과 같은 것을 알 수 있죠?

이런 후위수식을 어떻게 풀 수 있을까요? 이것 역시 스택을 쓰면 쉽게 풀 수 있습니다.

왜냐면 주제가 스택을 응용하는 것이니까요.

 

        

우선 숫자는 모조리 스택에 집어 넣습니다. 1, 2, 3이 숫자이므로 스택이 집어넣지요. 그 후 연산자가 나오게 되면 스택에 두 수를 꺼내 계산하고 다시 스택에 집어 넣습니다. 2와 3을 꺼내 곱하면 6이 되니 6을 다시 스택에 push하는 것이죠.

        

이 후에 +를 만나게 됩니다. 스택에는 1과 6이 존재하므로 1과 6을 더해 7을 만들어 다시 스택에 집어넣습니다. 그 후 2까지는 숫자이므로 스택에 push하죠.

        

다시 +연산을 만났습니다. 아까 수행했던 것처럼 두 수를 스택에서 pop하여 6을 만들어 스택에 다시 push합니다. 그 후 2는 숫자이니 스택에 push합니다.

     

이제 / 연산이네요. 두 수를 꺼내 6/2연산을 수행하고 3을 스택에 push합니다. 그 후 스택에 넣고 +를 만나게 됩니다. 이제 스택에 있는 7과 3을 꺼내 더하기 연산을 한 후 스택에 다시 집어넣습니다.

이제 모든 식은 종료되었고 스택에는 10이 남았습니다. 마지막에 남은 10이 정답이 되는 것입니다.

이제 어떻게 후위식이 연산되는지 알겠죠?