This week's book giveaway is in the Artificial Intelligence and Machine Learning forum.
We're giving away four copies of TensorFlow 2.0 in Action and have Thushan Ganegedara on-line!
See this thread for details.
Win a copy of TensorFlow 2.0 in Action this week in the Artificial Intelligence and Machine Learning forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Paul Clapham
  • Bear Bibeault
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Tim Cooke
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • salvin francis
  • Scott Selikoff
  • fred rosenberger

evaluate parse tree (by doing a tree walk) for arithmetic expressions passed to it

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In my programming languages class we are working on a parser project that generates a parse tree and evaluates mathematical expressions based on the trees generated.

I have completed the first part, and the correct parse trees are generated according to the given mathematical expressions.

I am having trouble getting started on the second part, in which the interpreter does a tree walk and calculates a result based on the characteristics of the parse tree.

I only need to create one method to do this, everything else has been included in the assignment.

Here is my working method for addition and subtraction in my parser class:



What I need to do now is include a method in my interpreter class that can evaluate the expression "a=2+3" if I can figure that part out I can probably get the rest, but
as for now I have no idea what to do.

This is what the given evaluate method in my interpreter class looks like:



These are the specific assignment instructions:

You will be completing the method evaluate(TreeNode t) contained in the TestInterpreter class so that it correctly evaluates the parse tree (by doing a tree walk) for arithmetic expressions passed to it as the parameter t, and returns the result of the evaluation. Here are the meanings (interpretations) of the operations associated with the operators, all with respect to real operands:
+ addition
- subtraction



Any help is appreciated. Thanks!

 
Marshal
Posts: 25969
70
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, just knowing that you have a TreeNode doesn't really get you very far. Do you know anything about the structure of that TreeNode and the other nodes it's connected to? I expect it would help if you drew a picture of the tree which is below that node, or at least of an example like the one you had there.
 
Jim Gallagher
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The corresponding tree is output to the console, so I know what the tree looks like. Again, like I said I'm completely stumped.

This is the TreeNode class:



 
Paul Clapham
Marshal
Posts: 25969
70
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So what's in the root node of this tree?
 
Saloon Keeper
Posts: 7395
66
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I guessing your parse tree should look something like this but your code doesn't handle the '=' symbol, or 'a', or any numeric constants.
 
Marshal
Posts: 70718
288
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are you using Strings for your values in the nodes? You will either have operators or expressions. Since you have done your parsing already, presumably from an infix expression to a tree, you will be able to reduce your expressions to one of variable and number, each being a kind of terminal. Remember that variables should have a value set before you can use them to the right of the assignment operator.
I would suggest you consider an Operator enum, maybe a bit like that in the Java® Language Specification (=JLS).
 
Bartender
Posts: 4109
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Another way is to make sure that a TreeNode knows how to determine its value. So, say, for a ConstantNode that would be just the value, for an AddNode that would be the sum of left.evaluate + right.evaluate.
So, given a Tree, all you need to do is: root.evaluate();

And for things like: a = 2 + 3, you could have an "assignmentNode", like Carey describes, but perhaps easier is to maintain a Map<String, TreeNode> so that when encountering the expression 'a = b + 2', you can look up b and protest if it is not in the map.
 
Saloon Keeper
Posts: 22678
153
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Why are you using Strings for your values in the nodes? You will either have operators or expressions.



I wouldn't worry too much about that. That's a design decision and there are both positives and negatives in doing premature conversions. Anyway, it's not uncommon to have the first pass produce a string-based Abstract Syntax Tree and then have a later pass refactor it. It tends to make reducing expressions like 5 +7, "ABC" + "GO" and "ABC"+123 easier.

One popular way to process an AST for interactive calculator system is, in fact to run reductions on the AST until you end up with a single node containing the solution.

That is, Becomes:
Which then becomes simply "a", which is then usually resolved to its value and printed.
 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Did anyone figure out how to do this?
 
Campbell Ritchie
Marshal
Posts: 70718
288
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Yes, people probably did work out how to do it. You do a post‑order traversal of the tree (usually left to right) to get the tokens in postfix order; an in‑order traversal to get infix, and a pre‑order traversal to get prefix. Unless you are writing LISP, you probably want postfix.
 
Paul Clapham
Marshal
Posts: 25969
70
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Andrey Little wrote:Did anyone figure out how to do this?



Yes, I did. Like Campbell says, others did too. Why do you ask?
 
a wee bit from the empire
Thread Boost feature
https://coderanch.com/t/674455/Thread-Boost-feature
reply
    Bookmark Topic Watch Topic
  • New Topic