[Stack + Swith Expression] 150. Evaluate Reverse Polish Notation

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

Evaluate Reverse Polish Notation - LeetCode

https://github.com/fineman999/algorithm_java/issues/8

150. Evaluate Reverse Polish Notation · Issue #8 · fineman999/algorithm_java

---

1. 서론

이번 알고리즘 문제는 후위 표기법을 통해 식을 계산하는 문제다.

후기 표기법은 연산자를 연산 대상의 뒤에 쓰는 연산 표기법이다.

알고리즘을 풀기 위해 자바에서 제공해 주는 Stack과 Swith를 적용하였다.

2. 알고리즘 내용

후위 표기법으로 산술식을 나태는 문자열 토큰 배열이 제공된다.

올바른 연산자는 +, - , * 및 /이다.

각 피연산자는 정수이거나 다른 식일 수 있다.

두 숫자의 소수점은 버린다.

0으로 나눌 수 없다.

입력은 올바른 산술식을 후기표기법으로 나타낸다.

32비트 정수로 나타낸다.

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

3. 알고리즘 풀이

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

        for (String token : tokens) {
            calculate(token, stack);
        }
        return stack.pop();
    }

    private void calculate(String token, Stack<Integer> stack) {
        switch (token) {
            case "+" -> {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a + b);
            }
            case "-" -> {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b - a);
            }
            case "*" -> {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(a * b);
            }
            case "/" -> {
                int a = stack.pop();
                int b = stack.pop();
                stack.push(b / a);
            }
            default -> stack.push(Integer.parseInt(token));
        }
    }
}

4. 결과

단위 테스트

leetcode 결과

정상적으로 잘 동작한다.

추가적으로 자바에서 쓰이는 Stack과 Swith문에 대해 알아보자.

4. Stack<E>

Stack<E> 클래스는 자바에서 제공되는 클래스이다.

4.1 특징

제네릭 클래스

• 타입 안정성을 보장한다.

주요 메서드

• push(E item): 요소 추가
• isEmpty(): 빈 값 확인
• pop(): 맨 위 요소 제거 및 반환
• peek(): 맨위 요소 조회

5. Swith Expression

5.1 Swith Statement

public enum Day { SUNDAY, MONDAY, TUESDAY,
    WEDNESDAY, THURSDAY, FRIDAY, SATURDAY; }

// ...

    int numLetters = 0;
    Day day = Day.WEDNESDAY;
    switch (day) {
        case MONDAY:
        case FRIDAY:
        case SUNDAY:
            numLetters = 6;
            break;
        case TUESDAY:
            numLetters = 7;
            break;
        case THURSDAY:
        case SATURDAY:
            numLetters = 8;
            break;
        case WEDNESDAY:
            numLetters = 9;
            break;
        default:
            throw new IllegalStateException("Invalid day: " + day);
    }
    System.out.println(numLetters);

switch statement를 이용하여 요일의 글자수를 프린트하는 코드이다.

numLetters를 저장하는 대신 'return'할 수 있다면 더 좋을 것이다. Swith Expressions를 이용하여 더 좋은 코드를 만들 수 있다.

5.2 Swith Expression

    Day day = Day.WEDNESDAY;    
    System.out.println(
        switch (day) {
            case MONDAY, FRIDAY, SUNDAY -> 6;
            case TUESDAY                -> 7;
            case THURSDAY, SATURDAY     -> 8;
            case WEDNESDAY              -> 9;
            default -> throw new IllegalStateException("Invalid day: " + day);
        }
    );

Java 런타임이 화살표의 왼쪽에 있는 레이블과 일치하면 화살표의 오른쪽에 있는 코드를 실행하고 일치하지 않으면 Swith Expression의 다른 코드를 실행하게 된다. 화살표의 오른쪽에 있는 코드가 식을 실행하면 해당 식의 값이 Swith Expression의 값이 된다. 다만 예외를 제외한 모든 값이 반환이 유효할 때만 Swith Expression 값이 된다.

아니면 반환 값이 없게 하고 싶으면 아래와 같이 작성하면 된다.

 

    int numLetters = 0;
    Day day = Day.WEDNESDAY;
    switch (day) {
        case MONDAY, FRIDAY, SUNDAY -> numLetters = 6;
        case TUESDAY                -> numLetters = 7;
        case THURSDAY, SATURDAY     -> numLetters = 8;
        case WEDNESDAY              -> numLetters = 9;
        default -> throw new IllegalStateException("Invalid day: " + day);
    };
    System.out.println(numLetters);

Swith Expression의 장점

• Swith Statement에서 사용하는 break문을 삽입하는 것을 잊기 쉽다. 그렇게 하면 의도하지 않는 결과를 초래할 수 있게 된다. 반면 Swith Expression은 다음 case로 넘어가지 않기 때문에  break문이 없어도 된다.
• case를 판별하는 부분에 조건을 여러개 넣어도 가능하다.

 

참고

https://docs.oracle.com/en/java/javase/17/language/switch-expressions.html

Java Language Updates

https://ko.wikipedia.org/wiki/%EC%97%AD%ED%8F%B4%EB%9E%80%EB%93%9C_%ED%91%9C%EA%B8%B0%EB%B2%95

역폴란드 표기법 - 위키백과, 우리 모두의 백과사전