Evaluate Reverse Polish Notation

Q: Qual é a complexidade de tempo para avaliar a notação polonesa reversa?

A solução com pilha executa em O(n) de tempo para n tokens: cada número é empilhado uma vez, e cada operador faz duas remoções e uma inserção na pilha. A pilha pode conter até cerca de n/2 valores, então o espaço é O(n) . Reduzir repetidamente o primeiro operador leva O(n²) de tempo, porque a cada rodada a busca recomeça do início.

Q: Por que a notação polonesa reversa não precisa de parênteses?

Na notação comum, 3 + 4 * 2 precisa de uma regra de precedência ou de parênteses para indicar qual operação vem primeiro. Na notação polonesa inversa, um operador sempre se aplica aos dois valores imediatamente anteriores, então a ordem dos tokens diz tudo: 3 4 2 * + é 11 e 3 4 + 2 * é 14. É por isso que uma única pilha consegue avaliá-la sem precisar olhar adiante.

Q: Como fazer uma divisão com truncamento em direção a zero em Python?

Use int(a / b) . O operador // arredonda para baixo, então -7 // 2 é -4, enquanto int(-7 / 2) é -3. A divisão de ponto flutuante é suficientemente exata aqui porque os valores cabem em 32 bits. Para inteiros arbitrariamente grandes, divida os valores absolutos usando // e coloque o sinal de volta depois.

MédioPilha

+10

Você recebe uma expressão aritmética em notação polonesa reversa, como um array de tokens. Nessa notação, cada operador vem logo após seus dois operandos, então 3 4 + significa 3 + 4 e 3 4 + 2 * significa (3 + 4) * 2, sem necessidade de parênteses. Cada token é um número inteiro ou um dos operadores +, -, * e /.

Avalie a expressão e retorne seu valor. A divisão mantém apenas a parte inteira e trunca em direção a zero: 7 / 2 é 3 e -7 / 2 é -3.

Função

evalRPN(tokens: string-array) → integer

tokensstring-array: os números e operadores da expressão, em ordem
Retornainteger: o valor da expressão

Restrições

1 ≤ tokens.length ≤ 10⁴
Cada token é +, -, *, / ou um número inteiro de -200 a 200 escrito em decimal, com um sinal de menos à esquerda quando for negativo.
tokens é uma expressão válida em notação polonesa reversa.
Não ocorre divisão por zero, e todos os valores intermediários e finais são maiores que -2³¹ e menores que 2³¹.

Exemplos

Entrada: tokens = ["8", "3", "-", "4", "*"]
Saída: 20
Explicação: O - é aplicado aos dois números que vêm antes dele, na ordem em que aparecem: 8 e depois 3, então resulta em 5, não em -5. Em seguida, * multiplica esse 5 por 4, resultando em 20.

Entrada: tokens = ["6", "2", "9", "3", "/", "-", "*"]
Saída: -6
Explicação: O primeiro operador, /, usa os dois valores mais recentes: 9 dividido por 3 é 3. Em seguida, - calcula 2 menos esse 3, que é -1, e * multiplica 6 por -1.

Entrada: tokens = ["10", "-7", "2", "/", "+"]
Saída: 7
Explicação: O token -7 é um número, não um operador. -7 dividido por 2 é -3.5, que é truncado em direção a zero para -3, em vez de arredondado para baixo para -4, e 10 mais -3 é 7.

+18 testes ocultos ao enviar

Para ir além

Você consegue reconstruir a expressão na notação comum, como (3 + 4) * 2, adicionando parênteses somente onde eles alteram o significado?

Solução

A notação polonesa reversa não precisa de parênteses porque a ordem dos tokens já determina a ordem das operações: cada operador é aplicado aos dois valores imediatamente anteriores a ele, e qualquer um desses valores pode ser o resultado de um operador anterior. Uma pilha de valores avalia a expressão inteira em uma única passagem da esquerda para a direita. As armadilhas estão nos detalhes: a ordem dos operandos para - e /, distinguir o operador - do número -7 e a divisão que trunca em direção a zero.

Recolha o primeiro operador, repita

Correta, mas não termina nos maiores testes

Intuição

É assim que você resolveria isso no papel. Encontre o operador mais à esquerda. Nenhum operador vem antes dele, então os dois tokens imediatamente anteriores são números simples e são seus operandos. Calcule o resultado e substitua esses três tokens por um número. A expressão agora é mais curta e ainda significa a mesma coisa. Repita até restar um único número.

Considere ["6", "2", "9", "3", "/", "-", "*"]. O primeiro operador é /, então 9 3 / se torna 3: ["6", "2", "3", "-", "*"]. Depois, 2 3 - se torna -1: ["6", "-1", "*"]. Depois, 6 -1 * se torna -6, a resposta.

Está correto porque cada rodada substitui uma parte completa a b op pelo seu valor, e os operadores que vêm depois veem esse valor exatamente onde a parte estava. É lento porque, em cada rodada, a busca recomeça do início e depois fecha uma lacuna no meio do array. Com 5,000 números seguidos por 4,999 operadores, o primeiro operador fica aproximadamente na metade em todas as 4,999 rodadas, então somente as buscas verificam cerca de 1.25 × 10^7 tokens. Os números à esquerda do operador quase não mudam de uma rodada para a seguinte, mas são lidos novamente em todas as rodadas.

