Evaluate Reverse Polish Notation (Stack)

LeetCode의 Queue, Stack 튜토리얼의 네 번째 문제인 Evaluate Reverse Polish Notation다.

Explore - LeetCode

Reverse Polish Notation이 뭔가 했더니 옛날에 자료구조 수업시간에 배웠던 연산식 표기법이었다. 예를 들어 우리 같은 사람들은 보통 1과 2를 더한다고 하면 "1 + 2"처럼 표현하지만 컴퓨터에서는 "1 2 +"처럼 표현하는 방법이 있다는 얘기를 들었다. 이게 아마 컴파일러 쪽이었나 아무튼 이 방법이 더 효율적인 경우가 있다고 들었는데 위키피디아 문서를 읽어보니 표현식을 평가(evaluate)할 때 스택을 사용하여 컴퓨터 메모리를 효율적으로 사용하기 위한 방법이라고 한다. 이번 문제에서는 이 표현식을 생성하는 게 아니라 주어진 표현식을 스택을 이용하여 평가하는 코드를 작성하는 것이 목적이다.

 

문제의 조건은 다음과 같다.

• 평가 가능한 연산자는 '+', '-', '*', '/'로 제한한다.

• 주어진 표현식은 피연산자 두 개와 연산자 한 개로 이루어지는 규칙을 유지한다.

• 0으로 나누는 등 올바르지 않은 표현식은 주어지지 않는다.

• 두 정수 간 나눗셈은 정수형으로 변환하며 나머지는 버려야 한다.

문제의 예시는 다음처럼 주어진다.

["2", "1", "+", "3", "*"]

이는 피연산자 두 개와 연산자 한 개로 이루어지기 때문에 맨 처음에는 2와 1을 '+'하는, 즉 2 + 1을 수행하여 3이 되며 이는 뒤에 있는 3과 '*'하여 3 * 3을 수행하게 된다. 일반적인 표현식으로 나타내면 다음과 같을 것이다.

( ( 2 + 1 ) * 3 )

그럼 이를 어떻게 스택을 활용하여 변환할 수 있을까? 이는 괄호 검사랑 비슷한데 사칙 연산 기호를 만나면 스택에서 피연산자 두 개를 빼서 해당 연산 기호에 맞는 연산을 수행하고 다시 스택에 집어넣어서 다른 피연산자와 연산될 수 있도록 하면 된다.

import java.util.Stack;


class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        
        for(String token: tokens){
            if(token.equals("*") || token.equals("/") || token.equals("+") || token.equals("-")){
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;
                switch(token){
                    case "*":
                        result = num1 * num2;
                        break;
                    
                    case "/":
                        result = num1 / num2;
                        break;
                        
                    case "+":
                        result = num1 + num2;
                        break;
                        
                    case "-":
                        result = num1 - num2;
                        break;
                }
                stack.push(String.valueOf(result));
            } else {
                stack.push(token);
            }
        }
        
        return Integer.parseInt(stack.pop());
    }
}

연산자가 아니라면 스택에 삽입하고, 연산자라면 스택에서 피연산자를 꺼내 연산하고 그 결과(피연산자)를 스택에 집어넣는 과정을 반복하다 보면 언젠가는 모든 표현식을 평가하고 마지막 피연산자만 스택에 혼자 들어있게 된다. 이는 문자열이기 때문에 정수로 파싱 해서 반환해주면 문제없이 풀 수 있다.

 

재구성하다 보면 보이겠지만 ( ( ( ( a + b) / 3 ) +... )처럼 순서대로 괄호를 감싸면서 순서대로 표현식이 구축되는 것을 볼 수 있다. 아마 컴퓨터가 표현식을 평가하는데 뭔가 도움이 되긴 할 것 같다. 트리로 나타낸다면 오른쪽 노드로만 계속 뻗어나가는 모양이라던가...