[Leetcode Top Interview 150] 150. Evaluate Reverse Polish Notation

난이도 : medium

문제링크

• tokens이라는 String 배열이 주어짐
  • 후위표기식으로 표현되는 배열
• 결과를 리턴하라
  • 결과의 범위는 32bit

 

• division by zero 없음
• -200 <= operand <= 200

 

1. 접근법

• 두개의 배열을 선언
• operator를 만나기 전까지 left 배열에 operand 하나씩 push
• operator를 만나면 pop해서 연산결과를 다시 left 배열에 push
• left 배열 원소갯수가 1개일 때까지 반복
• 결과 리턴

 

2. 의사코드

Stack<Integer> left = new Stack<>();
Stack<Integer> right = new Stack<>();

int idx = 0;
while (idx != tokens.length) {	    
	if (tokens[idx]가 연산자) {
    	int second = right.pop();
        int first = right.pop();
        
        연산하기
        연산결과 left에 push        
    } else {
    	right.push(tokens[idx])
    }   
    
    idx++;
}

return left.peek();

 

 

3. 구현 코드

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

        int left;
        int right;
        int result;

        int idx = 0;

        while (idx < tokens.length) {
            String token = tokens[idx];
            if (isOperator(token)) {
                right = stack.pop();
                left = stack.pop();
                result = calculate(left, right, token);
                
                stack.push(result);                
            } else {
                stack.push(Integer.parseInt(token));
            }

            idx++;
        }

        return stack.pop();
    }

    private boolean isOperator(String token) {
        if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
            return true;
        }

        return false;
    }

    private int calculate(int left, int right, String operand) {
        return switch(operand) {
            case "+" -> left + right;
            case "-" -> left - right;
            case "*" -> left * right;
            case "/" -> left / right;
            default -> 0;        
        };
    }
}

• stack에서 먼저 뽑은 operand가 right operand (더 늦게 들어갔음)
• stack에서 나중에 뽑은 operand가 left operand (더 빨리 들어갔음)

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - tokens의 길이만큼 반복하면서 연산함
• 공간복잡도 : O(n) - 최대 tokens의 원소갯수의 반만큼 stack의 크기가 잡힐 수 있음

 

5. 개선점

잘 모르겠다

 

 

6. 회고

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        int right;
        int left;
        
        for (int i=0; i < tokens.length; i++) {
        	if (tokens[i].equals("+")) {
            	stack.push(stack.pop() + stack.pop());
            } else if (tokens[i].equals("-")) {
              	right = stack.pop();
                left = stack.pop();
            
            	stack.push(left - right);
            } else if (tokens[i].equals("*")) {
            	stack.push(stack.pop() * stack.pop());
            } else if (tokens[i].equals("/")) {
                right = stack.pop();
                left = stack.pop();
            
        	stack.push(left / right);
            } else {
            	stack.push(Integer.parseInt(tokens[i]));
            }
        }
        
        return stack.pop();
    }
}

(출처: NeetCode)

• 거의 유사하다
• 코딩 스타일만 다르다