Infixdən Prefixə
Jaap laboratoriya tapşırığı üçün bir həll yazdı. Tapşırıq olduqca sadə idi: arifmetik ifadəni infiks notasiya ilə Polşa (prefiks) notasiya ifadəsinə çevirmək. İnfix notasiya operatorları operandlar arasında yazılır (məsələn, 12 + 5), prefiks notasiya isə operatorları operandların soluna yerləşdirir (məsələn, + 12 5).
Jaapın çevirməli olduğu ifadənin sintaksisi belə idi:
Expression ::= Number
| '(' Expression Op Expression ')'
| '(' '-' Expression ')'
Op ::= '+' | '-'
Number ::= Digit j Number Digit
Digit ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Əgər Number bir neçə rəqəmdən ibarətdirsə, '0' ilə başlamayacaq.
Number ən çox 9 rəqəmdən ibarət olacaq.
Bu nöqtədə etiraf etməliyik ki, tapşırıq çox yaxşı müəyyən edilməmişdi. Daha dəqiq desək, nəticə ifadəsinin sintaksisi verilməmişdi. Beləliklə, Jaap özü bəzi qərarlar verməli oldu — və o, yanlış qərarlar verdi.
Bu onun ilk səhvi idi: o, prefiks notasiya ilə boşluqların artıq olduğunu düşündü. Bu, infiks notasiya üçün doğrudur, çünki iki rəqəm arasında həmişə bir operator olacaq. Lakin prefiks notasiya ilə rəqəmlər bir-birindən ayrılmalıdır. Prefiks notasiya ilə boşluqları buraxmaq, Jaapın etdiyi kimi, +1234 kimi ifadələrə səbəb olur ki, bu da üç fərqli şərhə malikdir. (Tapşırıq: üç fərqli sintaksis ağacını çəkin.)
Bu, Jaapın ikinci səhvi idi: o, prefiks notasiya ilə mötərizələrin artıq olduğunu düşündü. Prefiks notasiya mötərizələr olmadan yalnız operatorların arityası sabit olduqda qeyri-müəyyən deyil. Qeyri-müəyyənlik, məsələn, həm unar, həm də binar minusun mövcudluğunda baş verir. İfadə: –34, (- (- 3 4)) kimi oxuna bilər, 1 qiymətini alır, ya da (- (- 3) 4) kimi, -7 qiymətini alır, və hətta (- (- 34)) kimi, 34 qiymətini alır.
Biz sizdən Jaapın proqramını bərpa etməyi istəmirik. Biz sizdən onun çıxışının nə qədər qeyri-müəyyən olduğunu tapmağı istəyirik.
Giriş verilənləri
Hər bir test halı yalnız '+' və '-' simvollarını və '0' ilə '9' rəqəmlərini ehtiva edən uzunluğu ≤ 1000 olan boş olmayan bir sətirdən ibarətdir. Bu sətir Jaapın proqramının çıxışıdır.
Çıxış verilənləri
Hər bir test halı üçün, fərqli şərhlərlə giriş ifadəsindən əldə edilə biləcək ən kiçik və ən böyük dəyəri ehtiva edən bir sətir çap edin.