[2주차] 150. Evaluate Reverse Polish Notation

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

Evaluate Reverse Polish Notation - LeetCode

---

📝 문제

후위 표현식으로 표현된 수학식의 각 토큰이 담긴 String 배열이 주어진다. 해당 식의 계산결과를 반환하시오.

 

 

🎈 풀이

Stack을 이용하여 풀었다. 후위표현식을 계산하는 전형적인 방식이다.

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (int i=0; i<tokens.length; i++) {
        String token = tokens[i];
        if (isNumber(token)) {
            stack.push(Integer.parseInt(token));

        } else {
            int temp = stack.pop();

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

    return stack.pop();
}

private boolean isNumber(String s) {
    try {
        Integer.parseInt(s);
    } catch (NumberFormatException e) {
        return false;
    }

    return true;
}

• tokens 을 순회하며, 값이 숫자면 스택에 담는다.
• 값이 숫자가 아니면, 스택에서 숫자 두 개를 꺼내 현재 꺼낸 연산자에 해당하는 연산을 하고, 결과를 스택에 넣는다.
• 마지막에 Stack 에 남은 수가 연산 결과이다

주의할 점은 피연산자의 순서에 따라 결과가 달라지는 '-', '/' 의 경우 주의해야 한다. 스택의 아랫쪽에 위치한 숫자가 먼저 들어간 숫자 이기 때문이다.