[스택] 4. 후위식 계산

4. 후위식 연산(postfix)

 

설명

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

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

입력

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

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

출력

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

예시 입력 1 

352+*9-

예시 출력 1

12

 

<<풀이>>

 

import java.util.Scanner;
import java.util.Stack;

class Main {
    private int solution(String str) {
        Stack<Integer> stack = new Stack<>();
        for (char x : str.toCharArray()) {
            if (Character.isDigit(x)) stack.push(x - 48);
            else {
                int rt = stack.pop();
                int lt = stack.pop();
                if (x == '+') stack.push(lt + rt);
                else if (x == '-') stack.push(lt - rt);
                else if (x == '*') stack.push(lt * rt);
                else if (x == '/') stack.push(lt / rt);
            }

        }
        return stack.get(0);
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String str = in.next();
        System.out.println(T.solution(str));
    }
}

 

이 문제는 후위식 연산이라고 해서 원래 중위식 연산이 디폴트이면 후위식은 연산기호를 계산하는 숫자의 마지막에 둔다.

 

풀이방식

우선, toCharArray를 활용해서 숫자이면 stack에 담아준다. 그러다가 연산자를만나게 되면 push를 통해 먼저 나오는 값은 오른쪽에 있다고 해서 rt에 넣어주고 그 다음 값은 lt에 넣어준다. 그렇게 해서 if 문으로 그 연산자의 조건에 맞게 구하고 다시 stack에 넣어준다.

 

이런식으로 반복해서 문제를 푸는 문제이다. !! 

 

여기서 pop을 두 번 해버리면 안 되지 않나!? stack 에 값이 없으면 어떻게 ?? 라고 생각할 수도 있지만 사실상 연산하기 위해서는 무조건 두 개의 피연산자가 들어가기 마련이다. 그렇게 생각하면 넣어준 문자열이 중위식을 후위식으로 만들었기에, 이러한 풀이는 문제가 없다는 것이다.

 

처음 보는 형태였고 이러한 방식이 나오면 이 논리의 흐름을 까먹지 말고 사용하자!!

 

<<추가 공부>>

 

'0' '1' 같은 char는 아스키코드로 했을 때 '0'->48 이고 '1' -> 49 이다. 따라서 이를 진짜 숫자로 바꾸기 위해서는 -48 을 하면 된다!