İfadələr
Aritmetik ifadələr adətən iki operand arasında operatorlarla yazılır (bu yazılış infiks notasiya adlanır). Məsələn, (x + y) * (z - w) infiks notasiya ilə yazılmış bir aritmetik ifadədir. Lakin ifadənin dəyərini hesablayan proqram yazmaq daha asandır, əgər ifadə postfiks notasiya ilə verilmişdirsə (bu notasiya tərs polyak notasiya kimi də tanınır). Postfiks notasiya ilə operator öz iki operandından sonra yazılır, hansı ki, özləri də ifadələr ola bilər. Məsələn, x y + z w - * yuxarıda verilmiş ifadənin postfiks notasiya ilə yazılışıdır. Belə yazılış üçün mötərizələrə ehtiyac yoxdur.
Postfiks notasiya ilə verilmiş ifadənin hesablanması üçün stek ilə işləyən bir alqoritm istifadə olunur. Stek iki əməliyyatı dəstəkləyən bir məlumat strukturu:
push: ədəd stekin üstünə qoyulur.
pop: ədəd stekin üstündən çıxarılır.
Hesablama zamanı ifadə soldan sağa işlənir. Əgər ədəd gəlirsə, onu stekə qoyuruq. Əgər operator gəlirsə, stekdən iki ədəd çıxarırıq, operatoru onlara tətbiq edirik və nəticəni yenidən stekə qoyuruq. Aşağıdakı psevdokod operator O-nu işləyir:
a := pop();
b := pop();
push(b O a);
İfadənin nəticəsi stekdə qalan tək ədəd olacaq.
Tutaq ki, stek əvəzinə növbə istifadə edirik. Növbə də push və pop əməliyyatlarına malikdir, lakin onların mənası bir az fərqlidir:
push: ədəd növbənin sonuna əlavə edilir.
pop: növbənin başlanğıcından ədəd çıxarılır.
Siz ifadəni elə yenidən yaza bilərsinizmi ki, növbə istifadə edən alqoritm onun hesablanmasında stek ilə hesablanan alqoritm ilə eyni nəticəni versin?
Giriş verilənləri
Birinci sətir t (t ≤ 200) ədədini ehtiva edir. Növbəti t sətirdən hər biri postfiks yazılışda bir ifadə ehtiva edir. Aritmetik əməliyyatlar böyük hərflərlə, ədədlər kiçik hərflərlə təqdim olunur. Hər ifadənin uzunluğu 10000 simvoldan azdır.
Çıxış verilənləri
Hər giriş sətiri üçün ifadəni elə çıxarın ki, növbə istifadə edən alqoritm ilə stek istifadə edən alqoritm eyni nəticəni versin. Nəticənin dəqiq müəyyən olunması üçün, verilmiş operatorların assosiativ və ya kommutativ olmadığını qəbul edin.