Member Avatar for Annuate

Hi I'm looking for a bit of direction for solving a problem. Just a bit of back story, my professor gave us a project of Building a tree, and using it to evaluate a mathematical expression. As far as the assignment is concerned it was completed but I was looking to expand on it a bit. When we build the tree it is pretty much hard coded into the project; Building the nodes and then linking them together. I was wondering how could I do something like take the users input, parse it and then use that to build a tree.

So far I have tried: First removing all the white space from the users input. Taking the formatted input and breaking it into tokens. I then want to somehow be able to set it up so it follows order of operations. I read that order of operations is easy to implement if I were to convert the input to something called reverse polish notation. So I did some research and found an algorithm on wikipedia called the Shunting-yard algorithm. This will take infix notation and convert it to reverse polish notation. I stopped here because the algorithm uses stacks and such and I think using so kind of defeats the purpose of using the tree as in the spirit of the original assignment because I could just as easily use a stack and rpn to solve the math. I feel/think? it might be overkill to go to such lengths and then put it back in a tree. Once I get the data in whatever format how would I go about building the actual tree without hard coding it. I'm thinking the solution is probably going to be recursive, but I haven't found any information really how to do it.

So am I on the right track here? Or did I veer very far off? I would appreciate some tips and pointers to the right direction.

  • 3 Contributors
  • 4 Replies
  • 159 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by rubberman
Member Avatar for griswolf

Have you heard of lex and yacc? (flex and bison if you want the GNU versions). Actually, for a basic calculator, just using the lexer is enough.

Member Avatar for Annuate

Have you heard of lex and yacc? (flex and bison if you want the GNU versions). Actually, for a basic calculator, just using the lexer is enough.

I have heard of so but never used. Mainly when I have heard of them being mentioned it was for compiler design. Makes sense though, since the source file of the language would need to be validated and such. Guess I'll have some reading to do. Would this also be good in pointing in the direction of building the tree? Or does this mainly apply only to parsing input? Thanks! :)

Member Avatar for griswolf

Yeah, those tools are definitely in the compiler-writer's kit. But they can be used for other things. Though if you think about it, you are pretty much describing a 'mini language' that can be 'parsed' and 'compiled' into an answer.

Its been decade(s? Wow!) since I paid much attention. A quick search found this man page for flex, with examples. I see from the examples that you can write code to handle token transitions, so that's probably enough to build your parse tree. Then a bit more code to walk the tree and you're done, eh? :)

Here's another examples page: http://comsci.liu.edu/~murali/lexyacc/Content.htm
It may be that bison [1] is exactly what you want?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.