Pular para o conteúdo

Avaliar tokens em notação pós-fixa

Fácil#stack#expression-evaluation~15 min

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

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

Travou na ideia, e não no código? O básico de pilhas explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado