Avalua Expressió General

En aquest exercici considerarem arbres generals que representen
expressions sobre els operadors +, *, i -, amb operands enters. Per
exemple, el següent arbre

    +
    |-- *
    |   |-- 1
    |   |-- 2
    |   '-- 3
    |-- +
    |   |-- -
    |   |   '-- 5
    |   |-- 1
    |   '-- 6
    '-- 2

representa l’expressió (1 ⋅ 2 ⋅ 3) + (−5 + 1 + 6) + 2. Els nodes
d’aquest arbre poden ser enters o operadors. Quan són operadors, els
fills del node són els operands. Quan són operands, no tenen fills.

L’operador ’-’ és la resta, i té dues interpretacions, en funció del
nombre d’operands. Si té un sol operand, és un canvi de signe. Per
exemple, l’arbre:

    -
    '-- 5

és l’expressió −5. Si té més d’un operand, es comporta com una resta de
la forma (n₁ − n₂ − ⋯ − n_(k)), és a dir, que el primer operand es pren
amb el seu valor, i els següents operands es resten del primer. Per
exemple, l’arbre:

    -
    |-- 10
    |-- 2
    |-- 5
    '-- 1

és l’expressió (10 − 2 − 5 − 1) que s’avalua a 2.

Implementeu, doncs, la funció següent:

    /**
     * @brief Avalua un arbre general no buit que representa una expressió.
     *
     * @pre L'arbre és no buit i l'expressió és correcta.
     *
     * @param t Arbre que representa l'expressió.
     * @return Resultat de l'avaluació de l'expressió.
     */
    int eval_expression(Tree<string> t);

Observació

Els fitxers públics (icona del gatet) contenen:

  ------------ ----------------------------------------------------
  tree.hh      la classe Tree<T>
  tree-io.hh   l’entrada/sortida de Tree<T>
  utils.hh     utilitats per tractar els nodes de l’arbre
  main.cc      el programa principal, amb la entrada/sortida feta
  Makefile     per compilar amb make
  .vscode      carpeta per compilar i debuggar amb VSCode
  ------------ ----------------------------------------------------

El mòdul util defineix les funcions is_number i string_to_int, per
simplificar la discriminació entre operands i valors i per fer la
conversió dels operands de strings a enters.

Cal implementar eval_expression en un fitxer .cc nou, compilar, i
finalment enviar només el fitxer amb la funció.

Entrada

(D’això s’encarrega el programa principal). L’entrada és una seqüència
d’arbres generals en format visual.

Sortida

(D’això també s’encarrega el programa principal). La sortida són els
strings resultants de cridar la funció eval_expression, un resultat per
línia.

Informació del problema

Autoria: Mª Lluïsa Bonet i Pau Fernández

Generació: 2026-01-25T13:16:34.422Z

© Jutge.org, 2006–2026.
https://jutge.org
