Evaluate Reverse Polish Notation
Você recebe uma expressão aritmética em notação polonesa reversa, como um array de tokens. Cada operador vem logo depois de seus dois operandos, então 3 4 + significa 3 + 4 e 3 4 + 2 * significa (3 + 4) * 2, sem parênteses. Cada token é um número inteiro ou um dos operadores +, -, * e /.
Retorne o valor da expressão. A divisão trunca em direção a zero: 7 / 2 é 3 e -7 / 2 é -3.
Função
- tokensstring-array
- os números e operadores da expressão, em ordem
- Retornainteger
- o valor da expressão
Restrições
1 ≤ tokens.length ≤ 104- Cada token é
+,-,*,/ou um número inteiro de-200a200, escrito em decimal, com um sinal de menos à esquerda quando for negativo. tokensé uma expressão válida em notação polonesa reversa.- Nenhuma divisão por zero ocorre, e todos os valores intermediários e finais são maiores que
-231e menores que231.
Exemplos
- Entrada
- tokens = ["8", "3", "-", "4", "*"]
- Saída
- 20
- Explicação
- O
-é aplicado a 8 e depois a 3, nessa ordem, então resulta em 5, não -5. Em seguida,*multiplica esse 5 por 4, resultando em 20.
- Entrada
- tokens = ["6", "2", "9", "3", "/", "-", "*"]
- Saída
- -6
- Explicação
- O
/usa os dois valores mais recentes: 9 dividido por 3 é 3. Em seguida,-calcula 2 menos 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, não -4, e 10 mais -3 é 7.
Para ir além
Você consegue reconstruir a expressão na notação comum, como (3 + 4) * 2, adicionando parênteses apenas onde eles alteram o significado?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Leia os tokens da esquerda para a direita. Quando encontrar um operador, a quais dois valores ele se aplica? Observe a ordem em que esses valores foram produzidos.
Um operador sempre se aplica aos dois valores mais recentes que ainda não foram usados por nenhum operador, e seu resultado se torna um novo valor para os operadores seguintes. “O mais recente ainda não usado” é exatamente o que uma pilha oferece.
Empilhe cada número. Ao encontrar um operador, retire primeiro o operando da direita e depois o da esquerda, combine-os nessa ordem e empilhe o resultado. Quando os tokens acabarem, a pilha conterá um valor: a resposta. Certifique-se de que a divisão trunque em direção a zero.
Solução
Cada operador se aplica aos dois valores imediatamente anteriores a ele, e qualquer um deles pode ser o resultado de um operador anterior. Assim, uma pilha de valores avalia a expressão em uma única passagem. Os pontos que exigem atenção são a ordem dos operandos em - e /, distinguir o operador - do número -7 e a divisão truncada.
Recolha o primeiro operador, repita
Correta, mas não termina nos maiores testes
Intuição
Encontre o operador mais à esquerda. Nenhum operador vem antes dele, então os dois tokens anteriores são números, seus operandos. Substitua esses três tokens pelo resultado. Os operadores que vêm depois dele veem esse valor no lugar que a parte ocupava, então a expressão mantém seu significado. Repita até restar um número.
A cada rodada, a busca recomeça do início. Com 5,000 números seguidos por 4,999 operadores, o primeiro operador fica aproximadamente na metade do caminho em cada rodada, então só as buscas leem cerca de 1.25 × 10^7 tokens.
Algoritmo
- Copie os tokens para uma lista que você possa alterar.
- Percorra a lista desde o início até o primeiro operador, na posição
k. - Aplique-o aos números nas posições
k-2(à esquerda) ek-1(à direita). - Substitua os três tokens nas posições
k-2,k-1ekpelo resultado. - Repita até restar um token e retorne-o como um 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
Mantenha os valores à esquerda do operador em uma pilha, em vez de lê-los novamente. Um número é colocado na pilha. Um operador desempilha dois valores, combina-os e empilha o resultado, onde ele aguarda o próximo operador como qualquer outro valor. A pilha sempre contém, em ordem, os valores das partes completas lidas até o momento, portanto um operador sempre é aplicado aos dois valores do topo. O valor do topo é o operando da direita, porque foi produzido por último.
Em 6 2 9 3 / - *, o / desempilha 3 e depois 9 e empilha 3, o - desempilha 3 e depois 2 e empilha -1, e o * empilha 6 × -1 = -6. Cada token é processado uma vez: tempo O(n) e espaço O(n).
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 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
- Trocar os operandos de posição. O primeiro valor removido é o operando da direita:
["3", "5", "-"]resulta em -2, e["2", "9", "/"]resulta em 0, não em 4. - Identificar operadores pelo primeiro caractere.
-7começa com um sinal de menos, mas é um número, então compare o token inteiro. - Arredondar para baixo em vez de truncar. O
//do Python, o/do Ruby, o%/%do R e omath.floordo Lua transformam-7 / 2em -4 e-1 / 3em -1. - Exibir
-0. Em JavaScript e Lua,0 * -5eMath.trunc(-1 / 3)resultam em zero negativo. Some 0 ao valor final.
Perguntas frequentes4
Qual é a complexidade de tempo de Evaluate Reverse Polish Notation?
A solução com pilha é executada em tempo O(n) para n tokens: cada número é empilhado uma vez, e cada operador realiza duas remoções e uma inserção. A pilha armazena até cerca de n/2 valores, então o espaço é O(n).
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 reversa, um operador sempre se aplica aos dois valores imediatamente anteriores a ele, então a ordem dos tokens determina o resultado: 3 4 2 * + é 11 e 3 4 + 2 * é 14.
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 é precisa o suficiente para valores de 32 bits. Para inteiros maiores, divida os valores absolutos usando // e recoloque o sinal.
Como transformar uma expressão comum em notação polonesa reversa?
O algoritmo shunting-yard faz isso em uma única passagem com uma pilha de operadores. Os números vão diretamente para a saída. Antes de empilhar um operador, mova para a saída todos os operadores empilhados de precedência maior ou igual. Um parêntese de fechamento move os operadores para fora até encontrar seu par de abertura. No final, os restantes vão para a saída.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def evalRPN(tokens):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumento
tokens = ["8", "3", "-", "4", "*"]
Saída Esperada
20