9.2 스택을 이용한 수식 파서 [디딤돌 자료구조와 알고리즘 with C++]

9.2 스택을 이용한 수식 파서

수학에서 수식은 피연산자 사이에 연산 기호를 표기하는데 이를 중위 표기라 얘기합니다. 그런데 컴퓨터 프로그램에서 중위 표기의 수식을 계산할 때 순차적으로 수행하면 수학에서의 연산 결과가 다르게 나옵니다. 예를 들어 2+3*5의 연산은 +연산보다 *연산을 먼저하기 때문에 17이지만 순서대로 연산을 수행하면 2+3을 수행한 후에 5*5를 수행해서 25가 나옵니다.

 

컴퓨터 프로그램에서 제대로 수식을 계산하기 위해서는 우선 순위에 맞게 연산의 순서를 파악한 후에 계산해야 합니다. 수식을 연산 순서에 맞게 표현하는 방법 중에 연산 기호의 자식으로 피연산자를 도식하는 수식 파서 트리를 이용해서 설명해 볼게요.

 

2+3*5 수식에서 +연산의 피연산자는 2와 3*5의 연산 결과입니다. 그리고 *연산의 피연산자는 3과 5입니다. 이를 수식 파서 트리로 도식하면 다음과 같습니다.

그리고 컴퓨터 프로그램에서 계산하기 쉽게 연산 기호를 피연산자보다 뒤에 표기하는 것을 후위 표기라 하는데 3*5는 3 5 *로 표기하고 2+3*5는 2 3 5 * + 로 표기합니다. 수식 파서 트리를 후위 운행하는 순으로 표기한 것이죠. 그리고 이렇게 후위 표기한 것을 피연산자는 스택에 보관하고 피연산자는 스택에 보관한 두 개의 피연산자를 꺼내와서 계산한 후에 스택에 보관하면 맨 마지막에 스택에 남아있는 값이 수식의 연산 결과입니다.

 

 

 

 

 

먼저 스택을 이용하여 중위 표기의 수식을 후위 표기로 바꾸는 원리를 알아봅시다.

 

이 책에서 입력 수식은 부호없는 수와 사칙 연산, 괄호만 사용하는 것으로 한정해서 설명하기로 할게요. 입력한 수식 표현 외의 계산 결과는 부호있는 수도 가능하게 하기로 해요.

 

중위 표기의 수식을 후위 표기로 바꿀 때는 우선 순위가 높은 것을 먼저 수행하기 위해 우선 순위가 낮은 것과 순서를 바꾸어야 하는데 이를 위해 스택을 사용합니다.

수는 모든 연산자보다 우선하므로 스택을 이용할 필요없이 배열에 보관합니다.

 

스택이 비어있을 때 연산자를 만나면 스택에 보관합니다.

 

더하기와 빼기 부호를 만나면 다른 연산보다 우선 순위가 낮으므로 스택에 보관했던 모든 연산 기호를 꺼내어 배열에 보관하고 자신(더하기와 빼기 부호)를 스택에 보관합니다.

 

곱하기나 나누기를 만나면 스택에 보관된 것을 꺼내어 자신보다 우선 순위가 낮은 더하기나 빼기를 만나면 꺼낸 것을 다시 스택에 보관한 후에 자신도 스택에 보관합니다. 이렇게 하면 나중에 꺼내는 순서는 우선 순위가 높은 순으로 꺼내게 됩니다. 스택에서 꺼낸 부호가 곱하기나 나누기일 때는 꺼낸 부호를 배열에 보관하고 자신을 스택에 보관합니다.

 

그리고 시작하는 괄호를 만나면 자신의 짝이 되는 끝나는 괄호 사이에 있는 수식을 별도의 스택을 이용하여 후위 수식으로 바꾼 후에 배열에 보관합니다.

 

수식의 끝을 만나면 스택에 보관한 기호를 꺼내어 배열에 보관하면 후위 표기로 바뀝니다.

 

2 + 3 * (5 + 4 * 2) – 3 + 6 수식을 예로 들어 구체적으로 설명해 볼게요.

 

2는 수이므로 배열에 보관합니다.

남은 입력 수식:  + 3 * (5 + 4 * 2) – 3 + 6

+는 스택에 있는 모든 기호를 꺼내어 배열에 보관한 후에 자신을 스택에 보관합니다.

 

3은 수이므로 배열에 보관합니다.

*는 스택에 있는 것을 꺼내어 자신과 연산자 우선 순위를 비교합니다. 꺼낸 부호가 + 이므로 꺼낸 것을 다시 스택에 보관한 후에 자신도 스택에 보관합니다.

남은 입력 수식: (5 + 4 * 2) – 3 + 6

(를 만나면 자신의 짝인 ) 사이에 있는 5 + 4 * 2 를 후위 수식으로 변환합니다. 이를 위해 새로운 배열1과 스택1을 사용할게요.

 5는 수이므로 배열1에 보관

남은 ( ) 내부 수식: + 4 * 2

남은 입력 수식: – 3 + 6

+를 만나면 스택1에 있는 모든 기호를 꺼내 배열1에 보관한 후에 자신을 스택1에 보관

남은 ( ) 내부 수식: 4 * 2

남은 입력 수식: – 3 + 6

4는 수이므로 배열1에 보관

남은 ( ) 내부 수식: * 2

남은 입력 수식: – 3 + 6

*는 스택1에 있는 것을 꺼내어 자신과 연산자 우선 순위를 비교합니다. 꺼낸 부호가 +이므로 꺼낸 부호를 스택1에 다시 보관한 후에 자신을 스택1에 보관합니다.

남은 ( ) 내부 수식: 2

남은 입력 수식: – 3 + 6

2는 수이므로 배열1에 보관합니다.

남은 ( )내부 수식: 없음

남은 입력 수식: – 3 + 6

 

  

( )내부 수식의 끝을 만났으므로 스택 1에 있는 것을 꺼내어 배열 1에 보관합니다.

남은 ( ) 내부 수식: 없음

남은 입력 수식: – 3 + 6

( ) 내부 수식을 후위 표기로 변환한 배열1에 있는 것들을 차례대로 배열에 보관합니다.

남은 입력 수식: – 3 + 6

- 를 만나면 스택에 있는 모든 기호를 꺼내 배열에 보관한 후에 자신을 스택에 보관합니다.

남은 입력 수식: 3 + 6

3은 수이므로 배열에 보관합니다.

남은 입력 수식: + 6

+ 를 만나면 스택에 있는 모든 기호를 꺼내 배열에 보관한 후에 자신을 스택에 보관합니다.

남은 입력 수식: 6

 

6은 수이므로 배열에 보관합니다.

남은 입력 수식: 없음

수식의 끝을 만났으므로 스택에 있는 것을 꺼내어 배열에 보관합니다.

따라서  2 + 3 * (5 + 4 * 2) – 3 + 6 를 후위 표기로 바꾸면 2 3 5 4 2 * + * + 3 – 6 + 가 됩니다. 그리고 계산하는 연산 순서는 * + * + - + 순서입니다. 4 2 * 를 제일 먼저 한 후에 연산 결과를 가지고 5 8 +을 수행합니다. 그리고 3 13 *를 수행하고 2 39 +, 41 3 -, 38 6 +를 수행하여 44입니다.

스택을 이용한 스택 계산기는"STEP BY STEP 1. 스택 계산기"를 참고하시기 바랍니다. ebook으로 판매(2000원)하고 있습니다. C언어로 스택 구현부터 컴파일러 개념을 적용하여 토큰 생성, 형태소 분석, 파싱 단계를 거치는 과정을 소개하고 구체적인 코드 구현을 소개하고 있습니다.