[알고리즘/Python] 150. Evaluate Reverse Polish Notation - 스택 풀이

📑 1. 문제 이해

https://leetcode.com/problems/evaluate-reverse-polish-notation/

Evaluate Reverse Polish Notation - LeetCode

후위 표현식을 계산하는 문제입니다. 주의해야할 점은 다음과 같습니다

- 숫자는 음수가 될 수 있습니다.

- 나눗셈의 경우 0으로 나누는 경우는 존재하지 않습니다.

- 나눗셈의 결과를 소수점 자리는 버립니다.(truncate toward zero)

- 중간 연산의 결과가 4바이트를 넘지 않습니다. python은 int와 long을 구분하지 않기 때문에 상관없지만 java와 같이 정적 타입 언어의 경우에는 문제가 될 수 있습니다. 

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같습니다.

 

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

 

Example 2: ["4", "13", "5", "/", "+"]

- 나눗셈이 포함되어 있습니다.

 

Example 3: ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

- 음수가 포함되어 있습니다.

💡 2. 알고리즘 설계

 스택을 이용하면 계산할 수 있습니다. 숫자는 스택에 저장해두고 연산자가 등장할때마다 두 개의 수를 빼서 계산한 후 결과를 다시 스택에 저장합니다. 마지막에 스택에 있는 하나의 수가 결과가 됩니다.

 주의할 점은 뺄셈, 나눗셈의 경우 숫자의 순서가 중요하며 마지막에 빠진 수가 뺄셈에서 빼는 수, 나눗셈에서 분모가 됩니다.

1. tokens 배열을 순회하면서 숫자를 표현한 문자인 경우에는 스택에 숫자로 바꾸어서 저장합니다.

2. 연산자를 표현한 문자의 경우 스택에서 두개의 수를 빼 대응하는 연산을 수행합니다. 첫번째 뺀 수를 num1, 두번째 뺀수를 num2라고 하면, (num2 +-*/ num1)를 계산합니다.

3. 계산한 결과를 스택에 저장합니다.

4. 마지막에 스택에 하나의 원소만 저장되어있으며, 그 원소를 반환합니다.

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operations = {"+", "-", "*", "/"}
        for c in tokens:
            # if c.isnumeric():
            if c not in operations:
                stack.append(int(c))

            else:
                b = stack.pop()
                a = stack.pop()

                if c == "+":
                    stack.append(a + b)
                elif c == "-":
                    stack.append(a - b)
                elif c == "*":
                    stack.append(a * b)
                elif c == "/":
                    stack.append(math.trunc(a/b))
        return stack[-1]

 음수를 표현한 문자의 경우 s.isnumeric()으로 판단할 수 없습니다. 음수의 경우 s.isnumeric()은 False가 반환됩니다.  버림을 수행하기 위해서는 math.trunc() 혹은 int()연산을 수행할 수 있습니다.

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열을 한번만 순회합니다. 스택에 넣었다 빼는 연산이 수행되지만 O(1) 복잡도를 가집니다.

공간 복잡도: O(N). 숫자들을 저장하기 위한 스택이 필요합니다.

---

✅ 정리

◎ 스택이 자주 응용되는 곳은 1) 중위표현식의 후위표현식으로 변환, 후위표현식의 계산 2) undo 3)DFS, 백트래킹 4) 컴퓨터의 스택 메모리 5) 괄호 짝 맞추기 등 입니다.