LeetCode 150. Evaluate Reverse Polish Notation

📊 결과

소요시간: 18분
Runtime: 5ms (Beats 72.45%)
Memory: 44.84MB

💻 내 코드

class Solution {
    public boolean isOperator(String s){
        if( s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) return true;
        return false;
    }

    public String calculator(String num1, String num2, String s){
        int a = Integer.parseInt(num1);
        int b = Integer.parseInt(num2);
        int c = 0;
        switch(s){
            case "+" :
                c = a+b;
                break;
            case "-" :
                c =a-b;
                break;
            case "*" :
                c = a*b;
                break;
            case "/" :
                c = a/b;
                break;
        }
        return Integer.toString(c);
        
    }

    public int evalRPN(String[] tokens) {
        Deque<String> stack = new ArrayDeque<String>();

        for(String s : tokens){
            if(isOperator(s)){
                String num2 = stack.pop();
                String num1 = stack.pop();
                stack.push(calculator(num1, num2, s));
            }else{
                stack.push(s);
            }
        }

        return Integer.parseInt(stack.pop());
    }
}

📝 평가

✔ 잘한 점

후위 표기법 이해: 스택을 활용한 전형적인 패턴 정확히 파악
함수 분리: isOperator, calculator로 역할 분리하여 가독성 향상
순서 주의: num2, num1 순서로 pop하여 올바른 연산 순서 유지 (빼기/나누기에서 중요!)
Switch 문 활용: 연산자별 분기 처리가 깔끔함
정확한 구현: 모든 테스트 케이스 통과

✦ 개선점

불필요한 타입 변환: String ↔ Integer 변환이 과도함
- 스택에 String 대신 Integer 저장 가능
메모리 낭비: 매번 Integer.toString(), Integer.parseInt() 호출
isOperator 로직: 간단한 Switch로 대체 가능
변수 c: 의미 없는 변수명, 바로 return 가능
성능: 문자열 연산보다 정수 연산이 더 빠름

✨ 최적화된 풀이

방법 1: Integer 스택 사용 (추천 ⭐⭐⭐⭐⭐)

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

개선 포인트:

✔ String → Integer 스택으로 변환 오버헤드 제거
✔ 함수 호출 최소화
✔ Switch의 default로 숫자 처리
✔ 덧셈/곱셈은 순서 무관하므로 간결하게 처리

방법 2: 함수형 접근 (가독성 중시)

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            if (isOperator(token)) {
                int num2 = stack.pop();
                int num1 = stack.pop();
                stack.push(calculate(num1, num2, token));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
    
    private boolean isOperator(String s) {
        return s.length() == 1 && "+-*/".contains(s);
    }
    
    private int calculate(int a, int b, String operator) {
        switch (operator) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;
            default: throw new IllegalArgumentException("Invalid operator");
        }
    }
}

방법 3: 배열 기반 스택 (메모리 최적화)

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

💡 배열 크기: 후위 표기법에서 최대 스택 크기는 n/2 + 1 (최악의 경우: 모든 숫자 후 연산자들)

📊 성능 비교

방법	시간복잡도	공간복잡도	Runtime	Memory	가독성	추천도
원본 코드	O(n)	O(n)	5ms	44.84MB	⭐⭐⭐⭐	⭐⭐⭐
Integer 스택	O(n)	O(n)	3-4ms	43.5MB	⭐⭐⭐⭐⭐	⭐⭐⭐⭐⭐
함수형 접근	O(n)	O(n)	3-4ms	43.5MB	⭐⭐⭐⭐⭐	⭐⭐⭐⭐
배열 스택	O(n)	O(n)	2-3ms	43MB	⭐⭐⭐	⭐⭐⭐⭐

💡 핵심 인사이트

배운 점

후위 표기법(RPN)의 원리

 중위: (2 + 3) * 4
 후위: 2 3 + 4 *
    
 처리 과정:
 - 숫자 만나면 → push
 - 연산자 만나면 → pop 2개, 계산, push

