Árboles de expresión usando clases en C++ con implementación

Prerrequisito: Árbol de expresión

El árbol de expresión es un árbol binario en el que cada Node interno corresponde al operador y cada Node hoja corresponde al operando, por lo que, por ejemplo, el árbol de expresión para 3 + ((5+9)*2) sería:

Expression Tree

En los árboles de expresión, los Nodes hoja son operandos y los Nodes no hoja son operadores. Eso significa que un árbol de expresión es un árbol binario donde los Nodes internos son operadores y las hojas son operandos. Un árbol de expresión consta de expresiones binarias. Pero para un operador unario, un subárbol estará vacío. 

Construcción del árbol de expresión:

  • El usuario proporcionará una expresión de sufijo para la cual el programa construirá el árbol de expresión. 
  • El recorrido en orden del árbol binario/árbol de expresión proporcionará una expresión infija de la entrada dada.

Ejemplo:  

Input:  A B C*+ D/
Output: A + B * C / D

Paso 1: Los primeros tres símbolos son operandos, así que cree Nodes de árbol y empuje los punteros hacia ellos en una pila como se muestra a continuación.

Create tree nodes

Paso 2: en el siguiente paso, se leerá un operador ‘*’, por lo que se extraen dos punteros a los árboles, se forma un nuevo árbol y se empuja un puntero a la pila.

New tree is formed

Paso 3: en el siguiente paso, se leerá un operador ‘+’, por lo que se extraen dos punteros a los árboles, se forma un nuevo árbol y se coloca un puntero en la pila.

push on stack

Paso 4: De manera similar, como en los casos anteriores, primero empujamos ‘D’ en la pila y luego en el último paso primero, leeremos ‘/’ y luego, como paso anterior, aparecerá el elemento superior y luego será el subárbol derecho de la raíz ‘/ ‘ y el otro Node será el subárbol derecho.

El árbol de expresiones construidas final es:

Final Constructed expression tree

A continuación se muestra el programa C++ para implementar el enfoque anterior:

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
class node {
public:
    char value;
    node* left;
    node* right;
    node* next = NULL;
    node(char c)
    {
        this->value = c;
        left = NULL;
        right = NULL;
    }
    node()
    {
        left = NULL;
        right = NULL;
    }
    friend class Stack;
    friend class expression_tree;
};
  
// Class stack to hold
// tree nodes
class Stack {
    node* head = NULL;
  
public:
    void push(node*);
    node* pop();
    friend class expression_tree;
};
  
// Class to implement
// inorder traversal
class expression_tree {
public:
    // Function to implement
    // inorder traversal
    void inorder(node* x)
    {
        if (x == NULL)
            return;
        else {
            inorder(x->left);
            cout << x->value << "  ";
            inorder(x->right);
        }
    }
};
  
// Function to push values
// onto the stack
void Stack::push(node* x)
{
    if (head == NULL) {
        head = x;
    }
  
    // We are inserting nodes at
    // the top of the stack [
    // following LIFO principle]
    else {
        x->next = head;
        head = x;
    }
}
  
// Function to implement pop
// operation in the stack
node* Stack::pop()
{
    // Poping out the top most[
    // pointed with head] element
    node* p = head;
    head = head->next;
    return p;
}
  
// Driver code
int main()
{
    // Postfix expression
    string s = "ABC*+D/";
  
    Stack e;
    expression_tree a;
    node *x, *y, *z;
    int l = s.length();
  
    for (int i = 0; i < l; i++) {
        // if read character is operator
        // then poping two other elements
        // from stack and making a binary
        // tree
        if (s[i] == '+' || s[i] == '-'
            || s[i] == '*' || s[i] == '/'
            || s[i] == '^') {
            z = new node(s[i]);
            x = e.pop();
            y = e.pop();
            z->left = y;
            z->right = x;
            e.push(z);
        }
        else {
            z = new node(s[i]);
            e.push(z);
        }
    }
  
    // Print the inorder traversal
    cout << " The Inorder Traversal of Expression Tree: ";
    a.inorder(z);
    return 0;
}
Producción:

El recorrido en orden del árbol de expresión: A + B * C / D

Publicación traducida automáticamente

Artículo escrito por kunjparekh310 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *