Expressió. Representació infixa amb el màxim nombre de parèntesis X21901

Statement

html

Donada la classe expressio que permet guardar expressions matemàtiques en un arbre binari usant memòria dinàmica, cal implementar el mètode

string llista_tokens_parentitzada() const;

que retorna un string amb la representació infixa de l’expressió amb tots els parèntesis possibles, excepte quan són operands (constants o variables) que mai fan falta. Els operadors i operands es guarden en l’string token de cada node. Els operadors unaris (+ - sqrt log exp) tenen el fill dret buit.

Cal enviar a jutge.org la següent especificació de la classe expressio i la implementació del mètode dins del mateix fitxer.

#include <cstdlib> #include <iostream> using namespace std; typedef unsigned int nat; class expressio { // Guarda una expressio en un arbre binari. // Els operadors i operands es guarden en l’string token de cada node. // Els operadors unaris (+ - sqrt log exp) tenen el fill dret buit. public: expressio(): _arrel(nullptr) {}; // Pre: cert // Post: el resultat és un arbre sense cap element expressio(expressio &ae, const string &x, expressio &ad); // Pre: cert // Post: el resultat és un arbre amb un element i dos subarbres // Les tres grans expressio(const expressio &a); ~expressio(); expressio& operator=(const expressio& a); // operador << d’escriptura friend std::ostream& operator<<(std::ostream&, const expressio &a); // operador >> de lectura friend std::istream& operator>>(std::istream&, expressio &a); string llista_tokens_parentitzada() const; // Pre: Cert // Post: Retorna string amb la representació infixa de l’expressió amb tots els parèntesis possibles, // excepte quan són operands (constants o variables) que mai fan falta. private: struct node { node* f_esq; node* f_dret; string token; }; node* _arrel; static node* copia_nodes(node* m); static void esborra_nodes(node* m); static void print_nodes(node* m, ostream &os, string d1); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació del mètode llista_tokens_parentitzada i privats addicionals

Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe expressio i un programa principal que llegeix una expressió i desprès crida el mètode llista_tokens_parentitzada.

Entrada

L’entrada consisteix en la descripció de l’arbre de l’expressió (el seu recorregut en preordre, en el qual inclou les fulles marcades amb l’string "#"). Per exemple, l’arbre

[*]
 \__[pt]
 |   \__#
 |   \__#
 \__[2]
     \__#
     \__#

es descriuria amb

* 2 # # pt # #

Sortida

El contingut de l’arbre binari seguit per l’string que retorna el mètode llista_tokens_parentitzada.

Observació

Només cal enviar la classe requerida i la implementació del mètode llista_tokens_parentitzada. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Public test cases

Input

34 # #

Output

[34]
 \__#
 \__#

34

Input

x # #

Output

[x]
 \__#
 \__#

x

Input

log 3 # # #

Output

[log]
 \__#
 \__[3]
     \__#
     \__#

log(3)

Input

* 2 # # pt # #

Output

[*]
 \__[pt]
 |   \__#
 |   \__#
 \__[2]
     \__#
     \__#

(2*pt)

Input

+ 2 # # * 3 # # y # #

Output

[+]
 \__[*]
 |   \__[y]
 |   |   \__#
 |   |   \__#
 |   \__[3]
 |       \__#
 |       \__#
 \__[2]
     \__#
     \__#

(2+(3*y))

Input

+ sqrt 2 # # # * 3 # # y # #

Output

[+]
 \__[*]
 |   \__[y]
 |   |   \__#
 |   |   \__#
 |   \__[3]
 |       \__#
 |       \__#
 \__[sqrt]
     \__#
     \__[2]
         \__#
         \__#

(sqrt(2)+(3*y))

Input

+ sqrt 2 # # # * - 3 # # # y # #

Output

[+]
 \__[*]
 |   \__[y]
 |   |   \__#
 |   |   \__#
 |   \__[-]
 |       \__#
 |       \__[3]
 |           \__#
 |           \__#
 \__[sqrt]
     \__#
     \__[2]
         \__#
         \__#

(sqrt(2)+(-(3)*y))

Input

log * - z # # # ^ x # # / + sqrt y # # # 7 # # 3 # # #

Output

[log]
 \__#
 \__[*]
     \__[^]
     |   \__[/]
     |   |   \__[3]
     |   |   |   \__#
     |   |   |   \__#
     |   |   \__[+]
     |   |       \__[7]
     |   |       |   \__#
     |   |       |   \__#
     |   |       \__[sqrt]
     |   |           \__#
     |   |           \__[y]
     |   |               \__#
     |   |               \__#
     |   \__[x]
     |       \__#
     |       \__#
     \__[-]
         \__#
         \__[z]
             \__#
             \__#

log((-(z)*(x^((sqrt(y)+7)/3))))

Information

Author: Jordi Esteve
Language: Catalan
Official solutions: C++
User solutions: C++