Sign in to follow this  

Need help with trees/linked lists

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've been working on my scripting language for a while now, and I basically want to make an AST (abstract syntax tree) from it. http://img383.imageshack.us/img383/4686/astdesignch3.jpg It's not the actual conversion that I need help with. It's actually working with the trees. I have this piece of code:
struct _lASTNode
{
	_lData data;
        _lASTNode* parent;
	vector<_lASTNode*> children;
};
Problem is, I don't know how to move through the tree, add nodes with data, and then move back up the tree. I had a rough idea of having a stack to follow through the tree, and whenever I needed to record a location, I would simply add it to the stack, and then move back up the tree and pop the stack as I go. But it's all theory for me just now. I still have to have a bit of help with this. Anyone out there willing to lend a hand? Cheers.

Share this post


Link to post
Share on other sites
Why are you traversing a tree in the first place? What kind of operation are you performing?

Stack, recursion, manual traversal are all valid.

But it comes down to exact task you're trying to perform, especially since you mention construction of the tree isn't a problem, and that requires full set of operations already.

Then there's also visitor pattern, which can be useful for some tree parsing.

Share this post


Link to post
Share on other sites
O_o

I truely don't know the answer to your question. Mostly why I came here to ask the question, heheh.

But anyway, I figured out that the tree could be made in a less tree like structure. I came up with two ideas. The first.. well, it's probably too complex for even me to fully understand, but the second one just follows a sort of depth thing. Like this:


- Root
-- main function
--- var myvar
---- *
----- +
------ 1
------ 3
----- 2
--- =
---- myvar
----- 2
---- 3
--- print
---- myvar
----- 3


(That's ment to be like the picture I gave in the link)

Share this post


Link to post
Share on other sites
Hi,

You might want to consider looking at some compiler theory books: pay particular attention context free grammars and parsing.

Good luck,

MAMEman.

Share this post


Link to post
Share on other sites
As I said, it's not the compilation I want to know about, just how the trees would be coded. After all, I'm sure they could be used for other things rather than just compilers.

Share this post


Link to post
Share on other sites
Hey Bud, this looks almost exactly like a problem I had in my second computer science course in college. It kind of makes me think this is a class project for you. So I can't, in good conscious, give you the code. But I will try to help you anyway :-)

You need to make a class to do all this stuff for you. And your node might be easier to implement like this (ok, I'll give you this bit of code):

struct node{
_lData data;
node* parent;
node* left;
node* right;
};



The reason being that the node becomes easier for you to visualize in the tree. Using a vector is just going to muck it all up. Of course, you've read the stuff on wikipedia, right? Right?
http://en.wikipedia.org/wiki/Binary_search_tree

So, your class should have the basic functions for managing a tree. Insert, delete, find, print, etc. Wikipedia gives a good description of the stuff (and too much source for me to be comfortable with). Since it looks like you're making a calculator then there's a couple of specifics for you. All the leaf nodes are going to be numbers, and all the rest of the nodes are all the operators. You have to first convert the input string (the calculation you want to perform, like (4*(3+4)) into what's called an infix (google it). The tree converts it to what's called a postfix for you. That's the beauty of data structures, the structure itself solves the problem.

The problem areas you're going to have are the insert function, and conversion to infix. Those are where I had problems. But after you get your class set up properly then it's all over.

Good luck, dude. And feel free to come back if you have more questions! But you better be able to show you've given it some work first ;-)

- Goishin

Share this post


Link to post
Share on other sites
Goishin,

Thanks for all the advice. I seem to be able to get trees actually working. Now it's converting the way equations are set out. I actually already know a way of converting Infix to Postfix (called RPN aswell right?), called the Shunting Yard Algorithm. Now, it might sound silly that I already know this method and still want to use the trees, but with some mucking around in notepad and paint, I think I will find the compilation process alot easier. Equations are just one part, but the rest will all work in a similar way.

So anyway, I have googled and Wiki'd any menthods for convertion infix (or if not infix, RPN) to a syntax tree. I haven't found anyway yet, so I figure I'd ask you since you seem to know alot about this :)


PS, sorry for the lack of evidence =]

Share this post


Link to post
Share on other sites

By honest advice is to start using recursion. Recursion is simpler to do, and you will learn a great deal from it. It will "show" you exactly how the AST works.

When you have more experience with it (you don't need to implement everything) you could use iterative methods.

After that you will see that it will be much easier to "convert" recursion to iteration.

I hope (though, I'm confident) you succeed.

Share this post


Link to post
Share on other sites
It's worth noting that technically the recursion would still build a tree -- it would be defined by the stack frames on the stack and would be lost as soon as the initial function returned (assuming it wasn't copied elsewhere, of course), but a tree nonetheless.

Share this post


Link to post
Share on other sites
Shunting Yard Algorithm, huh? Man, that Dijkstra dude, you'll see HIS name again.

If it is a class project you're working on, the real goal of this is the data structure, the tree. I don't know if your teacher is a recursion nut or not (mine was, and it drove me bonkers when later I had a teacher who was an array nut. I kept trying to do all my data structures using recursion, and she kept taking off points for not using an array. Go figure), but if you've got your tree working, then you can forget about it for now. But something tells me you're going to have to do quite a bit of futzing around with your insert function.

So postfix: The postfix comes from the way you traverse the tree. You know that there's a couple of different ways of traversing a tree, right? Think about it, there's pre-order, in-order, and post-order, right?
So you've got a calculation:
3 + 4
It get's converted to postfix:
3 4 +
You load it into the tree and it looks like this:
(+) <-hope that turns out ok after I post
(3) (4)
The operator is the parent (in this case the root) and the numbers are the leaf nodes. No matter how many operators and nested calculations you have, the numbers are always the leaf nodes.

Now look at the first two formats for the calculation, and look at how they look in the tree. Is there something about the way they look and how the tree is loaded that you should be paying attention to? Keep in mind there is a very strong reason for conversion to postfix. I'll give you a hint, think about the methods of tree traversal.

Ok, that should be enough for now.

Keep going, dude. You'll make it...

- Goishin

Share this post


Link to post
Share on other sites

This topic is 3845 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this