Jump to content
  • Advertisement
Sign in to follow this  
Zotoaster

Need help with trees/linked lists

This topic is 4059 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
Advertisement
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
I would probably work with a boost::shared_ptr<boost::variant<...> >, with the types in the variant being my possible node types.

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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!