Evaluate Reverse Polish Notation
역폴란드 표기법으로 된 산술식을 토큰 배열로 받습니다. 각 연산자는 두 피연산자 바로 뒤에 오므로, 3 4 +는 3 + 4를 의미하고 3 4 + 2 *는 괄호 없이 (3 + 4) * 2를 의미합니다. 각 토큰은 정수이거나 연산자 +, -, *, / 중 하나입니다.
식의 값을 반환하세요. 나눗셈은 0을 향해 버림합니다. 즉, 7 / 2는 3이고 -7 / 2는 -3입니다.
함수
- tokensstring-array
- 표현식의 숫자와 연산자를 순서대로
- 반환값integer
- 표현식의 값
제약 조건
1 ≤ tokens.length ≤ 104- 각 토큰은
+,-,*,/또는-200부터200까지의 정수이며, 10진수로 표기되고 음수인 경우 앞에 빼기 기호가 붙습니다. tokens는 역폴란드 표기법에서 유효한 표현식입니다.- 0으로 나누는 일은 발생하지 않으며, 모든 중간값과 최종값은
-231보다 크고231보다 작습니다.
예제
- 입력
- tokens = ["8", "3", "-", "4", "*"]
- 출력
- 20
- 설명
-는 8에 먼저, 그다음 3에 적용되므로 5가 됩니다. -5가 아닙니다. 그런 다음*는 그 5에 4를 곱하므로 20이 됩니다.
- 입력
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- 출력
- -6
- 설명
/는 가장 최근의 두 값을 사용합니다. 9를 3으로 나누면 3입니다. 그런 다음-는 2에서 3을 빼서 -1을 계산하고,*는 6에 -1을 곱합니다.
- 입력
- tokens = ["10", "-7", "2", "/", "+"]
- 출력
- 7
- 설명
- 토큰
-7은 연산자가 아니라 숫자입니다. -7을 2로 나누면 -3.5이며, 이는 0을 향해 버림하여 -3이 됩니다. -4가 아니며, 10에 -3을 더하면 7입니다.
후속 질문
의미가 달라지는 경우에만 괄호를 추가하여 (3 + 4) * 2와 같은 일반적인 표기법으로 식을 다시 만들 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
토큰을 왼쪽에서 오른쪽으로 읽으세요. 연산자를 만나면, 어떤 두 값에 적용되나요? 그 값들이 생성된 순서를 살펴보세요.
연산자는 항상 아직 어떤 연산자도 사용하지 않은 가장 최근의 두 값에 적용되며, 그 결과는 뒤따르는 연산자들이 사용할 새로운 값이 됩니다. “아직 사용되지 않은 가장 최근 값”은 바로 스택이 제공하는 것입니다.
모든 숫자를 푸시하세요. 연산자를 만나면 오른쪽 피연산자를 먼저 팝하고 왼쪽 피연산자를 두 번째로 팝한 다음, 그 순서대로 결합하고 결과를 푸시하세요. 토큰이 모두 소진되면 스택에는 값 하나, 즉 답이 남습니다. 나눗셈이 0을 향해 버림되도록 하세요.
풀이
각 연산자는 바로 앞에 있는 두 값에 적용되며, 둘 중 하나는 앞선 연산의 결과일 수도 있습니다. 따라서 값 스택을 사용하면 식을 한 번에 평가할 수 있습니다. 주의할 점은 -와 /의 피연산자 순서, 연산자 -와 숫자 -7의 구분, 그리고 나눗셈의 버림 처리입니다.
첫 번째 연산자를 접어 반복하기
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
가장 왼쪽에 있는 연산자를 찾습니다. 그 앞에는 연산자가 없으므로, 그 앞의 두 토큰은 숫자, 즉 피연산자입니다. 이 세 토큰을 결과로 바꿉니다. 뒤에 있는 연산자들은 해당 부분이 있던 자리에 그 값이 있다고 보고 연산하므로, 식의 의미는 그대로 유지됩니다. 숫자 하나만 남을 때까지 반복합니다.
매 라운드마다 처음부터 다시 검색합니다. 숫자 5,000개 뒤에 연산자 4,999개가 오는 경우, 각 라운드에서 첫 번째 연산자는 대략 중간 지점에 있으므로 검색만으로 약 1.25 × 10^7개의 토큰을 읽습니다.
알고리즘
- 토큰을 변경할 수 있는 목록에 복사합니다.
- 처음부터 스캔하여 위치
k에서 첫 번째 연산자를 찾습니다. k-2(왼쪽)와k-1(오른쪽)에 있는 숫자에 연산을 적용합니다.k-2,k-1,k에 있는 세 토큰을 결과로 바꿉니다.- 토큰이 하나만 남을 때까지 반복한 다음, 그 토큰을 숫자로 반환합니다.
def evalRPN(tokens):
items = list(tokens)
while len(items) > 1:
# Find the first operator. Everything to its left is a plain number.
k = 0
while items[k] not in ("+", "-", "*", "/"):
k += 1
left, right, op = int(items[k - 2]), int(items[k - 1]), items[k]
if op == "+":
value = left + right
elif op == "-":
value = left - right
elif op == "*":
value = left * right
else:
value = int(left / right) # int() truncates toward zero
# Replace the three tokens "left right op" with the number they stand for.
items[k - 2:k + 1] = [str(value)]
return int(items[0])값 스택을 사용한 한 번의 순회
핵심 아이디어
값을 다시 읽는 대신 연산자의 왼쪽에 있는 값들을 스택에 보관하세요. 숫자는 스택에 들어갑니다. 연산자는 값 두 개를 꺼내 결합한 다음 결과를 스택에 넣고, 결과는 다른 값과 마찬가지로 다음 연산자를 기다립니다. 스택에는 지금까지 읽은 완전한 부분식들의 값이 순서대로 항상 들어 있으므로, 연산자는 항상 맨 위의 두 값에 적용됩니다. 맨 위의 값은 가장 마지막에 만들어졌으므로 오른쪽 피연산자입니다.
6 2 9 3 / - *에서 /는 3을 꺼낸 다음 9를 꺼내 3을 넣고, -는 3을 꺼낸 다음 2를 꺼내 -1을 넣으며, *는 6 × -1 = -6을 넣습니다. 각 토큰은 한 번씩 처리됩니다. 시간은 O(n), 공간은 O(n)입니다.
알고리즘
- 빈 스택으로 시작합니다.
- 각 숫자 토큰에 대해 해당 값을 푸시합니다.
- 각 연산자에 대해 오른쪽 피연산자를 팝한 다음 왼쪽 피연산자를 팝합니다.
left op right를 계산하고,/의 경우 0을 향해 버림한 뒤 결과를 푸시합니다.- 마지막 토큰을 처리한 후 스택에 있는 단일 값을 반환합니다.
def evalRPN(tokens):
stack = [] # values of the parts read so far, the newest on top
for token in tokens:
if token in ("+", "-", "*", "/"):
# The right operand was pushed last, so it comes off first.
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // would round -7 / 2 down to -4.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]
함정과 경계 사례
- 피연산자의 순서를 바꾸는 것. 첫 번째로 꺼내는 값은 오른쪽 피연산자입니다.
["3", "5", "-"]의 결과는 -2이고,["2", "9", "/"]의 결과는 4가 아니라 0입니다. - 연산자를 첫 번째 문자로 판별하는 것.
-7은 마이너스 기호로 시작하지만 숫자이므로 토큰 전체를 비교해야 합니다. - 버림 대신 내림을 하는 것. Python의
//, Ruby의/, R의%/%, Lua의math.floor는-7 / 2를 -4로,-1 / 3을 -1로 만듭니다. -0을 출력하는 것. JavaScript와 Lua에서는0 * -5와Math.trunc(-1 / 3)이 음의 0을 반환합니다. 최종 값에 0을 더하세요.
자주 묻는 질문4
역폴란드 표기법 평가의 시간 복잡도는 얼마인가요?
스택 풀이의 시간 복잡도는 n개의 토큰에 대해 O(n)입니다. 각 숫자는 한 번 푸시되고, 각 연산자는 두 번 팝하고 한 번 푸시합니다. 스택에는 최대 약 n/2개의 값이 들어가므로 공간 복잡도는 O(n)입니다.
역폴란드 표기법에는 왜 괄호가 필요하지 않을까요?
일반적인 표기법에서는 어떤 연산을 먼저 수행하는지 나타내려면 3 + 4 * 2에 우선순위 규칙이나 괄호가 필요합니다. 역폴란드 표기법에서는 연산자가 항상 바로 앞에 있는 두 값에 적용되므로 토큰 순서에 따라 결과가 결정됩니다. 3 4 2 * +는 11이고 3 4 + 2 *는 14입니다.
Python에서 0을 향해 버림하여 나누려면 어떻게 하나요?
int(a / b)를 사용하세요. // 연산자는 내림하므로 -7 // 2는 -4인 반면, int(-7 / 2)는 -3입니다. 부동 소수점 나눗셈은 32비트 값에 충분히 정확합니다. 더 큰 정수의 경우 절댓값을 //로 나눈 다음 부호를 다시 적용하세요.
일반적인 표현식을 역폴란드 표기법으로 어떻게 바꾸나요?
셔닝 야드 알고리즘은 연산자 스택을 사용해 한 번의 순회로 처리합니다. 숫자는 바로 출력으로 보냅니다. 연산자를 스택에 넣기 전에 우선순위가 같거나 더 높은 스택의 연산자를 모두 출력으로 옮깁니다. 닫는 괄호가 나오면 짝이 되는 여는 괄호가 나올 때까지 연산자를 꺼냅니다. 마지막에는 나머지 연산자를 출력으로 보냅니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def evalRPN(tokens):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
tokens = ["8", "3", "-", "4", "*"]
예상 출력
20