Avaluar expressions amb divisió (PRO2) X96833
INTRODUCCIÓ:
En aquest exercici considerarem arbres que representen expressions sobre els operadors binaris +,-,*,/, i sobre operands naturals. Per exemple, el següent arbre representa l’expressió 3+4/2-5.
-
|
---- ----
| |
+ 5
|
---- ----
| |
3 /
|
---- ----
| |
4 2
Alhora d’avaluar una divisió, interpretem la divisió entera que ens ofereix C++. Noteu que, en particular, (−5)/2=−2, contradient la definició que trobem habitualment en llibres de matemàtiques.
Noteu també que la divisió per 0 no està definida, i això ho haurem de tenir en compte en resoldre l’exercici.
EXERCICI:
Implementeu una funció que, donat un arbre binari d’strings que representa una expressió correcta sobre naturals i operadors binaris +,-,*,/, retorna la seva avaluació i un indicador de si s’ha produït un error de divisió per 0, tot mitjançant paràmetres per referència. Aquesta és la capcelera:
// Pre: t és un arbre no buit que representa una expressió correcta // sobre els naturals i els operadors binaris +,-,*,/. // Les operacions no produeixen errors d'overflow, // però poden produïr error de divisió per 0. // Post: Si l'avaluació de l'expressió representada per t no produeix errors de divisió per 0, // llavors 'result' val l'avaluació d'aquesta expressió i 'error' val 'false'. // En cas contrari, 'error' val 'true', i el valor de 'result' és irrellevant. void evaluate(BinTree<string> t, int &result, bool &error);
Aquí tenim un exemple de paràmetre d’entrada de la funció i els corresponents valors de sortida:
evaluate(/(+(1,2),-(5,2)), result, error) produces result=1, error=false
Fixeu-vos que l’enunciat d’aquest exercici ja ofereix uns fitxers que haureu d’utilitzar per a compilar: main.cc, BinTree.hh, evaluate.hh, utils.hh, utils.cc. Us falta crear el fitxer evaluate.cc amb els corresponents includes i implementar-hi la funció anterior. Valdrà la pena que utilitzeu algunes de les funcions oferides a utils.hh. Haureu de compilar main.cc, utils.cc i evaluate.cc combinadament. Només cal que pugeu evaluate.cc al jutge.
Entrada
La primera linia de l’entrada descriu el format en el que es descriuen els arbres, o bé INLINEFORMAT o bé VISUALFORMAT. Després venen un nombre arbitrari de casos. Cada cas consisteix en una descripció d’un arbre un arbre binari que representa una expressió. Fixeu-vos en que el programa que us oferim ja s’encarrega de llegir aquestes entrades. Només cal que implementeu la funció abans esmentada.
Sortida
Per a cada cas, la sortida conté la corresponent avaluació de l’arbre o bé una indicació de que s’ha produït un error de divisió per 0 durant el procès d’avaluar l’arbre. Fixeu-vos en que el programa que us oferim ja s’encarrega d’escriure aquesta sortida. Només cal que implementeu la funció abans esmentada.
Observació
La vostra funció i subfuncions que creeu han de treballar només amb arbres. Heu de trobar una solució RECURSIVA del problema.
Input
VISUALFORMAT
-
|
-------- --------
| |
+ -
| |
------- ------- ---- ----
| | | |
- * 1 8
| |
---- ---- ---- ----
| | | |
5 2 4 4
+
|
-------- --------
| |
/ -
| |
------- ------- ---- ----
| | | |
+ - 5 4
| |
---- ---- ---- ----
| | | |
6 8 6 6
5
-
|
-------- --------
| |
* /
| |
---- ---- ------- -------
| | | |
/ 2 * *
| | |
---- ---- ---- ---- ---- ----
| | | | | |
5 8 7 2 4 7
-
|
--------------- ---------------
| |
/ -
| |
------- ------- -------- --------
| | | |
* / / *
| | | |
---- ---- ---- ---- ---- ---- ------- -------
| | | | | | | |
5 * 3 * 2 2 * /
| | | |
---- ---- ---- ---- ---- ---- ---- ----
| | | | | | | |
5 3 2 7 6 2 8 8
+
|
---- ----
| |
8 *
|
--------------- ---------------
| |
+ /
| |
------- ------- ------- -------
| | | |
/ - + -
| | | |
---- ---- ---- ---- ---- ---- ---- ----
| | | | | | | |
5 4 4 3 5 2 5 5
/
|
---- ----
| |
8 *
|
--------------- ---------------
| |
/ *
| |
------- ------- ------- -------
| | | |
+ * - /
| | | |
---- ---- ---- ---- ---- ---- ---- ----
| | | | | | | |
3 4 3 5 4 6 3 1
-
|
---- ----
| |
* 3
|
---- ----
| |
- 3
|
---- ----
| |
5 7
-
|
------- -------
| |
/ /
| |
---- ---- ---- ----
| | | |
4 7 3 1
6
/
|
---- ----
| |
7 2
/
|
---- ----
| |
3 2
-
|
---- ----
| |
5 6
5
-
|
------- -------
| |
* +
| |
---- ---- ---- ----
| | | |
8 6 7 5
+
|
---- ----
| |
6 5
/
|
---- ----
| |
5 3
/
|
---- ----
| |
4 6
/
|
---------- ----------
| |
* /
| |
-------- -------- ---- ----
| | | |
* / 6 /
| | |
---- ---- ------- ------- ---- ----
| | | | | |
* 6 + - 7 5
| | |
---- ---- ---- ---- ---- ----
| | | | | |
3 7 2 1 2 5
2
Output
26 Division by 0 5 0 Division by 0 Division by 0 Division by 0 -9 -3 6 3 1 -1 5 36 11 1 0 -21 2
Input
INLINEFORMAT +(12,52) 44 +(65,19) 5 -(/(/(-(7,20),+(71,97)),+(/(75,29),-(87,64))),40) *(/(43,89),5) -(8,38) -(/(/(80,30),*(76,21)),-(22,*(38,94))) /(*(+(78,53),/(22,60)),-(*(43,20),+(98,42))) /(-(-(*(40,40),+(57,82)),/(100,+(66,63))),/(-(-(2,70),-(39,21)),-(*(84,47),-(31,75)))) +(37,-(+(73,/(60,90)),49)) -(*(-(67,51),36),+(10,+(54,23))) *(44,-(83,8)) -(35,*(96,39)) -(+(55,87),*(*(/(60,81),*(16,53)),99)) -(/(25,*(+(27,94),64)),44) /(59,-(/(57,-(92,33)),/(55,+(-(27,12),*(83,20))))) -(*(64,/(+(18,91),-(/(75,35),23))),-(7,+(-(54,83),-(*(42,93),/(83,10))))) +(-(/(*(8,9),-(43,66)),-(78,/(5,14))),*(/(47,92),41)) 7
Output
64 44 84 5 -40 0 -30 3550 0 Division by 0 61 489 3300 -3709 142 -44 Division by 0 3542 -81 7
- Author
- PRO2
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++