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:
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.
posted 1 week ago
The corresponding tree is output to the console, so I know what the tree looks like. Again, like I said I'm completely stumped.
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).
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.
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.
"privilege" comes from the Latin words for "private" and "law" (legal) and dates to feudal times. To "claim privilege" meant that you were above the laws that applied to the common people.
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.