스택 계산기

infix에서 postfix방식으로 전환하는 스택 계산기의 예제

infix란 일반 표기번을 의미한다. 1+((a+2)*5)/7)

postfix란 후위 표기법으로 1a2 + 5 * 7 /+로 나타 내어 진다.

 

논리 순서로 보자면, 

괄호안의 연산이 밖으로 빠져 나가는 것이다.

1+((a2)+*5)/7) -> 1+((a2)+5)*/7) -> 1+((a2)+5)*7)/ -> 1((a2)+5)*7)/+ 

-> 마지막으로 괄호를 없앴을 때, 1a2 + 5 * 7 /+로 나타나 진다.

이후, 연산자가 나왔을때, 스택에서 피연산자 두개를 꺼내서 계산후 다시 집어 넣으면 

+ : a+2

* : (a+2) *5

/ : (a+2) * 5 / 7

+ : (a+2) * 5/ 7 + 1로 잘 나타난다.

 

이를 코드로 나타내어 본다면, 다음과 같다.

List<string> postFixList : 후위연산자 리스트로서 계산할때 사용할 토큰들을 가지고 있는 최종리스트

private Queue<string> tokenQueue : 입력한 계산을 연산자 기준으로 나눈 토큰들을 가지고 있는 큐

 private Stack<string> stack = new Stack<string>() : 마지막으로, 연산들을 가지고 있는 스택

세가지를 중심으로 계산을 해볼것이다.

먼저, 데이터를 받아 와서 연산자에 따라 토큰화 시킨다.

이로써, 큐에 입력한 데이터가 토큰화가 되었다.

이후, 큐에서 다음 토크을 꺼내고, 현재 토큰이 end가 아니고, 연산자가 아니라면, postfixList에 넣어 준다.

만약, 연산자라면 마지막에 봤던 연산자와 현재 연산자의 우선 순위를 비교해준다. 이를 위해, 따로 연산자를 모아두는 리스트가 필요한데, 이것이 위에서 선언했던 stack 이다. 현재 토큰을 바로 스택에 넣는게 아니라 마지막으로 쌓여있던 스택에서의 토큰과 현재 토큰의 우선 순위를 비교하여, 스택에 넣는것이다. 만약 현재 토큰이 스택에서 peek(꺼내지않고 정보만 가져오는 것)한 토큰 보다 우선순위가 높다면, 현재 토큰을 스택에 넣고(이전이 +이고 현재가 *라면 순서가 + *가 되는 것이다 => 1 +2 * 3이라면 123*+) , 현재가 이전보다 낮다면 괄호가 아닐 경우 최종 postfixList에 넣어준다( => 1*2+3 이라면 12* 3+).

다음 토큰을 꺼내는 함수

이렇게 처리를 한후, stack에 남아 있는 연산자들은 순서대로 pop해준다.

이후, postfix의 결과는 aggregate(짧고 간결하게 하나의 string 으로 나타낼수 있다)로 나타내고 계산후 결과값을 리턴해주는데, 계산에대한 것은 다음 이미지를 참고

위에서 언급했던 연산자가 나왔을때 피연산자두개를 스택에서 꺼내와 연산하고 다시 넣는 과정

 

우선순위 비교, 우선순위 선정에 대해선 더 자세한 공부가 필요한듯 하다.