자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 후위식 연산 (postfix)

 

https://hyejin.tistory.com/1234

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 크레인 인형 뽑기 (카카오)

-> 이전 문제 풀이 

 

 

 

4. 후위식 연산 (postfix) 

설명

후위연산식이 주어지면 연산한 결과를 출력하는 프로그램을 작성하세요.

만약 3*(5+2)-9 을 후위연산식으로 표현하면 352+*9- 로 표현되며 그 결과는 12입니다.

 

입력

첫 줄에 후위연산식이 주어집니다. 연산식의 길이는 50을 넘지 않습니다.

식은 1~9의 숫자와 +, -, *, / 연산자로만 이루어진다.

 

출력

연산한 결과를 출력합니다.

 

예시 입력 1 

352+*9-

 

예시 출력 1

12

 

 

 

문제 풀이 1

public int solution(String str)
{
   int answer = 0;
   Stack<Integer> stack = new Stack<>();
   
   for (char c : str.toCharArray())
   {
      if (Character.isDigit(c)) {
         stack.push((int) c - 48);
      }else {
         int a = stack.pop();
         int b = stack.pop();
         switch (c) {
            case '+':
               answer = b + a ;
               break;
            case '-':
               answer = b - a ;
               break;
            case '*':
                answer = b * a;
               break;
            case '/':
               answer = b / a;
               break;
         }
         stack.push(answer);
         answer =0;
      }
   }
   
   return stack.get(0);
}

👩‍💻 : 이 문제는 숫자일 때는 stack에 넣어뒀다가 연산자를 만나면 stack에서 두개의 숫자를 꺼내서 연산하고, 그 결과를 다시 stack에 넣어두면 된다. 

 

그래서 우선 Character.isDigit() 메서드를 사용해서 문자가 숫자이면 stack.push하는데 이때, 문자 c 값을 그대로 넣으면 c가 '3' 일때 stack에 51 값이 stack에 담긴다. 그러므로 '0'의 값에 해당하는 48을 빼줘야 한다. 

 

그 다음 연산자이면 이제 stack에서 2개의 값을 꺼내서 a, b 변수에 담았다. 

그 다음 +, -, *, / 연산자에 해당하는 연산을 수행하면 되는데 이때, 후위 연산이기 때문에 b가 먼저 계산되어야 한다. 

그 다음 이 연산 결과를 stack에 push해주면 되고, answer 를 0으로 초기화해준다.  (사실 answer 초기화 이런 과정 없이 바로 stack에 넣으면 됐던 것임..!) 

 

그 다음 맨 마지막까지 stack에 남아있는 값이 최종 연산 결과이기 때문에 stack.get(0) 값을 꺼내서 리턴하면 된다.

 

 

 

문제 풀이 2

public int solution2(String str)
{
   Stack<Integer> stack = new Stack<>();
   
   for (char c : str.toCharArray())
   {
      if (Character.isDigit(c)) {
         stack.push(c - 48);
      }else
      {
         int rt = stack.pop();
         int lt = stack.pop();
         
         if (c == '+') {
            stack.push(lt + rt);
         }
         else if (c == '-') {
            stack.push(lt - rt);
         }
         else if (c == '*') {
            stack.push(lt * rt);
         }
         else if (c == '/') {
            stack.push(lt / rt);
         }
      }
   }
   
   return stack.get(0);
}

👾 : 강사님도 나랑 동일한 방식으로 풀었는데 lt, rt 로 변수 이름을 두어 좀 더 쉽게 구분할 수 있게 했다. 

그 다음, stack에 바로 연산 결과를 push 했고, 그 다음 stack.get(0) 을 리턴해줬다.