Programozás‎ > ‎Feladatok‎ > ‎

Fenyőfa zárójelezéssel

A Kísérleti Fanemesítő Intézet újfajta fenyőfákat nemesített ki. A fenyőfa törzséből tetszőleges számú ág leágazhat, lehet, hogy egyetlenegy sem. Az egyes ágak ugyanolyan hosszúak, de feleakkora tömegűek, mint a törzs, s a végükből újra tetszőleges számú ág ágazhat le, vagy egy sem. Ezek megint ugyanolyan hosszúak, mint amiből kinőttek, de feleakkora tömegűek. Egy fát zárójelekkel és F betűkkel írunk le a számítógép számára: F(első ág)(második ág) ... (n. ág) formában. A fá- nak törzse biztosan van.

Feladat

Készíts programot, amely meghatározza 
  1. a fa magasságát (a leghosszabb út hosszát a gyökértől valamelyik ág végéig); 
  2. a törzs tömegét (feltételezve, hogy a fa legkisebb (azaz a gyökértől legtávolabbi) ágai éppen egységnyi tömegűek); 
  3. a fa tömegét (az ágak össztömege)!

Bemenet

A standard bemenet egyetlen sorában a fát leíró szöveg szerepel. A bemenet hossza legfeljebb 100 000 karakter, és minden esetben egy # zárja.

Kimenet

A standard kimenet három sorába a a fa magasságát, a törzs tömegét, valamint a fa tömegét kell írni!

Példa

Bemenet  Kimenet
F#1
1
1
F(F)(F)#2
2
4
F(F)(F)(F)(F)#2
2
6
F(F(F)(F)(F))(F)#3
4
11

Tesztadatok

mester.inf.elte.hu: Haladó feladatok > Rekurzív adatszerkezetek > Fenyőfa zárójelezéssel
Két minta tesztadat: ffa-minta.zip

Címkék

A feladat forrása: mester.inf.elte.hu
Algoritmusok: rekurzív adatszerkezetek

megoldás