Wstęp do programowania w C++

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.