Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_05_16 - Stos i arytmetyka

W tym zadaniu zajmiemy się bardzo ciekawym sposobem wykonującym obliczenia arytmetyczne bez użycia nawiasów i wykorzystując strukturę danych jaką jest stos.

Zaczniemy od przykładu. Wyznaczmy wynik działania

(3+4)*(5+6) = 77.

W klasycznym zapisie wykorzystaliśmy nawiasy. W notacji, którą tu przedstawię, podane wyrażenie może wyglądać następująco:

3 4 + 5 6 + * = 77

A oto algorytm:

  1. Powtarzaj dopóki są dane do wczytania
    1. Jeśli wczytany obiekt jest liczbą, to wrzuć ją na stos
    2. Jeśli wczytany obiekt jest operatorem, to
      1. Zdejmij pierwszą liczbę ze stosu i zapisz ją pod zmienną x
      2. Zdejmij drugą liczbę ze stosu i zapisz ją pod zmienną y
      3. Wykonaj działanie: y operator x i wynik wrzuć na stos
  2. Wypisz wartość, która została na stosie

Na wejściu pojawi się ciąg liczb i operatorów zapisanych poprawnie w omawianej notacji. Twoim zadaniem jest wyliczenie wartości wyrażenia, wypisanie wyniku oraz nazwę algorytmu złożonego z trzech dużych liter.

Wejście

W pierwszym wierszu jedna liczba q określająca liczbę elementów wyrażenia zapisanego w pewnej notacji (nie więcej niż 100).

Każde z q wierszy ma postać. Najpierw jedna liczba należąca do zbioru {0, 1}. Jeśli pojawi się 1, to następnie pojawi się niewielka całkowita liczba, którą należy wrzucić na stos, w przeciwnym razie pojawi się operator należący do zbioru {+, -, *, /}. Dane są tak dobrane, aby wynik był zawsze całkowity.

Wyjście

Wyjście składa się z dwóch wierszy. W pierwszym wierszu wartość wyrażenia, natomiast w drugim trzyliterowa nazwa omawianego algorytmu zapisana z dużych liter w języku polskim.

Przykład

Wejście:
7
1 3
1 4
0 +
1 5
1 6
0 +
0 *

Wyjście:
77
***

Zamiast gwiazdek należy wpisać nazwę algorytmu.

Dodane przez:Marcin Kasprowicz
Data dodania:2016-03-02
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.