[LeetCode] 150. Evaluate Reverse Polish Notation - Java[자바]

링크

문제

역 폴란드어 표기법으로 산술식을 나타내는 문자열 토큰 배열이 주어집니다.

표현식을 평가합니다. 표현식의 값을 나타내는 정수를 반환합니다.

참고하세요:

• 유효한 연산자는 +, -, * 및 /입니다.
• 각 피연산자는 정수 또는 다른 표현식일 수 있습니다.
• 두 정수 사이의 나눗셈은 항상 0을 향해 잘립니다.
• 0으로 나눈 값은 존재하지 않습니다.
• 입력은 역연산 표기법으로 유효한 산술식을 나타냅니다.
• 답과 모든 중간 계산은 32비트 정수로 표현할 수 있습니다.

풀이

Stack을 이용한 풀이

import java.util.*;  
  
class Solution {  
    public int evalRPN(String[] tokens) {  
        Stack<Integer> stack = new Stack<>();  
        for (String token: tokens) {  
            switch (token) {  
                case "+" -> stack.push(stack.pop() + stack.pop());  
                case "-" -> {  
                    int a = stack.pop();  
                    int b = stack.pop();  
                    stack.push(b - a);  
                }  
                case "*" -> stack.push(stack.pop() * stack.pop());  
                case "/" -> {  
                    int a = stack.pop();  
                    int b = stack.pop();  
                    stack.push(b / a);  
                }  
                default -> stack.push(Integer.parseInt(token));  
            }  
        }  
        return stack.pop();  
    }  
}

배열을 이용한 풀이

class Solution {  
  
    public int evalRPN(String[] tokens) {  
        int[] stack = new int[tokens.length];  
        int top = -1;  
        for (String token: tokens) {  
            switch (token) {  
                case "+" -> stack[top - 1] += stack[top--];  
                case "-" -> stack[top - 1] -= stack[top--];  
                case "*" -> stack[top - 1] *= stack[top--];  
                case "/" -> stack[top - 1] /= stack[top--];  
                default -> stack[++top] = Integer.parseInt(token);  
            }  
        }  
        return stack[top];  
    }  
}

Stack이나 배열 모두 숫자면 저장하고, 연산자가 나온 경우에는 두개의 수를 뽑아서, 계산 후에 다시 넣는 동작을 반복하면 결국 계산 된 마지막 결과만 배열과 stack 남게 됩니다.

계산이 끝난 결과값을 return 하기만 하면 끝