Algoritmo

Copie os tokens para uma lista que você possa alterar.
Percorra a lista do início até o primeiro operador, na posição k.
Aplique-o aos números nas posições k-2 (à esquerda) e k-1 (à direita).
Substitua os três tokens nas posições k-2, k-1 e k pelo resultado.
Repita até restar um token e retorne-o como número.

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])

Uma passagem com uma pilha de valores

Intuição

A abordagem de recolhimento relê os números à esquerda do operador. Em vez disso, mantenha-os em uma pilha. Leia os tokens uma única vez, da esquerda para a direita. Um número vai para a pilha. Um operador retira os dois valores do topo da pilha, combina-os e coloca o resultado de volta, onde ele aguarda o próximo operador como qualquer outro valor.

Percorra ["6", "2", "9", "3", "/", "-", "*"]. Os quatro números vão para a pilha: [6, 2, 9, 3]. O / retira 3 e depois 9 e coloca 9 / 3 = 3 na pilha: [6, 2, 3]. O - retira 3 e depois 2 e coloca 2 - 3 = -1 na pilha: [6, -1]. O * retira -1 e depois 6 e coloca 6 * -1 = -6 na pilha. Resta um valor, e ele é a resposta.

Por que funciona: a cada momento, a pilha contém os valores das partes completas lidas até então, em ordem, e um operador sempre é aplicado às duas últimas. O topo da pilha é o operando à direita, porque foi produzido por último; portanto, retire-o primeiro. Errar essa ordem só fica evidente com - e /, em que 8 3 - deve resultar em 5, e não em -5.

A divisão exige cuidado em algumas linguagens. A expressão trunca em direção a zero, mas // do Python, / do Ruby e %/% do R arredondam para baixo, transformando -3.5 em -4. Cada número é empilhado uma vez, e cada operador retira dois valores e empilha um, então a passagem leva O(n) de tempo, e a pilha nunca contém mais do que n valores.

Algoritmo

Comece com uma pilha vazia.
Para cada token que seja um número, empilhe seu valor.
Para cada operador, desempilhe o operando da direita e, em seguida, o operando da esquerda.
Calcule left op right, truncando em direção a zero para /, e empilhe o resultado.
Após o último token, retorne o único valor na pilha.

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]

Armadilhas e casos extremos

O loop da pilha é curto; a maioria das respostas erradas se deve à ordem dos operandos e à forma como a linguagem faz divisões.

Trocar os operandos. O primeiro valor removido é o operando à direita: ["3", "5", "-"] é -2, e ["2", "9", "/"] é 0, não 4.
Identificar operadores pelo primeiro caractere. -7 começa com um sinal de menos, mas é um número. Compare o token inteiro ou verifique se ele tem apenas um caractere.
Arredondar para baixo em vez de truncar. -7 / 2 deve resultar em -3, e -1 / 3 deve resultar em 0. // do Python, / do Ruby, %/% do R e math.floor do Lua resultam em -4 e -1.
Exibir -0. Em JavaScript e Lua, todo número é um float, então 0 * -5 e Math.trunc(-1 / 3) resultam em zero negativo, que é exibido como -0. Some 0 ao valor final para transformá-lo em 0.
Ler um número dígito por dígito. Tokens como 13 e -200 têm vários caracteres; analise o token inteiro.
Supor que o último token é um operador. Um único número, como ["7"], é uma expressão válida cujo valor é 7.

Perguntas frequentes4

Qual é a complexidade de tempo para avaliar a notação polonesa reversa?

A solução com pilha executa em O(n) de tempo para n tokens: cada número é empilhado uma vez, e cada operador faz duas remoções e uma inserção na pilha. A pilha pode conter até cerca de n/2 valores, então o espaço é O(n). Reduzir repetidamente o primeiro operador leva O(n²) de tempo, porque a cada rodada a busca recomeça do início.

Por que a notação polonesa reversa não precisa de parênteses?

Na notação comum, 3 + 4 * 2 precisa de uma regra de precedência ou de parênteses para indicar qual operação vem primeiro. Na notação polonesa inversa, um operador sempre se aplica aos dois valores imediatamente anteriores, então a ordem dos tokens diz tudo: 3 4 2 * + é 11 e 3 4 + 2 * é 14. É por isso que uma única pilha consegue avaliá-la sem precisar olhar adiante.

Como fazer uma divisão com truncamento em direção a zero em Python?

Use int(a / b). O operador // arredonda para baixo, então -7 // 2 é -4, enquanto int(-7 / 2) é -3. A divisão de ponto flutuante é suficientemente exata aqui porque os valores cabem em 32 bits. Para inteiros arbitrariamente grandes, divida os valores absolutos usando // e coloque o sinal de volta depois.

Como você transforma uma expressão comum em notação polonesa reversa?

O algoritmo shunting-yard faz isso em uma única passagem, usando uma pilha de operadores. Os números vão direto para a saída. Antes de um operador ser colocado na pilha, todos os operadores nela com precedência maior ou igual são movidos para a saída; um parêntese de abertura é colocado na pilha, e um parêntese de fechamento move os operadores para a saída até encontrar seu correspondente. No final, os operadores restantes vão para a saída.

Python

def evalRPN(tokens):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado