LeetCode 150 Evaluate Reverse Polish Notation

nayu1105·2023년 8월 29일

leetcode 알고리즘

LeetCode

목록 보기

17/28

LeetCode 150 Evaluate Reverse Polish Notation 풀러가기

문제

String 배열 tokens 가 주어진다.

tokens에 있는 배열은 역폴란드 기업으로 표현된 산술표현식이다.

역폴란드 기업으로 표현된 산술표현식이란

["2","1","+","3","*"]일 때 , ((2, 1, +) 3, *) 로 묶어지며 ((2 + 1) * 3)을 수행하면 된다.

이를 계산한 결과값을 리턴한다.

문제 분석

첫번째 시도

산수식 표현은 보통 스택을 활용해서 많이 풀어봐서 검증만 하고 바로 구현했다.

역폴란드 기업이니, 숫자 2개 연산자 1개 순서대로 들어오다는 걸 기억하면 된다.

숫자 일 경우 stack에 넣고, 연산자일 경우 에서 숫자 2개를 뽑고, 계산 후 다시 stack에 넣으면 된다.

위 과정을 표현식 끝까지 계속 하면 stack에는 정답 숫자만 남아있다. 이를 리턴하면 된다.

코드

import java.util.*;

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

        for(int i=0; i<tokens.length; i++){
            
            if(tokens[i].equals("+")||tokens[i].equals("-")
                ||tokens[i].equals("/")||tokens[i].equals("*")){
                int a = stack.pop();
                int b = stack.pop();
                switch(tokens[i]){
                case "+" : 
                    stack.push(b+a);
                    break;
                case "-" :
                    stack.push(b-a);
                    break;
                case "*" :
                    stack.push(b*a);
                    break;
                case "/" :
                    stack.push(b/a);
                    break;
                }
            }
            else stack.push(Integer.valueOf(tokens[i]));

        }

        return stack.pop();
    }
}