Stack<T> 와 Polish 계산기

큐와 반대로 스택은 나중에 저장된 자료가 먼저 처리될 때 사용하는 자료구조이다. 나중에 들어온 자료가 먼저 처리되므로 후입선출(LIFO, "Last-In First-Out") 이라고도 한다. 스택은 입력과 출력이 한 방향에서만 이루어진다. 스택에 자료를 넣는 것을 Push, 꺼내는 것을 Pop이라고 한다. 큐와 마찬가지로 .NET 컬렉션은 Stack과 Stack<T>를 제공한다. 제네릭과 제네릭 아닌 것의 차이니 제네릭 쓰는 게 더 나을 것 같다.

 

Polish표기법을 사용하는 4칙 연산 계산기

Polish 표기법은 피연산자 뒤에 연산자를 쓰게 된다.   1+2  => 1 2 + 로 표기한다.

이렇게 되면 수식에 괄호가 없어도 우선순위를 처리할 수 있게 된다.

예를들어 (10-20)*3 => 10 20 - 3 * 가 된다.

 

Polish 표기법으로 표현된 수식을 계산할 때 Stack을 사용한다. 숫자가 나오면 Stack에 넣고 연산자가 나오면 Stack에서 두개의 값을 꺼내어 계산하고 결과를 Stack에 넣는다. 계산이 끝나면 Stack의 맨 밑에 결과값이 저장되어 있다.

 

 

계산과정

10 20이 스택에 들어가고 -를 만나니 20이 튀어나오고 10이 튀어나온다. 계산은 10 - 20 먼저튀어나온 것 앞에 연산기호가 붙는다. 

계산할 숫자인 3이 스택에 들어가고 3 * (-10) 이므로 스택에 -30 저장

 

static void Main(string[] args)
        {
            Console.WriteLine("계산할 수식을 Polish 표기법으로 입력하세요");
            string[] token = Console.ReadLine().Split(' ');//split은 문자열을 자르기

            foreach (var item in token)
            {
                Console.Write(" {0}", item);
            }
            Console.Write("=");

            Stack<double> nStack = new Stack<double>();
            foreach (var s in token)
            {
                if(isOperator(s))
                {
                    switch(s)
                    {
                        case "+":
                            nStack.Push(nStack.Pop() + nStack.Pop());
                            break;
                        case "-":
                            nStack.Push(-(nStack.Pop() - nStack.Pop()));
                            break;
                        case "*":
                            nStack.Push(nStack.Pop() * nStack.Pop());
                            break;
                        case "/":
                            nStack.Push(1.0/(nStack.Pop() / nStack.Pop()));
                            break;
                    }
                }
                else
                {
                    nStack.Push(double.Parse(s));
                }
               
            }
            Console.WriteLine(nStack.Pop());

        }
        private static bool isOperator(string s)
        {
            if (s == "+" || s == "-" || s == "*" || s == "/")
                return true;
            else
                return false;
        }

먼저 bool 을 반환하는 isOperator은 문자에서 연산기호 즉 +,-,*,/  들이 매개변수로 온다면 참을 반환하고 그 외의 경우엔 거짓을 반환한다. 

 

계산할 수식을 Polish 표기법으로 입력하게 되면 Split을 통해서 공백을 기준으로 문자열을 자른다.

다음 foreach문을 통해서 token의 item인 s가 연산기호라면 스택에서 Pop두개를 해서 해당 연산을 case문을 통해서 연산하고, 그외의 경우는 숫자이기 때문에 double형으로 바꿔서 스택에 밀어넣는다. 최종적으로 스택에 남은 한 숫자가 결과이다.