[150. Evaluate Reverse Polish Notation] (알고리즘)
Stack
문제
You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.
Evaluate the expression. Return an integer that represents the value of the expression.
Note that:
- The valid operators are
'+','-','*', and'/'. - Each operand may be an integer or another expression.
- The division between two integers always truncates toward zero.
- There will not be any division by zero.
- The input represents a valid arithmetic expression in a reverse polish notation.
- The answer and all the intermediate calculations can be represented in a 32-bit integer.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”] Output: 9 Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,”13”,”5”,”/”,”+”] Output: 6 Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,””,”/”,””,”17”,”+”,”5”,”+”] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Constraints:
1 <= tokens.length <= 104tokens[i]is either an operator:"+","-","*", or"/", or an integer in the range[-200, 200].
스스로 고민
접근법
- Reverse Polish Notation 이 뭔지 찾아 봤는데 피연산자가 뒤에 나오는 표기법이다.
- 우선순위나 괄호가 필요 없다.
-
중위 표기법: 5 + ((1 + 2) * 4) - 3 RPN: 5 1 2 + 4 * + 3 - 계산: 5 + (3 * 4) - 3 = 5 + 12 - 3 = 14
-
중위 표기법: ((7 - 3) * (2 + 1)) / 4 RPN: 7 3 - 2 1 + * 4 / 계산: (7 - 3) * (2 + 1) / 4 = 4 * 3 / 4 = 3
-
중위 표기법: 10 + (3 * (8 - 4)) ^ 2 RPN: 10 3 8 4 - * 2 ^ + 계산: 10 + (3 * 4) ^ 2 = 10 + 12 ^ 2 = 10 + 144 = 154
-
중위 표기법: (6 * (5 + 2)) - 8 / 4 RPN: 6 5 2 + * 8 4 / - 계산: (6 * 7) - (8 / 4) = 42 - 2 = 40
- 스택으로 순서대로 넣어서 뽑아 쓰면 될거 같다.
의사코드
- push로 모든 내용을 다 넣는다.
- 연산자는 따로 정해준다.
- 처음 진행할 때 숫자가 있어야 연산이 되니까 연산자가 있다면 패스
- 숫자가 나온다면 스택으로 쌓는다
- 숫자가 쌓인 상태에서 연산자가 나온다면 연산을 진행한다.
- 처음에 맞는거 같은데 계속 오류가 나서 문제를 확인해보니 나눗셈을 할 때는 나머지를 버리도록 해야한다.
- 계산된 값을 계속 push 해주고 마지막에 pop 을 리턴해주면 된다.
구현 코드
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
if not self.is_empty():
return self.items.pop()
def top(self):
if not self.is_empty():
return self.items[-1]
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = Stack()
operators = {'+', '-', '*', '/'}
if len(tokens) == 1: return int(tokens[0])
for token in tokens:
if token not in operators:
stack.push(int(token))
else:
second = stack.pop()
first = stack.pop()
answer = 0
if token == "+":
answer = first + second
elif token == "-":
answer = first - second
elif token == "/":
answer = int(first / second)
else:
answer = first * second
stack.push(answer)
return stack.pop()
시간 복잡도와 공간 복잡도
시간 복잡도:
- 반복문에서 토큰의 개수인 O(n) 번 실행된다. 각 반복에서 수행되는 작업은 O(1) 시간이 걸린다.
- 스택에 값을 추가하거나 연산을 수행하는 작업은 O(1) 시간이 소요된다.
- 따라서 전체적으로
evalRPN()메서드의 시간 복잡도는 O(n) 다.
공간 복잡도:
stack객체는 입력된 토큰의 값을 저장하기 위한 공간을 필요로 한다. 최악의 경우 n개의 토큰을 저장해야 하므로 O(n)의 공간이 소요된다.operators세트는 연산자를 저장하기 위한 공간을 필요로 한다. 연산자의 개수에 상관없이 고정된 크기를 가지므로 O(1)의 공간이 소요된다.- 나머지 변수들은 상수 개수의 메모리를 사용하므로 공간 복잡도에 영향을 주지 않는다.
- 따라서 전체적으로 공간 복잡도는 O(n) 다.
회고 과정
다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
def evaluate(x1: int, x2: int, operator: str) -> int:
if operator == "+":
return x1 + x2
elif operator == "-":
return x1 - x2
elif operator == "*":
return x1 * x2
else:
return int(x1 / x2)
operators = {"+", "-", "*", "/"}
stack = []
for s in tokens:
if s in operators:
x2 = stack.pop()
x1 = stack.pop()
stack.append(evaluate(x1, x2, s))
else:
stack.append(int(s))
return stack.pop()
- 위와 같이 아예 계산되는 과정을 함수로 정의한 후 리스트에 결과 값을 담은 다음 가장 마지막 값을 추출하는 형식이다.
- stack을 구현해서 연습하느라고 코드가 좀 길어지긴 했지만 이렇게 사용한다면 가독성이 정말 좋은 것 같다.
댓글남기기