• Post Reply Bookmark Topic Watch Topic
  • New Topic

My expression parser program  RSS feed

 
John Wickerson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey guys,

I have a fairly general question on Java.

I'm having a bash at writing a program that parses an expression. That is, it is given input such as the string "(x+5)*(x-4)", then it works out the 'expression tree' that represents the expression, which in this case would be:



Now, I have the superclass Operand, which has two children classes: Branch and Leaf. Each node on the above tree is either a Branch or a Leaf. The operations (e.g. x-4) are Branches, and always consist of two Operands and one Operator. The constants and variables are Leaves, and simply consist of a value.

Now to my question.

How to create the expression? I am currently using

This works great 99% of the time. However, if my expression is simply a constant, such as 5, ...

... it doesn't work, because clearly, 5 is a Leaf not a Branch. I have to use:

but this clearly isn't as good, because I have to decide whether the string represents a Leaf or a Branch before even constructing the expression. Ideally, I would make the expression with code like the following:

This would be nice because the class Operand encompasses Branches and Leaves. Unfortunately, Operand is an abstract class, and I feel it is best to keep it that way.

Any advice would be gratefully received...


Kind regards,
John
 
John Wickerson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(UPDATE)

I thought I'd let you know that I've come up with what I think is a reasonably good solution to the problem - I'd still appreciate your comments on my solution or any better solutions...

I now use



And the abstract class Operand has the static method makeEx:



Cheers,
John
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Using exceptions as flow control in valid syntax is almost always wrong. Let's try to replace that.

An alternative is to parse ahead far enough to see if a node is a branch or a leaf. Look ahead parsing is pretty tricky so maybe this tells us that the concept of Branch and Leaf classes isn't working for us.

Maybe they're all just Nodes and some have children and some don't.

Any of that sound useful?
[ March 28, 2006: Message edited by: Stan James ]
 
John Wickerson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hmm, I did suspect that what I was doing wasn't particularly 'good coding' . I'll have a go at using your suggestion. Off the top of my head I'm thinking the new Operand class would be something like this:A nicety of doing it this way is that o1 could be set and o2 left Null for an operation like negation that takes only one operand.
 
John Wickerson
Greenhorn
Posts: 13
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(Update)
I've now fully implemented the new version as suggested. It works beautifully, so thanks for suggesting it!

John
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!