Obrnuta poljska notacija

Opis zadatka:

Za aritmetičke izraze kao što su 2+3, 2+3*4, (2+3)*4, itd. sa kojima se tipično susrećemo kako u matematici tako i u programiranju, kažemo da su zapisani u infiksnoj formi, s obzirom da se operator nalazi između operanada. Najveća mana ovakvog zapisa leži u činjenici da je neophodno uspostaviti konvencije o prioritetu pojedinih operatora (npr. konvenciju da množenje ima veći prioritet u odnosu na sabiranje), i eventualno koristiti zagrade za promjenu prioriteta.

U računarstvu je od velikog značaja jedan posve drugačiji zapis aritmetičkih izraza, poznat pod imenom postfiksna ili obrnuta poljska notacija, u kojem se operatori navode nakon operanada (naziv obrnuta poljska notacija dat je u čast poljskog matematičara Jana Lukasiewitza, koji je predložio upravo obrnuti princip - da se operatori zapisuju ispred operanada). Na primjer, prethodna tri izraza zapisana u infiksnoj notaciji, u obrnutoj poljskoj notaciji zapisuju se ovako:

2 3 +
2 3 4 * +
2 3 + 4 *

Izračunavanje izraza u obrnutoj poljskoj notaciji izvodi se tako da se svaki operand na koji se naiđe dodaje na kraj liste (koja je na početku prazna), dok se prilikom nailaska na binarni operator posljednja dva elementa iz liste brišu i zamjenjuju rezultatom operacije (sličan princip može se primijeniti i na n-arne operatore). Broj koji na kraju izračunavanja ostane u listi predstavlja rezultat izračunavanja (taj broj mora biti jedinstven ako je izraz bio ispravan). Uzmimo na primjer, slijedeći izraz zapisan u obrnutoj poljskoj notaciji:

3 5 6 4 - * 6 + * 2 /

Izračunavanje ovog izraza teklo bi ovako:

3
3 5
3 5 6
3 5 6 4
3 5 2               6 i 4 su zamijenjeni sa 6-4=2
3 10                5 i 2 su zamijenjeni sa 5*2=10
3 10 6
3 16                10 i 6 su zamijenjeni sa 10+6=16
48                  3 i 16 su zamijenjeni sa 3*16=48
48 2
24                  48 i 2 su zamijenjeni sa 48/2=24

Dakle, rezultat izračunavanja je 24. Jedna od glavnih prednosti obrnute poljske notacije leži u činjenici da nije potrebno voditi računa o prioritetu operacija, kao i da je svaki izraz moguće zapisati bez upotrebe zagrada. Na primjer, izraz koji bi se u infiksnom obliku zapisao kao

((3 + 5) / (7 - 2) + 4 / (8 - 5)) / (3 + 5 * (4 / (7 - 2)))

u obrnutoj poljskoj notaciji zapisuje se kao

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

Stoga, kompajleri većine programskih jezika interno prevode sve aritmetičke izraze u obrnutu poljsku notaciju prije bilo kakve dalje obrade. Vaš zadatak je da napravite program koji aritmetičke izraze u infiksnom obliku koji se sastoje od jednoslovnih promjenljivih (a-z), četiri računske operacije (+, -, * i /), i eventualno zagrada, pretvori u obrnutu poljsku notaciju.

Izvršni program treba snimiti pod imenom RPN.EXE

Ulazna datoteka:

U prvom i jedinom redu ulazne tekstualne datoteke RPN.IN nalazi se niz znakova koji predstavlja aritmetički izraz u infiksnoj notaciji koji treba pretvoriti u postfiksnu odnosno obrnutu poljsku notaciju. Ispravan aritmetički izraz smije sadržavati samo jednoslovne promjenljive pisame malim slovima (od "a" do "z"), binarne operatore "+", "-", "*" i "/" kao i male zagrade "(" i ")" za promjenu prioriteta operacija. Ispravan aritmetički izraz neće sadržavati nikakve razmake.

Izlazna datoteka:

Ukoliko ulazna datoteka sadrži ispravan aritmetički izraz u infiksnoj notaciji, tada u prvi i jedini red izlazne tekstualne datoteke RPN.OUT treba upisati niz znakova koji predstavlja aritmetički izraz u obrnutoj poljskoj notaciji. Ovaj izraz sastoji se od niza znakova koji smiju sadržavati samo mala slova (od "a" do "z") i binarne operatore "+", "-", "*" i "/". Nikakvi razmaci u izrazu nisu dozvoljeni. Ukoliko ulazna datoteka ne sadrži ispravan aritmetički izraz, u izlaznu datoteku treba samo ispisati tekst

NEISPRAVAN IZRAZ

Vremensko ograničenje:

Za svaki testni primjer program treba da ponudi rješenje za najviše 10 sekundi.

Primjeri:

RPN.IN
x+y+z
RPN.OUT
xy+z+
RPN.IN
x+(y+z)
RPN.OUT
xyz++
RPN.IN
x+y*z
RPN.OUT
xyz*+
RPN.IN
(x+y)*z
RPN.OUT
xy+z*
RPN.IN
x*(y+z
RPN.OUT
NEISPRAVAN IZRAZ
RPN.IN
a+b/c+d
RPN.OUT
abc/+d+
RPN.IN
(a+b)/(c+d)
RPN.OUT
ab+cd+/
RPN.IN
x*(y+z*(a+b*(c-d))/e)
RPN.OUT
xyzabcd-*+*e/+*

[Testni podaci] [Rješenje (Pascal)] [Rješenje (C++)]