스택계산기 구현 : 연산자 우선순위와 결합 순서만 생각해 봅시다.

 안녕하세요. 오늘은 간단하게 스택 계산기 프로그램을 만드려고 합니다.

 

 

---

 일단 괄호가 없는 유효한 식은 숫자 (연산자 숫자)* 이런 패턴으로 들어올 겁니다. 예를 들어 3도 유효한 계산 식입니다. 그리고, 3*7-2도 유효한 식입니다. 연산자는 *과 +, -만 들어온다고 가정해 보겠습니다. 먼저 우선순위부터 set 하도록 하겠습니다.

 

 *는 +, -보다 우선순위가 높으니, *의 priority를 0으로, +과 -를 1로 설정하였습니다.

 

 11번째 줄이 그러한 일을 수행합니다. 그리고, ArrayList인 num과 op는, 수식으로부터 들어온 수와 연산자를 순서대로 넣어놓았습니다. 예를 들어서 2-3+7이 들어왔다면, num에는 2, 3, 7 순서대로 들어가고, op에는 -와 +이 순서대로 들어가 있습니다. 이제 이것을 바탕으로 어떻게 해야하는지 간단하게 브리핑 해 보도록 하겠습니다.

 

 먼저, num에 수가 하나만 들어 있는 경우에는 볼 것도 없습니다. 그냥, 들어있는 수 하나만 돌려주면 됩니다. 예를 들어 20이라는 수식이 들어온 경우, 그냥 20을 돌려주면 됩니다. 그렇지 않으면 어떻게 하면 좋을까요?

 

 수 2개와 연산자 하나를 stack에다 넣으면 됩니다. 이 처리를 하는 코드가 20번째 줄에서 23번째 줄에 있습니다.

 

 

 이 부분까지는 그리 어렵지 않군요. 그 다음에 문제입니다.

 

---

 2+3*7이 있었습니다. 2, +, 3이 들어간 상태에서 *가 들어왔습니다. 이 경우에 무조건 2와 3을 먼저 더해야 할까요? 그것은 아닙니다. 왜냐하면, +가 *보다 우선 순위가 낮기 때문입니다.

 

 

 그림에서군청색 부분을 보면, 2, +, 3이 지금 stack에 있는 상황이고 *이 들어오려는 상황입니다. 이를 다시 그림으로 표현해 보면 아래와 같습니다.

 

 

 즉, op를 저장하고 있는 stack의 top이 +인 상태인데요. 여기서 *이 들어오려는 상황입니다. +보다는 *이 더 priority가 높기 때문에, +에 걸려있는 것이 먼저 계산이 되면 안 되는 상황입니다. 그렇기 때문에 *과 7이 들어옵니다.

 

 

 정리하면, op의 stack의 top에 있는 것보다 현재 넣으려는 연산자의 우선 순위가 높으면 그냥 넣어버리면 됩니다. 그렇지 않으면 어떻게 해야 할까요? 2-3+7이 있을 때, 우리는 3+7부터 계산하지 않습니다. 2-3부터 계산을 합니다. -과 +는 같은 우선순위인데, 왼쪽부터 계산하고 있어요. 이를 좌측 결합이라고 합니다. 프로그래밍 언어론 시간에 배우실지도 모르겠습니다.

 

 아래 상황을 생각해 보겠습니다.

 

 7-2*3+5를 계산한다고 해 보겠습니다. 7-2*3에 대한 것이 스택에 올라갔다고 한다면, 아래 그림과 같을 겁니다.

 

 

 이 상황에서 +5가 들어왔다고 해 보겠습니다. 즉, +라는 연산자가 들어왔다고 해 보겠습니다. 이것은 stack의 꼭대기에 있는 *보다 우선 순위가 낮습니다. 그렇기 때문에, + 연산을 하기 전에, 적절하게 연산이 되어야 합니다. 그러면 먼저, *에 걸린 2와 3이 먼저 연산이 될 겁니다.

 

 즉, num 스택에 있는 2와 3, 그리고 op에 있는 *이 빠질 겁니다. 그리고 2*3을 연산한 결과는 6이기 때문에, 이 결과는 num에 다시 push가 됩니다.

 

 

 즉, 우리는 7-2*3+...를 7-6+... 으로 바꾼 셈입니다. 여기서 질문 하나 드리겠습니다. 7-6+5를 계산하기 위해서 우리는 +를 먼저 계산해야 할까요? 아니면 -를 먼저 계산해야 할까요? 좌측 결합이기 때문에, -를 먼저 계산해야 합니다. 즉 +과 5를 넣기 전에, 먼저 - 연산을 먼저 해야 한다는 것입니다.

 

 그러면, +과 우선순위가 같은 -도 빠질 겁니다. 이제, num stack에는 1만, op에는 아무것도 남아있지 않습니다.

 

 즉, 우선 순위가 더 낮은 operation을 만나거나, op가 빌 때 까지 계속 연산자를 소모하면서 계산을 하는 작업을 반복하면 됩니다. 이에 대한 코드는 아래와 같습니다.

 

 28번째 줄에서, stack의 top에 있는 연산자의 우선순위가 현재 넣을 연산자의 우선순위보다 높거나 같으면 계속 calc을 하면서 연산자를 하나씩 소모합니다. 저는 prio값이 낮으면, 우선 순위가 높다고 정의했습니다. 그렇기 때문에 28번째 줄 while loop의 조건이 스택에 있는 것이 현재 넣을 것의 prio보다 작거나 같으면. 이라고 되어 있습니다.

 

 그리고 수식을 다 돌고 나서 opStack이 비어 있지 않으면, 그에 대한 처리를 37번째 줄에서 하고 있음을 알 수 있습니다. 최종적으로, numStack의 0번째 원소를 리턴한다고 생각하시면 되는데요. 그냥, 연산자 스택이 비었을 때, numStack의 top에 들어 있는 값을 돌려준다고 생각하시면 되겠습니다. 그런데, 중간 중간에 있는 calc이 무엇일까요?

 

 

 calc 메서드를 보면, 어렵지 않게, 피연산자 2개와 연산자 하나를 가지고 calc 한 결과를 다시 numStack에 넣는다는 것을 직관적으로 알 수 있습니다. 그러면 '(' 처리는 어떻게 하면 좋을까요? 여기에는 나오지 않았습니다만, '('은 다른 어떠한 것보다 연산자가 높다고 생각하면 됩니다. 즉, '('를 만나면 무조건 넣습니다. 그리고, 이 때 stack의 empty 조건을 최근에 '('을 넣은 위치로 바꾸면 됩니다. 다시 말해서, '('을 만났다면, empty라고 판단을 하는 겁니다. 만약에 ')'를 만났다면 '('를 만날 때 까지 모조리 pop을 해 버리면 됩니다. 이건 조금만 더 생각해 보시면 쉽게 구현하실 수 있을 겁니다. 그러니, 여기에서느 따로 언급해 드리지는 않겠습니다.