728x90
Postfix Notation
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.
Reverse Polish Notation(RPN)이라는 말이 낯설었는데, 자료구조 시간에 배운 Postfix Notation(후위표기법)이었다.
Postfix Notation은 연산자가 피연산자 뒤에 위치하는 표기법으로, 괄호가 없이도 연산자 우선순위를 명확히 표현할 수 있다.
이 때문에 컴퓨터의 스택 기반 연산에서 매우 효율적이게 동작한다.
Infix Notation(중위표기법) / Prefix Notation(전위표기법) / Postfix Notation(후위표기법) 정도는 기억해두자!
풀이: Stack 이용
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t == "+":
a, b = stack.pop(), stack.pop()
stack.append(a + b)
elif t == '-':
a, b = stack.pop(), stack.pop()
stack.append(b - a)
elif t == '*':
a, b = stack.pop(), stack.pop()
stack.append(a * b)
elif t == '/':
a, b = stack.pop(), stack.pop()
stack.append(int(b / a))
else:
stack.append(int(t))
return stack[0]숫자는 stack에 저장하고, operand를 만나면 stack에서 꺼내 바로 연산하면 된다.
truncates toward zero: //를 써도 될까?
The division between two integers always truncates toward zero.
이 문제를 처음에 틀렸던 이유는 이 부분 때문이었는데,
division에서 truncates toward zero를 하기 위해서 //를 쓰면 된다고 생각했던 것이다.
파이썬에서 //는 truncate가 아니라 floor(내림) 방식으로 연산한다.
따라서 음수에서 -7 // 3 = -3 와 같이 연산한다.
이 문제에서는 자연수가 아니라 integer를 연산해야하므로, //를 쓰면 안 되고 int()로 형변환하는 방식을 택해야 한다.
728x90