C++

Forum

 
Help with popping stack of pointers

bujiko (9)
Hey guys. So I am creating a program that will convert a postfix expression into an infix expression. I have to use an expression tree. I am just starting out and I am already having a bit of trouble. What I am doing is reading numbers and creating a separate tree for each of them, then creating a pointer and pushing it onto the stack. However, when I try to output my stack, it isn't popping. For example if I input 42, it should output: 2, 4. Instead, it outputs 2, 2. If I insert 403, it should output 3, 0, 4. Instead if outputs: 3,3,3. The top of the stack isn’t changing. Can anyone see why?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <stack>
#include <string>
using namespace std;

struct tree
{
	char oper;
	tree* right;
	tree* left;
};

tree insertint(char x)
{
	
	tree temp;
	
	
	temp.oper = x;
	temp.right = NULL;
	temp.left = NULL;
	
	return temp;	
}


int main()
{
string input;
stack<tree*> s;
tree* p;
tree temp;

cout << "Please enter an expression" << endl;
cin >> input;
for(int i=0; i < input.length(); i++)
{
	temp = insertint(input[i]);
	p = &temp;
	s.push(p);
	
}
while(!s.empty())
{
p= s.top();
cout << p->oper << endl;
s.pop();
}

}
ne555 (10692)
You are putting the same pointer over and over again.

1
2
3
 
stack<tree> s;
//...
   s.push( insertint(input[i]) );
Last edited on
ajh32 (659)
You don't need a seperate function you just need a constructor for your struct:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
#include <iostream>
#include <stack>
#include <string>
using namespace std;

struct Tree
{
	Tree(char _oper)
		: oper(_oper)
		, right(NULL)
		, left(NULL)
	{
	}

	char oper;
	Tree* right;
	Tree* left;
};

int main()
{
	string input;
	stack<Tree> s;

	cout << "Please enter an expression" << endl;
	cin >> input;
	
	for(int i=0; i < input.length(); i++)
	{
		s.push(Tree(input[i]));
	}

	while(!s.empty())
	{
		Tree t = s.top();
		cout << t.oper << endl;
		s.pop();
	}
}
bujiko (9)
Oh, I understand now. I was using the pointer wrong. I forgot that changing the pointer like that will continually change it. I fixed that up, and added the rest of the program but I came across a problem again. When the input is an operator such as '+', I made a new tree and set its right and left pointers to the two trees at the top of the stack, then popped them off the stack. Then I create a pointer and point it to the final top of the stack and use that pointer to display it, in infix form with parentheses. My insertoper function is causing a problem though, it is putting the wrong value into the left pointer. I hate to be a bother, but I cant seem to find the problem. If one of you could take another look at it :(


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
#include <iostream>
#include <stack>
#include <string>
using namespace std;

struct tree
{
	char oper;
	tree* right;
	tree* left;
};

tree insertint(char x)
{
	
	tree temp;
	
	
	temp.oper = x;
	temp.right = NULL;
	temp.left = NULL;
	
	return temp;	
}

tree insertoper(char x, stack<tree> &s)
{
	tree temp;

	temp.oper = x;
	temp.right = &s.top();	
	s.pop();
	temp.left = &s.top();
	s.pop();

	return temp;
}



void displaytree(tree *tree)
{
	if(tree->left == NULL && tree->right == NULL)
	cout << tree->oper;
	
	else
{
	cout << "(";
	displaytree(tree->left);
	cout << tree->oper;
	displaytree(tree->right);
	cout << ")";
}
}



int main()
{
string input;
stack<tree> s;
tree* p;
tree temp;

cout << "Please enter an expression" << endl;
cin >> input;

for(int i=0; i < input.length(); i++)
{
if(input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
{
	s.push(insertoper(input[i], s));
}
else
{
	s.push(insertint(input[i]));
}

}

p = &s.top();
displaytree(p);

}
ajh32 (659)
Please give some example input, also what output you are expecting and what you are actually getting.
bujiko (9)
If I input 53+ it should output (5+3) the output I am getting is just a bunch of left parentheses, non stop until I get a core dump.
ajh32 (659)
You need to be careful with pointers. You are assigning address' to your tree right and left members that go out of scope so the address is no longer valid etc. I think it is best under this scenario to assign our data on the heap. But you also then need to be careful to ensure you delete the memory allocated before you lose the address'. The following code I believe achieves your objective. I have changed your struct into a class and set the member variables as private so that they don't get tampered with from outside of the code. Please also note the default, custom and copy constructors as well as the destructor. Let me know how you get on with it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
using namespace std;

class tree
{
public:
    // default constructor:
    tree()
    : oper('0'), right(NULL), left(NULL)
    {
    }
    
    // custom constructor:
    tree(char _oper, tree* _right = NULL, tree* _left = NULL)
    : oper(_oper), right(_right), left(_left)
    {
    }
    
    // copy constructor:
    tree(const tree& t)
    : oper(t.oper) , right(t.right) , left(t.left)
    {
    }
    
    // destructor:
    ~tree()
    {
        if (right)
        {
            delete right;
            right = NULL;
        }
        
        if (left)
        {
            delete left;
            left = NULL;
        }
    }
    
    static void displaytree(tree* tree)
    {
        if(tree->left == NULL && tree->right == NULL)
            cout << tree->oper;
        
        else
        {
            cout << "(";
            displaytree(tree->left);
            cout << tree->oper;
            displaytree(tree->right);
            cout << ")" << endl;
        }
    }

private:
    char oper;
    tree* right;
    tree* left;
};


int main()
{
    string input;
    stack<tree*> s;
    
    cout << "Please enter an expression" << endl;
    cin >> input;
    
    for(int i=0; i < input.length(); i++)
    {
        if(input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
        {
            tree* p = s.top();
            tree* right = new tree(*p);
            delete p;
            s.pop();
            p = s.top();
            tree* left = new tree(*p);
            delete p;
            s.pop();
            
            p = new tree(input[i], right, left);
            s.push(p);
        }
        else
        {
            tree* p = new tree(input[i]);
            s.push(p);
        }
        
    }
    
    tree::displaytree(s.top());

    while (!s.empty())
    {
        tree* p = s.top();
        delete p;
        s.pop();
    }
}
Last edited on
bujiko (9)
Ok sweet, that worked for when the equation insert was only 2 number with an operator. For example. 53+ outputs (5+3) which is correct. However when I input something with more numbers and operators such as 53+2*9-, the expected output is: (((5+3)*2)-9). Instead I was getting a segmentation fault, or output that was missing numbers. What I did was remove the parts of the code that said "delete p" in this section: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
for(int i=0; i < input.length(); i++)
    {
        if(input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
        {
            tree* p = s.top();
            tree* right = new tree(*p);
            delete p;
            s.pop();
            p = s.top();
            tree* left = new tree(*p);
            delete p;
            s.pop();
            
            p = new tree(input[i], right, left);
            s.push(p);
        }


So it became: 
1
2
3
4
5
6
7
8
9
10
11
12
13
 
if(input[i] == '+' || input[i] == '-' || input[i] == '*' || input[i] == '/')
        {
            tree* p = s.top();
            tree* right = new tree(*p);
            s.pop();
            p = s.top();
            tree* left = new tree(*p);
            s.pop();
            
            p = new tree(input[i], right, left);
            s.push(p);
        }


And it ended up working perfectly. Not sure why the delete calls were causing a problem. Anyway, thank you so much for the help! :)
ne555 (10692)
Before you were making a lot of copies
Now you are leaking memory.

The copy constructor and destructor are producing a double delete
ajh32 (659)
@bujiko - you need the deletes as @ne555 was pointing out:

In the follwoing code we are creating two new instances of tree objects and using the copy constructor to copy the data previously held on the stack, as we are getting rid of these two pointers off the stack we need to delete them else you end up with a leak. So please put these delete's back:

1
2
3
4
5
6
7
8
9
10
11
 
tree* p = s.top();
tree* right = new tree(*p);
delete p;
s.pop();
p = s.top();
tree* left = new tree(*p);
delete p;
s.pop();
            
p = new tree(input[i], right, left);
s.push(p);
Last edited on
ajh32 (659)
I've been thinking about what you are attempting to do here. I don't think your solution to the problem is a very good one. Sorry. I can see it getting rather complicated. I think a better way to parse the input string would be to use regex.
Topic archived. No new replies allowed.