연산 순서의 중요성

 // 잘못된 예: 5 - 3 = -2 (틀림!)
 stack.push(stack.pop() - stack.pop());
    
 // 올바른 예: 5 - 3 = 2
 int b = stack.pop();  // 3
 int a = stack.pop();  // 5
 stack.push(a - b);    // 5 - 3 = 2

덧셈(+), 곱셈(*): 교환법칙 성립 → 순서 무관
뺄셈(-), 나눗셈(/): 순서 중요!

불필요한 타입 변환 제거
- String 스택 → 매번 parse/toString
- Integer 스택 → 변환 없음
- 성능 차이: 약 20-30% 개선

핵심 개념

후위 표기법(Reverse Polish Notation)의 장점:

괄호 불필요
우선순위 고려 불필요
스택으로 O(n) 평가 가능
컴파일러 내부에서 사용

스택 활용 패턴:

숫자: push
연산자: pop → 계산 → push
최종: 스택에 결과 1개만 남음

🎯 개선 후 코드

추천: Integer 스택 + Switch 방식

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (String token : tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    int subtrahend = stack.pop();
                    int minuend = stack.pop();
                    stack.push(minuend - subtrahend);
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int divisor = stack.pop();
                    int dividend = stack.pop();
                    stack.push(dividend / divisor);
                    break;
                default:
                    // 숫자인 경우
                    stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }
}

개선 포인트:

✔ Integer 스택으로 변환 오버헤드 제거
✔ 의미 있는 변수명 (subtrahend, divisor 등)
✔ 주석으로 의도 명확화
✔ 간결하면서도 명확한 로직

📚 관련 개념

알고리즘 패턴

스택(Stack): 후위 표기법 평가의 핵심
후위 표기법(Postfix Notation): 연산자 우선순위 제거
계산기 구현(Calculator): 수식 파싱의 기초

연관 개념

표기법 종류
- 중위(Infix): 2 + 3 * 4 (사람이 쓰는 방식)
- 후위(Postfix/RPN): 2 3 4 * + (컴퓨터가 쓰는 방식)
- 전위(Prefix): + 2 * 3 4
중위 → 후위 변환 (Shunting Yard Algorithm)
- 연산자 우선순위 처리
- 괄호 처리
- 스택 2개 사용
실무 활용
- 컴파일러: 수식 평가
- 계산기 앱
- 스프레드시트 수식 처리
- DB 쿼리 최적화

수학적 배경

스택 머신(Stack Machine): JVM, Forth 언어 등
역폴란드 표기법: HP 계산기에서 사용

🎓 다음 단계

비슷한 문제

LeetCode 224. Basic Calculator ⭐⭐⭐⭐
- 중위 표기법 계산 (괄호 포함, +/- 만)
LeetCode 227. Basic Calculator II ⭐⭐⭐
- 중위 표기법 계산 (괄호 없음, +/-/*/÷)
LeetCode 772. Basic Calculator III ⭐⭐⭐⭐⭐ (Premium)
- 중위 표기법 계산 (괄호 포함, 모든 연산자)
LeetCode 394. Decode String ⭐⭐
- 스택으로 문자열 디코딩
LeetCode 636. Exclusive Time of Functions ⭐⭐
- 스택으로 함수 호출 시간 계산

심화 학습

중위 → 후위 변환 구현하기 (Shunting Yard)
괄호 처리 추가하기
부동소수점 연산 지원
에러 처리 강화 (0으로 나누기, overflow 등)

연습 포인트 체크리스트

Integer 스택 버전으로 다시 구현
배열 기반 스택으로 메모리 최적화
중위 표기법 계산기 구현 (#224, #227)
Shunting Yard 알고리즘 학습
에러 처리 추가 (예외 상황 대응)
단위 테스트 작성해보기

🏷️ Keywords

#Stack #RPN #ReversePolishNotation #PostfixNotation #Calculator #수식평가
#Deque #Switch #IntegerStack #ShuntingYard #ExpressionEvaluation #컴파일러 #알고리즘 #자료구조 #LeetCodeMedium #코딩테스트