Segmentation fault (core dumped) c

Question

URI 1463

I’m solving URI Exercise 1464 (Link to the Exercise), and I had the problem of "Segmentation fault (core dumped)" and I can’t locate the root of the error (I know it might be in the realloc/malloc).

Below is the following 1463 code in cpp:

#include <iostream>
#include <string>
#include <queue>
using namespace std;

typedef struct no
{
    char info;
    struct no *left;
    struct no *right;
} Node;

typedef struct treeBin
{
    Node *root;
} treeBin;

string removeSpace(string input)
{
    string phrase;
    int cont, aux = 0;
    for (cont = 0; cont < input.length(); cont++)
    {
        if (input[cont] != ' ')
        {
            phrase.push_back(input[cont]);
        }
    }
    return phrase;
}

Node *createNode(string input, int first, int end)
{
    int cont = 0, cont_parent = 0, separator = 0;
    char carac = ' ';
    Node *node = (Node *)realloc(node, sizeof(Node));
    if (first == end)
    {
        node->right = NULL;
        node->left = NULL;
        node->info = input[first];
    }
    else
    {
        if ((input[first] == '(') && (input[end] == ')'))
        {
            node = createNode(input, first + 1, end - 1);
        }
        else
        {
            for (cont = first; cont <= end; cont++)
            {
                if (input[cont] == '(')
                {
                    cont_parent++;
                }
                else if (input[cont] == ')')
                {
                    cont_parent--;
                }
                else if (input[cont] == '+' || input[cont] == '-')
                {
                    if (cont_parent == 0)
                    {
                        separator = cont;
                        carac = input[cont];
                    }
                }
                else if (input[cont] == '/' || input[cont] == '*')
                {
                    if (cont_parent == 0 && (carac != '+' && carac != '-'))
                    {
                        separator = cont;
                        carac = input[cont];
                    }
                }
            }
            node->info = carac;
            node->left = createNode(input, first, separator - 1);
            node->right = createNode(input, separator + 1, end);
        }
    }
    return node;
}

void printLine(queue<Node *> row, int currentLevel)
{
    queue<Node *> aux;
    if (row.empty())
    {
        return;
    }
    else
    {
        cout << "Nivel " << currentLevel << ": ";
        while (!row.empty())
        {
            cout << row.front()->info;
            if (row.front()->left != NULL)
            {
                aux.push(row.front()->left);
            }
            if (row.front()->right != NULL)
            {
                aux.push(row.front()->right);
            }
            row.pop();
        }
        cout << endl;
        printLine(aux, currentLevel + 1);
    }
}

void printTree(treeBin *binTree)
{
    queue<Node *> aux;
    aux.push(binTree->root);
    printLine(aux, 0);
}

main()
{
    string input;
    treeBin *binTree = new treeBin;

    getline(cin, input);
    do
    {
        input = removeSpace(input);
        cout << input << endl;
        binTree->root = createNode(input, 0, input.length() - 1);
        printTree(binTree);
        getline(cin, input);
        if (!cin.eof())
            cout << endl;
    } while (!cin.eof());
    return 0;
}

Answer 1

We have to understand that Segmentation fault (core dumped) is a very common and difficult error at runtime, of course every program is called process this process has a part of the memory intended for it that is managed by OS operating system.

What happens when Segmentation fault happens is that your PROCESS or your program is accessing the memory of another process, such as when accessing a NULL pointer.

I divided the solution into 3 steps, 1: compile the debug version, 2: use gdb to debug.

1:g++ -g main.c -o main

the FLAG -g indicates the debug version.

2: gdb main

First I threw a break in main I advanced line by line, advancing I realized that its code gave problem in the following line:

133: binTree->root = createNode(input, 0, input.length() - 1);

Entering the function I noticed the following line:

36: Node *node = (Node *)realloc(node, sizeof(Node));

Note that realloc only works for a pointer that has already been allocated, either by new or by malloc or calloc.

I corrected your line by: Node *node = new Node; // Alocando a memoria.

CODE CORRECTED:

#include <iostream>
#include <string>
#include <queue>
using namespace std;

typedef struct no
{
    char info;
    struct no *left;
    struct no *right;
} Node;

typedef struct treeBin
{
    Node *root;
} treeBin;

string removeSpace(string input)
{
    string phrase;
    int cont, aux = 0;
    for (cont = 0; cont < input.length(); cont++)
    {
        if (input[cont] != ' ')
        {
            phrase.push_back(input[cont]);
        }
    }
    return phrase;
}

Node *createNode(string input, int first, int end)
{
    int cont = 0, cont_parent = 0, separator = 0;
    char carac = ' ';
    Node *node = new Node; // CORRIGIDO
    // Node *node = (Node *)realloc(node, sizeof(Node)); ERRO
    if (first == end)
    {
        node->right = NULL;
        node->left = NULL;
        node->info = input[first];
    }
    else
    {
        if ((input[first] == '(') && (input[end] == ')'))
        {
            node = createNode(input, first + 1, end - 1);
        }
        else
        {
            for (cont = first; cont <= end; cont++)
            {
                if (input[cont] == '(')
                {
                    cont_parent++;
                }
                else if (input[cont] == ')')
                {
                    cont_parent--;
                }
                else if (input[cont] == '+' || input[cont] == '-')
                {
                    if (cont_parent == 0)
                    {
                        separator = cont;
                        carac = input[cont];
                    }
                }
                else if (input[cont] == '/' || input[cont] == '*')
                {
                    if (cont_parent == 0 && (carac != '+' && carac != '-'))
                    {
                        separator = cont;
                        carac = input[cont];
                    }
                }
            }
            node->info = carac;
            node->left = createNode(input, first, separator - 1);
            node->right = createNode(input, separator + 1, end);
        }
    }
    return node;
}

void printLine(queue<Node *> row, int currentLevel)
{
    queue<Node *> aux;
    if (row.empty())
    {
        return;
    }
    else
    {
        cout << "Nivel " << currentLevel << ": ";
        while (!row.empty())
        {
            cout << row.front()->info;
            if (row.front()->left != NULL)
            {
                aux.push(row.front()->left);
            }
            if (row.front()->right != NULL)
            {
                aux.push(row.front()->right);
            }
            row.pop();
        }
        cout << endl;
        printLine(aux, currentLevel + 1);
    }
}

void printTree(treeBin *binTree)
{
    queue<Node *> aux;
    aux.push(binTree->root);
    printLine(aux, 0);
}

main()
{
    string input;
    treeBin *binTree = new treeBin;

    getline(cin, input);
    do
    {
        input = removeSpace(input);
        cout << input << endl;
        binTree->root = createNode(input, 0, input.length() - 1);
        printTree(binTree);
        getline(cin, input);
        if (!cin.eof())
            cout << endl;
    } while (!cin.eof());
    return 0;
}