Az S. 164. feladat (2022. október)

S. 164. A fordítóprogramok nagyon alacsony szinten átrendezhetik a forrásprogramban kiszámítandó kifejezésben az elvégzendő műveletek sorrendjét azért, hogy időt vagy memóriát spóroljanak. Ez sokat javíthat egy programon, de nem változtathatja meg annak jelentését. Ebben a feladatban egy egyszerű számítás memóriaigényét próbáljuk csökkenteni.

Adott egy csak változókat, valamint összeadás és szorzás műveleteket tartalmazó kifejezés. Az egyszerűség kedvéért fordított lengyel jelölést használunk. Például az \(\displaystyle (a+b)*c\) kifejezés lengyel formában \(\displaystyle ab+c*{}\) lesz. Ennek előnye, hogy a számítógép ezt balról jobbra haladva egyszerűen végre tudja hajtani. Kezdetben az összes változó értéke bent van a memóriában, mindegyik egy egységnyi tárhelyet foglal el. Egy matematikai művelet végrehajtása után az eredmény egy új (egységnyi) memóriaterületre kerül. Az előző példában \(\displaystyle x=a+b\), \(\displaystyle y=x*c\). A program így 5 egységnyi memóriát használ, kezdetben \(\displaystyle a\), \(\displaystyle b\) és \(\displaystyle c\) értékének, majd \(\displaystyle x\) és \(\displaystyle y\) tárolására.

A kifejezés kiértékelése javítható, ha a később már nem használt (egységnyi) memóriaterületeket minden lehetséges alkalommal felülírjuk. A példa egy lehetséges végrehajtása ezzel a javítással: \(\displaystyle a=a+b\), \(\displaystyle b=a*c\). A program így 3 egységnyi memóriát használ a kezdeti változók miatt. (Nem számít, hogy az eredmény végül melyik változóba kerül.)

Készítsünk programot, amely egy lengyelformában adott kifejezés esetén megadja, hogy hány egységnyi tárhely szükséges a kifejezés kiértékeléséhez az eredeti és az optimalizált módszer felhasználásával.

A bemenet első és egyetlen sora egy számítást tartalmaz a fordított lengyel jelölés szerint. Ennek minden karaktere az angol abc egy kisbetűje, illetve a ,,+'' és ,,*'' karakter lehet.

A kimenet első sorába a számolás optimalizáció nélküli, a második sorába az optimalizáció utáni memóriaigényét kell írni.

Minta:

Időlimit: 0,5 mp.

Értékelés: a pontok 20%-a kapható, ha a megoldás a kimenet első sorát helyesen határozza meg.

Beküldendő egy s164.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2022. november 15-én LEJÁRT.

Statisztika:

4 dolgozat érkezett.
9 pontot kapott:	Horváth Milán.
2 pontot kapott:	3 versenyző.

A KöMaL 2022. októberi informatika feladatai