문제

https://leetcode.com/problems/evaluate-reverse-polish-notation/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 후위 표기식에 관한 문제
• 토큰이 ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]로 입력되었다면 정답은 ((10 (6 / ((9 + 3) -11))) + 17) + 5 = 22가 되어야 함
• 나중에 들어온 수가 먼저 계산되는 형태이므로 Stack을 사용해 입력된 숫자들을 순서대로 넣어주고 연산(+, -, *, /)이 나온다면 앞의 두 숫자를 연산해주고 뒤에 결과값을 삽입해 주면 해결 가능
• 위 방식대로 ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] 이 입력을 처리해보면 아래와 같음

1. Stack = {10, 6, 9, 3}까지 순서대로 추가되고 +가 입력되었음
2. 마지막 두 수 (9, 3)을 pop하고 더 해줌 => 12
3. 결과값 12를 Stack의 마지막에 삽입 => Stack = {10, 6, 12}
4. -11은 숫자이므로 Stack에 삽입 => Stack = {10, 6, 12, -11}
5. *가 입력되었으므로 뒤의 두 수를 추출하여 곱해주고 삽입 => Stack = {10, 6, -132}
6. /가 입력되었으므로 뒤의 두 수를 추출하여 나눠주고 삽입 => Stack = {10, 0}
7. *가 입력되었으므로 뒤의 두 수를 추출하여 곱해주고 삽입 => Stack = {0}
8. 17 입력 => Stack = {0, 17}
9. + 입력 => Stack = {17}
10. 5 입력 => Stack = {17, 5}
11. + 입력 => Stack = {22}
12. 22 return

코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            if (isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int afterNum = stack.pop();
                int beforeNum = stack.pop();

                if (token.equals("+")) {
                    stack.push(beforeNum + afterNum);
                } else if (token.equals("-")) {
                    stack.push(beforeNum - afterNum);
                } else if (token.equals("*")) {
                    stack.push(beforeNum * afterNum);
                } else {
                    stack.push(beforeNum / afterNum);
                }
            }
        }

        return stack.pop();
    }

    // str이 숫자인지 판단
    private static boolean isNumber(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return false;
        }
        return true;
    }
}

결과