Problema número 349

Jan el olvidado

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Calculadora HP 48G, que usa la notación polaca inversa

El problema de tener un nombre extraño es que el mundo buscará la forma de no tener que recordarlo incluso aunque hagas algo importante en la vida. Es lo que le ocurrió al polaco Jan Łukasiewicz, creador de lo que se llamó notación polaca (o notación prefija) por motivos bastante obvios. Consiste en una forma de escribir expresiones (aritméticas, lógicas o algebraicas) en la que se colocan los operadores antes que los operandos. Así, por ejemplo, lo que en la notación tradicional (infija) escribiríamos como 3 + 4, Jan decidió escribirlo como + 3 4.

Lejos de ser una decisión caprichosa, la principal ventaja de la notación polaca es que no requiere paréntesis para escribir cualquier expresión sin ambigüedad. Esta ventaja es lo suficientemente grande como para que la empresa HP decidiera utilizar una variante, la notación polaca inversa*, en sus clásicas calculadoras.

Notación infijaNotación polaca
3 + 4+ 3 4
3 − (4 × 5)− 3 × 4 5
(3 + 4) × 5× + 3 4 5
(3 − 4) ÷ (5 + 2)÷ − 3 4 + 5 2

Entrada

El programa leerá, de la entrada estándar, un número indicando la cantidad de casos de prueba que tendrá que procesar. Cada uno, en una línea, contendrá una expresión en notación polaca. Por simplicidad, los números tendrán únicamente un dígito. Los operadores válidos serán suma (+), resta (-), multiplicación (*) y división (/). El primer operando se proporciona antes que el segundo, y la división será entera.

Salida

Para cada caso de prueba el programa deberá escribir, en una línea independiente, el valor de la expresión. Se garantiza que tanto los resultados parciales como los finales serán menores que 231 en valor absoluto, y nunca habrá divisiones por 0.

Entrada de ejemplo

4
+ 3 4
- 3 * 4 5
* + 3 4 5
/ - 3 4 + 5 2

Salida de ejemplo

7
-17
35
0
1En la notación polaca inversa (también llamada notación postfija) el operador se escribe detrás de los operandos. El ejemplo del enunciado quedaría por tanto 3 4 +.