Evaluate Reverse Polish Notation

Q: 역폴란드 표기법 평가의 시간 복잡도는 얼마인가요?

스택 솔루션은 n 개의 토큰에 대해 O(n) 시간이 걸립니다. 각 숫자는 한 번 푸시되고, 각 연산자는 두 번 팝하고 한 번 푸시합니다. 스택에는 최대 약 n/2 개의 값이 들어갈 수 있으므로 공간 복잡도는 O(n) 입니다. 첫 번째 연산자를 계속해서 결합하면 매번 처음부터 다시 검색하므로 O(n²) 시간이 걸립니다.

Q: 역폴란드 표기법에는 왜 괄호가 필요하지 않을까요?

일반적인 표기법에서 3 + 4 * 2 는 어떤 연산을 먼저 수행하는지 나타내기 위해 연산자 우선순위 규칙이나 괄호가 필요합니다. 역폴란드 표기법에서는 연산자가 항상 바로 앞의 두 값에 적용되므로 토큰의 순서가 모든 것을 말해 줍니다. 3 4 2 * + 는 11이고 3 4 + 2 * 는 14입니다. 그래서 미리 살펴보지 않고도 하나의 스택만으로 계산할 수 있습니다.

Q: Python에서 0을 향해 버림하여 나누려면 어떻게 하나요?

int(a / b) 를 사용하세요. // 연산자는 내림하므로 -7 // 2 는 -4인 반면, int(-7 / 2) 는 -3입니다. 여기서는 값이 32비트에 들어가므로 부동 소수점 나눗셈이 충분히 정확합니다. 임의로 큰 정수의 경우 절댓값을 // 로 나눈 다음 부호를 다시 붙이세요.

보통스택

+10

역폴란드 표기법으로 된 산술식을 토큰 배열로 받습니다. 이 표기법에서는 각 연산자가 두 피연산자 바로 뒤에 오므로, 3 4 +는 3 + 4를 의미하고 3 4 + 2 *는 괄호 없이 (3 + 4) * 2를 의미합니다. 각 토큰은 정수이거나 +, -, *, / 연산자 중 하나입니다.

식을 계산하여 그 값을 반환하세요. 나눗셈은 정수 부분만 취하고 0을 향해 버림합니다. 즉, 7 / 2는 3이고 -7 / 2는 -3입니다.

함수

evalRPN(tokens: string-array) → integer

tokensstring-array: 표현식의 숫자와 연산자를 순서대로
반환값integer: 표현식의 값

제약 조건

1 ≤ tokens.length ≤ 10⁴
각 토큰은 +, -, *, / 또는 -200부터 200까지의 정수이며, 10진수로 표기되고 음수인 경우 앞에 빼기 기호가 붙습니다.
tokens는 역폴란드 표기법에서 유효한 표현식입니다.
0으로 나누는 일은 발생하지 않으며, 모든 중간값과 최종값은 -2³¹보다 크고 2³¹보다 작습니다.

예제

입력: 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이며, 이는 내림하여 -4가 되는 것이 아니라 0을 향해 버림하여 -3이 되고, 10 더하기 -3은 7입니다.

제출 시 숨은 테스트 +18개

후속 질문

괄호를 의미를 바꾸는 경우에만 추가하여 (3 + 4) * 2와 같은 일반적인 표기법으로 식을 다시 구성할 수 있나요?

풀이

역폴란드 표기법에서는 토큰의 순서가 연산 순서를 이미 결정하므로 괄호가 필요하지 않습니다. 각 연산자는 바로 앞에 있는 두 값에 적용되며, 그 값 중 하나는 이전 연산의 결과일 수도 있습니다. 값 스택을 사용하면 전체 식을 왼쪽에서 오른쪽으로 한 번 훑으며 계산할 수 있습니다. 주의해야 할 점은 세부 사항에 있습니다. -와 /의 피연산자 순서, 연산자 -와 숫자 -7을 구별하는 방법, 그리고 0을 향해 버림하는 나눗셈입니다.

첫 번째 연산자 접기, 반복

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

종이에 풀 때는 이렇게 하면 됩니다. 가장 왼쪽에 있는 연산자를 찾습니다. 그 앞에는 연산자가 없으므로, 바로 앞의 두 토큰은 일반 숫자이며 해당 연산자의 피연산자입니다. 결과를 계산하고 이 세 토큰을 숫자 하나로 바꿉니다. 식은 이제 더 짧아졌지만 여전히 같은 의미입니다. 숫자 하나만 남을 때까지 반복합니다.

["6", "2", "9", "3", "/", "-", "*"]를 살펴보겠습니다. 첫 번째 연산자는 /이므로 9 3 /은 3이 됩니다. 즉, ["6", "2", "3", "-", "*"]가 됩니다. 다음으로 2 3 -은 -1이 됩니다. 즉, ["6", "-1", "*"]가 됩니다. 그다음 6 -1 *은 -6이 되며, 이것이 답입니다.

각 단계에서 완전한 부분식 a b op를 그 값으로 바꾸고, 그 뒤의 연산자들이 해당 부분식이 있던 바로 그 위치에서 그 값을 사용하므로 올바른 방법입니다. 매 단계마다 처음부터 다시 검색한 다음 배열 중간의 빈자리를 메우기 때문에 느립니다. 숫자 5,000개 뒤에 연산자 4,999개가 있다면, 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", "/", "-", "*"]를 차례로 살펴보세요. 네 숫자를 스택에 넣습니다: [6, 2, 9, 3]. /는 3을 꺼낸 다음 9를 꺼내고 9 / 3 = 3을 넣습니다: [6, 2, 3]. -는 3을 꺼낸 다음 2를 꺼내고 2 - 3 = -1을 넣습니다: [6, -1]. *는 -1을 꺼낸 다음 6을 꺼내고 6 * -1 = -6을 넣습니다. 값 하나가 남으며, 그것이 답입니다.

작동하는 이유: 어느 순간이든 스택에는 지금까지 읽은 완성된 부분들의 값이 순서대로 들어 있으며, 연산자는 항상 그중 마지막 두 값에 적용됩니다. 스택의 맨 위 값은 마지막에 만들어졌으므로 오른쪽 피연산자입니다. 따라서 이 값을 먼저 꺼냅니다. 순서를 잘못 처리해도 -와 /에서만 드러나는데, 이때 8 3 -의 결과는 -5가 아니라 5여야 합니다.

일부 언어에서는 나눗셈에 주의해야 합니다. 이 식은 0을 향해 버림하지만, Python의 //, Ruby의 /, R의 %/%는 내림하므로 -3.5가 -4가 됩니다. 각 숫자는 한 번씩 스택에 들어가고 각 연산자는 값 두 개를 꺼내 하나를 넣으므로, 이 과정은 O(n) 시간이 걸리고 스택에는 최대 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은 빼기 기호로 시작하지만 숫자입니다. 토큰 전체를 비교하거나, 토큰의 길이가 1자인지 확인하세요.
버림이 아닌 내림을 하는 경우. -7 / 2의 결과는 -3이어야 하고, -1 / 3의 결과는 0이어야 합니다. Python의 //, Ruby의 /, R의 %/%, Lua의 math.floor는 각각 -4와 -1을 반환합니다.
-0을 출력하는 경우. JavaScript와 Lua에서는 모든 숫자가 부동소수점 수이므로 0 * -5와 Math.trunc(-1 / 3)은 음의 0을 반환하며, 이는 -0으로 출력됩니다. 최종 값에 0을 더하면 0으로 바뀝니다.
숫자를 한 번에 한 자리씩 읽는 경우. 13과 -200 같은 토큰은 여러 문자로 이루어져 있으므로 토큰 전체를 파싱하세요.
마지막 토큰이 연산자라고 가정하는 경우. ["7"]처럼 숫자 하나만 있는 것도 값이 7인 유효한 수식입니다.

자주 묻는 질문4

역폴란드 표기법 평가의 시간 복잡도는 얼마인가요?

스택 솔루션은 n개의 토큰에 대해 O(n) 시간이 걸립니다. 각 숫자는 한 번 푸시되고, 각 연산자는 두 번 팝하고 한 번 푸시합니다. 스택에는 최대 약 n/2개의 값이 들어갈 수 있으므로 공간 복잡도는 O(n)입니다. 첫 번째 연산자를 계속해서 결합하면 매번 처음부터 다시 검색하므로 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비트에 들어가므로 부동 소수점 나눗셈이 충분히 정확합니다. 임의로 큰 정수의 경우 절댓값을 //로 나눈 다음 부호를 다시 붙이세요.

일반 표현식을 역폴란드 표기법으로 어떻게 바꾸나요?

셔팅 야드 알고리즘은 연산자 스택을 사용해 한 번의 순회로 처리합니다. 숫자는 바로 출력으로 이동합니다. 연산자를 스택에 넣기 전에 스택에 있는 우선순위가 같거나 더 높은 모든 연산자를 출력으로 옮깁니다. 여는 괄호는 스택에 넣고, 닫는 괄호는 짝이 되는 괄호를 만날 때까지 연산자를 출력으로 옮깁니다. 마지막에는 남은 연산자를 출력으로 옮깁니다.

Python

def evalRPN(tokens):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

tokens = ["8", "3", "-", "4", "*"]

기대값