I was trying to solve this problem

https://practice.geeksforgeeks.org/problems/construct-an-expression-tree/1?utm_source=gfgpractice#

Problem: To create expression tree for given postfix expression

My Approach: I tried to maintain a stack of nodes and generated a tree using general postfix evaluation approach where the resultant for the given operator would be the node itself but with modified left and right pointers.

But I'm getting error.

Segmentation Fault (SIGSEGV)
Learn More about
Seg Fault

// { Driver Code Starts
#include<bits/stdc  .h>
using namespace std;

struct et
{
    char value;
    et* left, *right;
    
    et(char x){
        value = x;
        left = right = NULL;
    }
};

bool isOperator(char c)
{
    if (c == ' ' || c == '-' ||
            c == '*' || c == '/' ||
            c == '^')
        return true;
    return false;
}

void inorder(et *t)
{
    if(t)
    {
        inorder(t->left);
        printf("%c ", t->value);
        inorder(t->right);
    }
}

et* constructTree(char []);

int main()
{   
    int t;
    cin>>t;
    while(t--){
    char postfix[25];
    cin>>postfix;
    et* r = constructTree(postfix);
    inorder(r);
    cout<<endl;
}
return 0;
}// } Driver Code Ends


/*struct et
{
    char value;
    et* left, *right;
};*/

//function to construct expression tree
et* constructTree(char postfix[])
{
//code here
    stack<et> operand;
    et *root=NULL;
    for(int i=0;postfix[i] != '\0';  i){
        if(postfix[i]>='a' && postfix[i]<='z'){
            et node = et(postfix[i]);
            //cout<<node.value<<" "<<node.left<<" "<<node.right<<"\n";
            operand.push(node);
            /*et nod = operand.top();
            cout<<nod.value<<" "<<nod.left<<" "<<nod.right<<"\n";
            operand.pop();
            operand.push(nod);
            et *no = &(operand.top());
            cout<<no->value<<" "<<no->left<<" "<<no->right<<'\n';*/
        }
        else{
            et right1=operand.top();
            operand.pop();
            et left1=operand.top();
            operand.pop();
            et node = (et(postfix[i]));
            node.left = &left1;
            node.right= &right1;
            operand.push(node);
            root=&(operand.top());
            //cout<<node.value<<" "<<node.left<<" "<<node.right<<"\n";
            //inorder(root);
        }
    }
    //root=NULL;
    return root;
}

Can anyone please tell me what to do so that I won't get an error ?

CodePudding user response：

The problem is here node.left = &left1;

left1 is a local variable and will be destroyed. So after that you're accessing an invalid address.

You can use something like this node.left = new er(left1);

but you should prefer to store pointers in stack at first.

CodePudding user response：

In function constructTree, you do not do any dynamic memory allocations. So whatever memory pointer you return from that function, is pointing to an invalid memory by the time you're outside the function.