Deleter for Simple Expression Tree in C++

Question

I have created a simple abstract class called expr_node which will serve as a base class for any expression-related nodes.

My goal is to create a simple deleter that can delete the allocated memory from the derived class in which would be recursive in some cases.

Rules and constraints (NOTE: for practice purposes only):

• Will not rely on smart pointers (std::unique_ptr and std::shared_ptr)
• Will not rely on std::variant or std::any
• Not using std::visit
• Apply dynamic dispatch
• Only use inheritance
• (i'm also aware that I use recursion very often here just for the sake of traversing each)

Important enumerations:

/// enum class: node_kinds
enum class node_kinds { 
  number_atom, unary_op, binary_op
};

/// enum class: unary_op_kinds
enum class unary_op_kinds { plus, minus };

/// enum class: binary_op_kinds
enum class binary_op_kinds {
  plus, minus, multiplies, divides, modulus
};

Abstract class:

/// abstract class: expr_node
struct expr_node {
  virtual ~expr_node() = default;
  virtual node_kinds node_kind() const = 0;
};

Derived classes from expr_node:

/// number_node
struct number_node : expr_node {
  std::int64_t value;
  
  number_node(std::int64_t value)
  : value(value) {}
  
  node_kinds node_kind() const override { return node_kinds::number_atom; }
};

/// unary_op_node
struct unary_op_node : expr_node {
  unary_op_kinds kind;
  expr_node* operand;
  
  unary_op_node(unary_op_kinds kind, expr_node* operand = nullptr)
  : kind(kind), operand(operand) {}
  
  node_kinds node_kind() const override { return node_kinds::unary_op; }
};

/// binary_op_node
struct binary_op_node : expr_node {
  binary_op_kinds kind;
  expr_node* left;
  expr_node* right;
  
  binary_op_node(binary_op_kinds kind, 
                 expr_node* left = nullptr, expr_node* right = nullptr)
  : kind(kind), left(left), right(right) {}
  
  node_kinds node_kind() const override { return node_kinds::binary_op; }
};

Main Highlight: Deleter

void delete_nodes(expr_node* node) {
  if (node != nullptr) {
    switch (node->node_kind()) {
      case node_kinds::number_atom:
        if (auto temp = dynamic_cast<number_node*>(node); temp != nullptr) {
          delete temp;
          temp = nullptr;
        }
        break;
        
      case node_kinds::unary_op:
        if (auto temp = dynamic_cast<unary_op_node*>(node); temp != nullptr) {
          delete_nodes(temp->operand);
          delete temp;
          temp = nullptr;
        }
        break;
        
      case node_kinds::binary_op:
        if (auto temp = dynamic_cast<binary_op_node*>(node); temp != nullptr) {
          delete_nodes(temp->left);
          delete_nodes(temp->right);
          delete temp;
          temp = nullptr;
        }
        break;
    }
    node = nullptr;
  }
}

Utilities for printing a tree:

std::ostream& operator<<(std::ostream& os, unary_op_kinds kind) {
    switch (kind) {
        using enum unary_op_kinds;
        case plus:
          return os << '+';
        case minus:
          return os << '-';
    }
    return os;
}

std::ostream& operator<<(std::ostream& os, binary_op_kinds kind) {
    switch (kind) {
        using enum binary_op_kinds;
        case plus:
          return os << '+';
        case minus:
          return os << '-';
        case multiplies:
          return os << '*';
        case divides:
          return os << '/';
        case modulus:
          return os << '%';
    }
    return os;
}

void display_nodes(expr_node* node, std::size_t level = 0) {
    if (node != nullptr) {
        switch (node->node_kind()) {
            case node_kinds::number_atom:
                if (auto temp_node = dynamic_cast<number_node*>(node); temp_node != nullptr) {
                    std::cout << std::string(level, ' ') << "number(" << temp_node->value << ")\n";
                }
                break;

            case node_kinds::unary_op:
                if (auto temp_node = dynamic_cast<unary_op_node*>(node); temp_node != nullptr) {
                    std::cout << std::string(level, ' ') << "unary_op(" << temp_node->kind << ")\n";
                    display_nodes(temp_node->operand, level + 1);
                }
                break;

            case node_kinds::binary_op:
                if (auto temp_node = dynamic_cast<binary_op_node*>(node); temp_node != nullptr) {
                    std::cout << std::string(level, ' ') << "binary_op(" << temp_node->kind << ")\n";
                    display_nodes(temp_node->left, level + 1);
                    display_nodes(temp_node->right, level + 1);
                }
                break;
        }
    }
}

Sample:

// 1 + (2 + (3 * (-4)))
expr_node* nodes = new binary_op_node(binary_op_kinds::plus,
  new number_node(1),
  new binary_op_node(binary_op_kinds::plus,
    new number_node(2),
    new binary_op_node(binary_op_kinds::multiplies,
      new number_node(3),
      new unary_op_node(unary_op_kinds::minus,
        new number_node(4)
      )
    )
  )
);

display_nodes(nodes);
delete_nodes(nodes);

Output:

binary_op(+)
 number(1)
 binary_op(+)
  number(2)
  binary_op(*)
   number(3)
   unary_op(-)
    number(4)

If we focus primarily on the deleter function delete_nodes, is it enough to be called a "proper" or is it properly deleting? Will there be undefined behavior happen?

Answer 1

A much simpler approach would be to create virtual destructors for unary_op_node and binary_op_node like the following:

struct unary_op_node : expr_node {
    expr_node* operand;
    // ...
    virtual ~unary_op_node() override {
        delete operand;
    }
};

struct binary_op_node : expr_node {
    expr_node* left;
    expr_node* right;
    // ...
    virtual ~binary_op_node() override
    {
        delete left;
        delete right;
    }
};

The whole tree can then be deleted with a simple delete statement:

int main()
{
    expr_node* nodes = new binary_op_node(binary_op_kinds::plus,
        new number_node(1),
        new binary_op_node(binary_op_kinds::plus,
            new number_node(2),
            new binary_op_node(binary_op_kinds::multiplies,
                new number_node(3),
                new unary_op_node(unary_op_kinds::minus,
                    new number_node(4)
                )
            )
        )
    );

    delete nodes;
}

---

Here are some notes on your existing implementation.

You should not use nullptr for comparisons. Use either use if (node) to check if the node is not null or if (!node) to check if the node is null.

This line:

if (auto temp = dynamic_cast<number_node*>(node); temp != nullptr) {

Can then be changed to the following:

if (auto temp = dynamic_cast<number_node*>(node); temp) {

And further reduced to:

if (auto temp = dynamic_cast<number_node*>(node)) {

---

If the dynamic_cast fails and returns null then something very nasty must have happened earlier. I would recommend that you either throw an exception when this happens:

case node_kinds::number_atom:
{
    auto temp = dynamic_cast<number_node*>(node);
    if (!temp)
        throw std::runtime_error("Failed to cast node");
    delete temp;
}
break;

Or, just assume that it will be successful:

case node_kinds::unary_op:
    delete dynamic_cast<unary_op_node*>(node);
    break;

---

Considering the following:

if (auto temp = dynamic_cast<number_node*>(node)) {
    delete temp;
    temp = nullptr;
}

I'm not sure why you are setting temp to nullptr. When temp falls out of the scope, it no longer exists and setting it to whatever value serves no purpose.

Perhaps this was closer to what your intentions were:

void delete_nodes(expr_node** node) {
    if (node) {
        switch ((*node)->node_kind()) {
            // ...
        }
        *node = nullptr;
    }
}

int main()
{
    delete_nodes(&nodes);
}

---

I think it may be worthwhile for a sanity check to include a default item to the switch. Something like the following:

    default:
        throw std::runtime_error("Invalid node type");