Si consideri la seguente rappresentazione di un albero binario:
<tree> ::= _ | <value><tree><tree>
dove
'_' rappresenta l'albero vuoto e <value> e' un carattere.
Scrivere un
programma che a partire da una rappresentazione di questo tipo costruisca il corrispondente
albero binario e lo visualizzi secondo la seguente rappresentazione:
<tree> ::= _ | <value>(<tree>,<tree>)
Esempio.
Si
consideri la seguente stringa:
ab__c_de___
Questa e' la rappresentazione
di un albero con radice 'a'.
'a' ha due figli: 'b' figlio sinistro e 'c' figlio
destro.
'b' non ha figli.
'c' non ha figlio sinistro ed ha 'd' come figlio
destro.
'd' ha 'e' come figlio sinistro e non ha figlio destro.
'e' non
ha figli.
A partire da questa
rappresentazione il programma deve visualizzare:
a(b(_,_),c(_,d(e(_,_),_)))
Esercizio 2
Si scriva un programma
che implementi le funzionalita' di una calcolatrice RPN (reverse polish notation).
In
una calcolatrice RPN, ogni volta che viene digitato un numero, questo viene inserito
in uno stack. Le operazioni (in questo caso somma, sottrazione, moltiplicazione
e addizione) operano prendendo i valori dello stack e inserendo nello stack il
risultato.
Il programma deve leggere numeri e operatori da linea di comando
e visualizzare all'uscita il valore contenuto nella testa dello stack.
Esempio.
Si
considerino i seguenti parametri in linea di comando:
1 2 3 4 + "*" 5 + -
Il
programma visualizzara':
18.0
Note.
E'
legittimo assumere che lo stack possa contenere un numero limitato di elementi,
per esempio 10.