[Stack] 전위수식(prefix), 후위수식(postfix), 중위수식(infix)

[Stack] 전위수식(prefix), 후위수식(postfix), 중위수식(infix)

 

중위수식(Infix)

중위수식은 일반적으로 우리가 수식을 사용할 때 피연산자 사이에 연산자를 표기하는 방식

Ex) 1+3*2+4/2

피연산자(숫자) 사이에 연산자(덧셈, 곱셈, 뺄셈, 나눗셈)가 있는 식을 중위수식(Infix) 이라고 합니다.

하지만 컴퓨터는 직관적으로 연산자의 우선순위에 따라 연산을 수행할 수 없으므로 연산자 우선순위에 따라 계산해주기 위해 Stack 자료구조를 사용하여 prefix, postfix 와 같은 수식으로 변경하여 계산을 해줘야 합니다.

 

전위수식(Prefix)

전위수식은 연산자가 피연산자 앞에 나오는 방식으로 5+8는 +58라고 표현하는 것입니다.

Ex) 1+2*3+1+2/2  =>  ((1+(2*3))+(1+(2/2))) => +((+1*(23))(+1/(22))) => ++1*23+1/22

이와 같이 연산자 우선순위에 따라 괄호로 묶어주고 연산자를 앞으로 빼주면 전위수식으로 이해하기 쉽게 변경 할수 있습니다.

 

후위수식(Postfix)

후위수식은 연산자가 피연산자 뒤에 오는 수식입니다. 5+8는 58+라고 표현하는 것입니다.

후위수식은 컴파일러가 사용하는 방식으로 스택을 사용하는 예로 설명 해보겠습니다.

Ex) 1+2*3+(4+2)/2 => ((1+(2*3)+((4+2)/2))) => ((1(23)*)+((42)+2)/))+ => 123*+42+2/+

위 와 같은 변환 과정을 Stack을 사용해 변경 해보도록 하겠습니다.

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

2. ( 나오면 스택에 push

3. * / 나오면 스택에 push

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

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

숫자 1이 나오니까 그대로 출력. 연산자 '+'가 나오므로 스택에 push하고 스택에 남아있는 연산자가 없으므로 '+'만 push

그다음 숫자 2가 나오니 그대로 출력. 이후 '*' 연산자가 나오므로 규칙 3에 의해 스택에 push합니다.

 

그 다음 숫자 3이 나오니 그대로 출력. 다음은 '+' 연산자로 규칙4에 의해서 '*' '+' 를 pop하여 출력. 그 후 방금 나온 '+'연산자를 스택에 push.

 

이제 여는 괄호를 스택에 push. 이후 숫자 4는 그대로 출력.

그리고 '+'연산자를 스택에 push하기 전에 '(' 위에 있는 모든 연산자를 출력해야 하나 '(' 이전에 연산자가 없으므로 '+'만 push

이제 숫자 2는 그대로 출력해줍니다.

닫는 괄호 ')' 가 나왔으니 이제 '(' 까지의 모든 연산을 pop하게 되어 '+'를 출력.

이 후 규칙 3으로 나눗셈 연산 '/' 를 스택에 집어넣습니다.  

숫자 2를 출력해주고 스택에 남은 연산자를 모두 pop 해줍니다.

그 결과 123*+42+2/+ 와 같이 후위수식으로 변경이 완성 됩니다.

 

이 후위수식을 컴퓨터 연산을 통해 계산하기 위해서 역시 Stack을 사용합니다.

우선 숫자는 모조리 스택에 집어 넣습니다. 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이 남게됩니다.

 

이렇게 후위수식 변경 법 및 연산 방법 까지 알아보았습니다. 끝.