POLSKI SPOJ

Wersja uproszczona (testy od 0pkt. do 9pkt.)

Należy obliczyć wartość podanego na wejściu wyrażenia arytmetycznego złożonego z liczb całkowitych, operatorów +, -, *, / oraz nawiasów. Formalnie, gramatyka pliku wejściowego input zadana jest w postaci:

< input >::==< rhs >\n
< rhs >::=< wyrażenie >
< rhs >::=< wyrażenie >[+-*/]< wyrażenie >
< wyrażenie >::=< liczba >
< wyrażenie >::=(< wyrażenie >[+-*/]< wyrażenie >)
< liczba >::=0
< liczba >::=[1-9][0-9]*
< liczba >::=-[1-9][0-9]*

Znaki występujące w pliku wejściowym wyróżniono na czerwono. Zapis wykorzystuje elementy składni wyrażeń regularnych.

Operatory arytmetyczne zdefiniowane są w sposób standardowy. Dzielenie należy rozumieć jako operację całkowitoliczbową z zaokrągleniem w dół i można założyć, że oba jego operandy podane w pliku wejściowym zawsze będą dodatnie. Plik wejściowy kończy się zaraz po pierwszym znaku nowej linii, a jego długość nie przekracza 50kB. W przypadku zastosowania się do porządku obliczania wyniku narzuconego w naturalny sposób przez nawiasy, wszystkie liczby występujące w obliczeniach są nie dłuższe niż 1000 cyfr dziesiętnych. Ograniczenie obliczeń do 18 cyfr dziesiętnych pozwala uzyskać 6pkt. na 9pkt. możliwych.

Przykłady

Przykład 1

Wejście:
=(11111*1111)*(-11111+0)

Wyjście:
-137157750631

Przykład 2

Wejście:
=((2*(((21/4)/3)*2))+22222)

Wyjście:
22226

Przykład 3

Wejście:
=(((99*999)*(9999*99999))*((99999*9999)*(999*99)))/(-1111+11111)

Wyjście:
977925602919947809416518

Wskazówka implementacyjna

Szkic algorytmu konwertującego podawany na wejściu ciąg znaków, opisany gramatyką wyrażenie, do postaci Odwrotnej Notacji Polskiej (ONP), może wyglądać następująco:

global lista poleceń ONP = pusta lista;

procedure ParsujWyrażenie()
begin
   wczytaj znak z wejścia
   if znak is '[0..9,-]':
      dokończ wczytywanie liczby z wejścia
      dodaj liczbę do listy
   if znak is '(':
      ParsujWyrażenie()
      wczytaj operator z wejścia
      ParsujWyrażenie()
      dodaj operator do listy
      wczytaj nawias zamykający z wejścia
end

Wersja rozszerzona (testy od 9pkt. do 15pkt.)

Należy napisać interpreter podawanych na wejściu skryptów bardzo prostego języka funkcyjnego. Skrypt złożony jest z ciągu linii definiujących wartości kolejnych funkcji, a w ostatniej linii następuje żądanie wypisania wyniku poprzedzone znakiem równości. Każda funkcja przyjmuje dokładnie jeden argument.

< input >::=< lhs >=< rhs >\n< input >
< input >::==< rhs >\n
< lhs >::=< funkcja >(< argument >)
< rhs >::=< wyrażenie >
< rhs >::=< wyrażenie >[+-*/]< wyrażenie >
< wyrażenie >::=< liczba >
< wyrażenie >::=< argument >
< wyrażenie >::=< funkcja >(< rhs >)
< wyrażenie >::=(< wyrażenie >[+-*/]< wyrażenie >)
< funkcja >::=[A-Z,_]+
< argument >::=[a-z]
< argument >::=< liczba >
< liczba >::=0
< liczba >::=[1-9][0-9]*
< liczba >::=-[1-9][0-9]*

Definicja funkcji może wystąpić co najwyżej raz w wersji ogólnej (argumentem w lhs jest mała literka alfabetu), oraz dowolnie wiele razy w wersji uszczegółowionej (dla konkretnie ustalonej wartości argumentu). Przy wywołaniu funkcji z argumentem należy zastosować wersję zdefiniowaną dla żądanej wartości argumentu, a w przypadku jej braku - wersję ogólną. Kolejność wszystkich linii w pliku oprócz ostatniej jest zupełnie nieistotna.

Pliki wejściowe spełniają takie same ograniczenia, jak w wersji uproszczonej zadania. Długość nazwy funkcji nie przekracza 20 znaków. Liczba różnych definicji wszystkich funkcji (łącznie) nie przekracza 20. Wiadomo, że przy wyliczaniu wartości wyrażenia nie wystąpią wywołania nieistniejących funkcji, zapętlenia (tj. wywołania rekurencyjne tej samej funkcji z tym samym argumentem, np. F(3)=3+(2*F(3))), itp. Można przyjąć, że przy naturalnym porządku obliczeń każda funkcja będzie wywołana dla co najwyżej 1000 różnych wartości argumentu (ale może być wywoływana dowolnie wiele razy...).

Przykłady

Przykład 1

Wejście:
IDEM(0)=0
IDEM(n)=IDEM(n-1)+1
=IDEM(333)

Wyjście:
333

Przykład 2

Wejście:
FIB(1)=1
FIB(2)=1
FIB(n)=FIB(n-1)+FIB(n-2)
=FIB(40)

Wyjście:
102334155

Przykład 3

Wejście:
POW_TEN(n)=SQUARE(POW_TEN(n/2))*POW_TEN(MOD_TWO(n))
POW_TEN(0)=1
POW_TEN(1)=10*POW_TEN(0)
SQUARE(x)=x*x
MOD_TWO(a)=a-(2*(a/2))
=POW_TEN(22)

Wyjście:
10000000000000000000000