Chapter 06. 계산기 프로그램 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

이제는 지금까지 공부한, 그리고 구현한 스택을 활용할 차례입니다. 자료구조에서 스택의 활용과 관련해서 빠지지 않고 등장하는 사례가 계산기 프로그램입니다. 우리가 구현할 계산기 프로그램은 아래에서 보이는 수준의 수식을 계산할 수 있어야 합니다.

 

( 3 + 4 ) * ( 5 / 2 ) + ( 7 + ( 9 - 5 ) ) 

 

프로그램 사용자가 위 수준의 문장을 입력하면 프로그램은 연산자의 우선순위와 괄호의 위치를 인식하여 연산의 결과를 프로그램 사용자에게 보여야 합니다. 즉, 우리가 구현할 계산기는 다음 두 가지를 고려해서 연산을 진행할 수 있어야 합니다.

• 소괄호를 파악하여 그 부분을 먼저 연산한다.
• 연산자의 우선순위를 근거로 연산의 순위를 결정한다.

물론 스택을 활용할 줄 안다고 해서 계산기가 저절로 구현되는 것은 아닙니다. 계산기를 구현하기 위해서는 별도의 알고리즘을 이해해야 합니다. 따라서 지금부터 계산기의 구현에 필요한 별도의 알고리즘을 소개하고자 합니다.

---

우선 앞으로 구현하게 될 계산기의 기능을 다음과 같이 제한하고자 합니다.

• 수식을 이루는 피연산자는 한 자리 숫자로만 이뤄진다.

즉, 1, 7과 같은 한 자리 숫자만 계산할 수 있는 계산기를 구현하겠다는 의미입니다. 이렇게 제한을 둔 이유는 당장 중요하지 않은 부분에 신경을 덜 쓰기 위함입니다. 계산기를 구현하면서 배우게 될 개념이 훨씬 중요하기 때문입니다. 

 

계산기 구현에 필요한 알고리즘 소개의 첫 번째 단계로 수식의 표기법을 소개하고자 합니다. 수식을 표기하는 방법에는 다음과 같이 세 가지 종류가 있습니다.

• 중위 표기법    예) 5 + 2 / 7
• 전위 표기법    예) + 5 / 2 7
• 후위 표기법    예) 5 2 7 / +

 위 세 가지 표기법 중에 우리에게 익숙한 표기법은 중위 표기법입니다. 하지만 중위 표기법은 연산의 순서를 알려주지 않습니다. 즉, 위의 예와 같이 중위 표기법으로 표기된 5 + 2 / 7 만 봐서는 어떤 연산을 먼저 수행해야 하는지 그 순서를 알 수가 없다는 의미입니다.

 

그럼 여기서 의문이 생길 것입니다. 우리들이 보기에는 당연히 다음과 같은 연산 순서를 따를 것이라는 것을 알 수 있습니다.

 

"2를 7로 먼저 나누고, 이 값을 5에 더한다."

 

그런데 이런 중위 표기법이 연산의 순서를 알려주지 않는다니? 조금 이상합니다. 사실 우리가 5 + 2 / 7과 같은 수식을 보고 연산 순서를 알 수 있는 이유는 연산 순서를 우리가 따로 약속을 해놨고, 이것을 이미 알고 있기 때문입니다.

 

덧셈과 뺄셈보다는 곱셈과 나눗셈이 먼저 수행되어야 하고, 괄호가 있으면 괄호 안의 수식을 먼저 연산해야 하는 등의 규칙을 우리들은 알고 있습니다. 하지만 다들 이런 규칙을 몰랐을 때는 다음과 같이 계산한 경험이 있을 것입니다.

 

"5에 2를 더하고 이 값을 7로 나눈다." 

 

이제 중위 표기법은 연산의 순서를 알려주지 않는다는 말의 의미를 조금은 이해했을 것입니다. 그렇다면 전위 표기법과 후위 표기법은 연산의 순서를 어떻게 알려준다는 것일까요? 전위 표기법은 다음과 같은 표기 순서를 가집니다.

 

