Avaliar tokens em notação pós-fixa
A missão
Problema
Uma calculadora de bolso guarda fórmulas em notação pós-fixa, em que cada operador vem depois dos seus dois operandos; assim, “3 4 +” significa 3 + 4 e nenhum parêntese é necessário. Dada a fórmula como uma lista de tokens, cada um sendo um inteiro ou um dos símbolos +, -, * e /, retorne o valor dela. A divisão trunca em direção a zero, então 7 / -2 é -3. A fórmula é sempre válida, tem entre 1 e 10.000 tokens, nunca divide por zero, e todo valor intermediário cabe em um inteiro de 32 bits com sinal.
Exemplos
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Por quê: (2 + 1) * 3
Input: tokens = ["4", "13", "5", "/", "+"]
Output: 6
Por quê: 4 + (13 / 5), e 13 / 5 trunca para 2
Input: tokens = ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Por quê: números negativos como -11 são operandos, não operadores
Dicas
0 / 3
Quando chega um operador, os operandos dele são os dois valores mais recentes que ainda não foram usados.
Empilhe (push) os números em uma pilha. Em um operador, desempilhe (pop) primeiro o operando direito e depois o esquerdo, aplique o operador e empilhe o resultado de volta.
A ordem importa para - e /. O // do Python arredonda em direção a menos infinito, então divida os valores absolutos e recoloque o sinal você mesmo para truncar em direção a zero.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- 1 ≤ tokens.length ≤ 10⁴
- the formula is valid and never divides by zero
- values fit in a 32-bit signed integer
- division truncates toward zero
Solução
Na notação pós-fixa, um operador sempre se aplica aos dois valores mais recentes ainda não usados, que é exatamente o que o topo de uma pilha guarda. Os números são empilhados; um operador desempilha o operando direito, depois o esquerdo, e empilha o valor combinado, então no final o único valor que sobra é a resposta. A única armadilha é a divisão: a divisão inteira do Python arredonda -7 // 2 para baixo, para -4, então o quociente é calculado sobre os valores absolutos e o sinal é restaurado depois, o que trunca em direção a zero. Um token só é operador se for exatamente um dos quatro símbolos, então “-11” é lido como número. Tempo e espaço são ambos O(n).
def eval_postfix(tokens):
stack = []
for tok in tokens:
if tok not in ("+", "-", "*", "/"):
stack.append(int(tok))
continue
right, left = stack.pop(), stack.pop() # right operand is on top
if tok == "+":
stack.append(left + right)
elif tok == "-":
stack.append(left - right)
elif tok == "*":
stack.append(left * right)
else:
q = abs(left) // abs(right) # truncate toward zero
stack.append(q if (left < 0) == (right < 0) else -q)
return stack[0]
print(eval_postfix(["2", "1", "+", "3", "*"])) # -> 9
print(eval_postfix(["4", "13", "5", "/", "+"])) # -> 6
print(eval_postfix(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) # -> 22Travou na ideia, e não no código? O básico de pilhas explica isso.