'연산자' '숫자 1' '숫자 2'

 

이것을 차례로 읽으면 다음과 같이 해석할 수 있습니다.

 

" '연산자'한다. '숫자 1'과 '숫자 2'를 "

 

후위 표기법은 다음과 같은 표기 순서를 가지며, 다음과 같이 해석할 수 있습니다.

 

'숫자 1' '숫자 2' '연산자'

" '숫자 1'과 '숫자 2'를 '연산자'한다. "

 

위와 같은 방식으로 전위 표기법과 후위 표기법은 연산의 순서를 알려줍니다. 이해를 돕기 위해 수식을 하나 예로 들겠습니다. 

 ( 1 + 2 ) * 7 - 1 + 6 / 2

위 식을 전위 표기법으로 적어보겠습니다.

 + - * + 1 2 7 1 / 6 2

그럼 위와 같은 수식이 됩니다.  이를 해석하면

 

" 더한다 ( 뺀다 [ 곱한다 { 더한다 ( 1 )과 ( 2 )를 }과 { 7 }를 ]에서 [ 1 ]을 )와 ( 나눈다 [ 6 ]과 [ 2 ]를 )를 " 

 

음... 이해하기 쉬우라고 해봤는데 더 어려워진 것 같습니다. 아무튼 핵심은 차례대로 읽었을 뿐인데 연산 순서에 맞게 연산이 된다는 것입니다. 이렇듯 전위 표기법이나 후위 표기법으로 작성된 수식에는 배치 순서를 근거로 한 연산 순서의 정보가 담기기 때문에, 이를 대상으로 한 연산에서는 연산자의 우선순위가 필요하지 않습니다. 다시 말해서 연산자의 우선순위란 중위 표기법만을 위한 것입니다.

 

뿐만 아니라 연산자의 배치 순서를 바꿈으로써 연산의 순서를 바꿀 수 있기 때문에, 소괄호를 필요로 하지도 않습니다. 즉, 소괄호도 중위 표기법만을 위한 것입니다. 이러한 장점들 덕분에 전위 표기법의 수식이나 후위 표기법의 수식을 대상으로 한 계산기를 구현하는 것이, 중위 표기법의 수식을 대상으로 하는 것보다 훨씬 수월합니다.

 

그렇다고 계산기에 수식을 전위 표기법이나 후위 표기법으로 입력해야 할 필요는 없습니다. 계산기 사용자는 수식을 중위 표기법으로 입력합니다. 그리고 우리가 그 수식을 전위 표기법 또는 후위 표기법의 수식으로 변환하여 계산이 진행되도록 합니다. 따라서 계산기의 구현에 앞서, 중위 표기법의 수식을 전위 표기법의 수식으로 변환할 줄 알아야 합니다. 참고로 프로그램 상에서 우리가 작성하는 연산문도 컴파일러에 의해서 후위 표기법으로 바뀌어 처리가 됩니다.

---

따라서 우리가 구현할 계산기는 다음의 과정을 거쳐서 연산을 진행하도록 할 계획입니다.

• 중위 표기법의 수식을 후위 표기법의 수식으로 바꾼다.
• 후위 표기법으로 바뀐 수식을 계산하여 그 결과를 얻는다.

 

먼저, 중위 표기법의 수식을 후위 표기법의 수식으로 바꾸는 방법에 대해서 생각해 보겠습니다. 다음의 수식을 예로 들어서 후위 표기법으로 변환하는 방법을 설명하겠습니다.

5 + 2 / 7 

프로그램이 위 수식을 피연산자, 연산자 단위로 구분하면서 맨 앞부터 하나씩 읽는다고 생각해 보겠습니다. 단, 스택을 활용하면서, 필요할 때는 읽어 들인 연산자 혹은 피연산자를 스택에 저장할 수 있고, 그렇지 않을 때는 읽어 들인 연산자 혹은 피연산자를 후위 표기법으로 표기할 자리에 배치한다고 생각해 보겠습니다. 말로 하니 어렵습니다. 최대한 이해하기 쉽게 설명해 보겠습니다.

기존 수식 블록화
5	+	2	/	7

위 배열은 위 수식을 연산자와 피연산자 단위로 하나씩 블록으로 배열한 것입니다. 그리고 다음의 빈칸은 후위 표기법으로 변환된 수식이 위치하게 될 자리입니다.

변환된 수식의 자리

그리고 두 블록 사이에는 다음과 같은 구조의 스택이 있습니다.

처음 기존 수식에서 '5'를 읽어 들입니다. 읽어 들인 것이 피연산자라면 그대로 '변환된 수식의 자리로 배치합니다. 따라서 기존 수식과 스택과 변환된 수식은 다음과 같은 형태가 됩니다.

기존 수식 블록화
	+	2	/	7

변환된 수식의 자리
5

이어서 '+'를 읽습니다. 이때 읽은 것이 연산자라면 이를 일단은 스택에 저장합니다. 그럼 다음과 같이 됩니다.

기존 수식 블록화
		2	/	7

+

변환된 수식의 자리
5

이어서 '2'를 읽으면 피연산자이므로, 곧바로 변환된 수식의 자리에 배치됩니다. 이후 '/'를 읽을 때는 연산자이므로 스택에 우선 저장해야 하는데 스택에 이미 '+'가 저장되어 있으므로 이때는 추가적인 로직을 검토해야 합니다.

 

피연산자를 스택에 저장하려는데 다른 피연산자가 스택에 이미 있다면 두 연산자 간의 우선순위를 비교합니다. 그렇게 해서 이미 스택에 있는 연산자보다 새로 추가하려는 연산자의 우선순위가 더 높다면 그 위에 새로 추가한 연산자를 쌓습니다. 만약 새로 추가하려는 연산자의 우선순위가 이미 스택에 있는 연산자의 우선순위와 같거나 낮다면 스택에 이미 있는 연산자를 변환된 수식의 자리에 배치하고 스택에 추가합니다.

 

따라서 '/'를 스택에 저장하려는데 '+'가 스택에 있으므로 '/'와 '+'의 우선순위를 비교합니다. '/'의 우선순위가 더 높기 때문에 '+'위에 '/'를 쌓습니다. 그럼 다음과 같은 형태가 됩니다.

기존 수식 블록화
				7

/

+

변환된 수식의 자리
5	2

이어서 마지막 남은 7을 변환된 수식의 자리로 배치합니다. 그리고 더 이상 읽을 데이터가 없다면 스택에 저장된 모든 데이터를 하나씩 변환된 수식의 자리에 배치합니다. 그럼 다음과 같이 변환이 완성됩니다.

기존 수식 블록화

변환된 수식의 자리
5	2	7	/	+

똑같이 중위 표기법을 후위 표기법으로 변환하는 다른 예를 하나 더 들어보겠습니다. 다음 수식을 보고 직접 그림을 그려가며 변환시켜보는 것도 좋습니다.

5 + 2 / 7 - 2 

변환을 시도했을 때 다음의 과정까지 오는 것은 쉬울 것입니다.

기존 수식
					-	2

/

+

변환된 수식
5	2	7

여기서부터는 '-'를 스택에 저장해야 하는데 스택에 이미 저장되어 있는 연산자들이 있으므로 우선순위를 비교해야 합니다. '-'보다는 '/'가 우선순위가 더 높기 때문에 '/'를 변환된 수식으로 옮깁니다. 따라서 다음과 같이 됩니다.

기존 수식
					-	2

+

변환된 수식
5	2	7	/

그럼 '/'도 옮겼으니 이제 '-'를 스택에 저장하면 될까요? 아닙니다. '-'를 스택에 저장하려고 보니 이번엔 '+'라는 녀석이 있습니다. 그래서 이 녀석과도 우선순위를 비교해야 합니다. 두 연산자의 우선순위는 같습니다. '-'의 우선순위가 더 높아야만 위에 쌓을 수 있으므로 이렇게 우선순위가 같은 경우에는 '+'를 변환된 수식으로 옮깁니다. 그렇게 하면 스택이 이제 비게 되고, '-'를 스택에 저장할 수 있게 됩니다. 변환을 다 마치면 다음과 같은 형태가 됩니다.

기존 수식

변환된 수식
5	2	7	/	+	2	-

---

책에서 가르쳐주는 것은 위 내용까지입니다. 그런데 저는 전위 표기법으로의 변환도 하고 싶습니다. 예를 들어 다음과 같은 수식이 있을 때,

5 + 2 / 7 - 2

이를 전위 표기법으로 변환할 알고리즘을 생각해보고자 합니다. 왜냐하면 제가 생각하기에 후위 표기법보다 전위 표기법을 계산에 사용하는 것이 프로그램을 구성할 때 더 간단할 것 같다는 생각이 들었기 때문입니다. 그래서 중위 표기법을 전위 표기법으로 변환하는 알고리즘을 다음과 같이 생각했습니다. 오랜 시간 반복 시도 끝내 찾아냈습니다.

• 주어진 수식의 꼬리부터 값을 읽어 들인다.
• 읽어 들인 데이터가 피연산자면 그대로 변환된 수식에 배치한다.
• 읽어 들인 데이터가 연산자면 스택에 저장한다.
• 연산자 A를 스택에 저장할 때 연산자 B가 이미 있으면 우선순위를 비교한다.
• 우선순위를 비교하여 연산자 A의 우선순위가 낮으면 연산자 B를 변환된 수식에 배치한다.
• 우선순위를 비교하여 연산자 A의 우선순위가 연산자 B와 같거나 높으면 스택에 저장한다.
• 연산자 B 배치 후 스택에 연산자 C가 남아 있으면 동일하게 우선순위를 비교하고 처리한다.
• 배치가 완료되면 변환된 수식을 거꾸로 다시 재배치한다.

인터넷에 검색하면 중위 표기법을 전위 표기법으로 변환하는 알고리즘이 나올지도 모릅니다. 하지만 위에 나열한 알고리즘은 제가 직접 생각해낸 알고리즘입니다. 따라서 실제 사용되는 알고리즘과 다를 수 있고, 오류가 발생할 수도 있습니다.

 

위 알고리즘을 바탕으로 다음의 수식을 전위 표기법으로 변환해 보겠습니다.

5 + 2 / 7 - 2

기존 수식
5	+	2	/	7	-

변환된 수식
2

꼬리부터 읽습니다. '2'는 피연산자입니다. 따라서 그대로 배치합니다.

기존 수식
5	+	2	/	7

-

변환된 수식
2

'-'는 연산자입니다. 따라서 스택에 저장합니다.

기존 수식
5	+

/

-

변환된 수식
2	7	2

조금 몇 과정을 거쳤습니다. 우선 '7'은 그대로 배치합니다. 그리고 '/'는 연산자이므로 스택에 저장해야 합니다. 그런데 스택에는 '-'연산자가 저장되어 있습니다. '-'연산자와 '/'연산자의 우선순위를 비교하면 '/'연산자가 더 높습니다. 따라서 스택에 저장합니다. 그리고 '2'는 피연산자이므로 그대로 배치합니다.

기존 수식
5

+

-

변환된 수식
2	7	2	/

다음 '+'연산자를 스택에 저장해야 하는데 스택에 있는 '/'연산자와 우선순위를 비교하면 '+'연산자의 우선순위가 낮습니다. 따라서 '/'를 스택에서 꺼내와 변환된 수식에 배치합니다. 그리고 '+'연산자와 '-'연산자의 우선순위는 같으므로 '+'연산자를 스택에 저장합니다.

기존 수식

변환된 수식
2	7	2	/	5	+	-

이후 '5'를 배치하고 스택에 남은 연산자들을 모두 꺼내와서 배치합니다. 여기서 끝이 아닙니다. 변환된 수식을 거꾸로 재배치해주어야 합니다.

변환된 수식
-	+	5	/	2	7	2

이로써 중위 표기법을 전위 표기법으로 변환하는 것이 끝이 났습니다.