Hi kri shan Yes, you can evaluate this expression just by java program but you would have to know following things, 1. Infix notation 2. Postfix notation 3. How to evaluate a postfix notation. I have set of classes which will just work for you ready made once I cast things to double instead of int in my code... but if this is your assignment then you should try it yourself and we will help you through your try if you have any difficulties... Now saying that, if you aren't aware of any of the above three then I would explain little bit, 1. Infix notation is the one you have given where there are operands and operators in "between them" (hence INfix) 2. Postfix notation is the one where you would have operands and operators at the "end of operands" (hence POSTfix) 3. You can google on how to evaluate a postfix expression using stack. its pretty easy as we have Stack class in java already and we don't have to build our stack... Please let us know if anything else we can help.. Regards Maulin
Of course, you'll also have to figure out how to break the input string apart, finding all of the operators and operands. Again, if you're wanting help with that part, just ask and folks around here will gladly help nudge you in the right direction. So, welcome to JavaRanch, kri shan! Folks 'round here ain't gonna do your homework for you, but if you ask a good question, you're sure to get some darn good help.
Actually this is not my assignment, i just tried thru string tokenizer, but it did not work properly. If posible just give your code.
Joined: Nov 04, 2001
Hi kri shan Well the approach I took was have a separator character as a space. So I always expect things to be like, String expression = "3 + 4 * 8 - 8"; then do, String tokens = expression.split(" "); which will give me tokens as separate items in the array... I guess having this space as a seperator should not be a big problem if the expression is in our control. By that I mean if the expression isn't coming from any external source over which we don't have control and that source generates expression without spaces... I don't get how string tokenizer would help us as we don't have any special character based on which we can tokenize...You would have to write the logic to do parsing...the following is a psuedocode that might help here..
This code is written as I was thinking so there might be some corrections to make it more sensible and again you would have to learn little java.util.Collection classes as I am using them here... I guess this might help.. Regards Maulin
Joined: Dec 10, 2001
Originally posted by kri shan: Actually this is not my assignment, i just tried thru string tokenizer, but it did not work properly. If posible just give your code.
If you were to post the code that you've been working on, I'm sure folks around here could help to nudge in the right direction to get it working. Homework assignement or not, that's how we like to do things around here.
If you want to solve this problem properly, you'll need to know quite a bit about tree manipulation. What you really want to do here is analyze your expression and parse it into a tree structure where the arguments are leaf nodes on the tree and the operators are non-leaf nodes. For instance, the expression you used as an example, "1000+2000.00+30-40*123/324", would get parsed into the following tree structure: -( +( +(1000,2000.00), 30), *(40, /(123, 324))) In order to envision this in a tree properly, picture the expression operator(argumentLeft, argumentRight) as a tree with "operator" being in a node and "argumentLeft" being the left child of that node, "argumentRight" being the right child of that node. So basically, the strategy you'll want to follow is to parse through the string, pulling out each argument and operator as you come across it and placing them each in their own nodes. Then, once you get a complete subexpression, you assemble the nodes into the proper tree structure by relating the nodes with the proper parent/left-child/right-child relationships. You'll probably want to create some classes you can use to do all this with...Node, ExpressionElement, Argument, Operator. The way I would do things, let each node contain any number of children. That way, you can have a node that represents a unary operator like negate (has only one child), multiply (has two children, left and right), and average (has any number of children). You can't have nodes keep a reference to their parent though--the parent has to have references to all of its children so you can easily traverse the tree from the root node down. So the easiest thing to do is have the children register themselves with a parent, and parents keep a list of child nodes. It's also useful for children to know their parent so they can describe themselves (for example, root nodes have no parent).
This Node class as presented is useless to you because it doesn't have the capability to have content...it can only be related to other Nodes. You can simply add another field to this guy to have him take a String, which you would set to "+", "*", or "2000" (for example), depending on what you want him to be. I would go a slightly different route to make things very flexible. I would change him into a package-private class called NodeImpl and abstract all of his Node-like behavior into an interface called Node. Then you can write specific kinds of Nodes that use a backing NodeImpl, but control access to that interface. This way, you can make an ArgumentNode, which must be instantiated with a parent and can have no children (arguments must be leaf nodes, remember). You could extend ArgumentNode with LiteralNode, a type of node that only represents actual literal values like 2000. You could also extend ArgumentNode with VariableNode, which represents variables in expressions like x. Here's a start in this direction:
This is just a one-off, you can probably come up with a much cleaner way of doing things if you sit down and think it through. Now you can do a similar thing with operators--make a node that represents all the different kinds of operators and then extend it with UnaryOperatorNode, BinaryOperatorNode, and NaryOperatorNode (any number of arguments) that all extend OperatorNode. OperatorNode could have an evaluate() method that takes an ArgumentNode of and performs the operation on those arguments. The sky's the limit. One thing you'll want to think about doing is perhaps splitting up the tree-like behavior from the expression-specific behavior into separate classes. In this case, the different kinds of nodes like LiteralNode wouldn't take and set double values directly, they would take instances of a Literal class that represents the literal value itself. The advantage of this is that you could create a Variable class that has a name and possibly a Literal--if assigned, that Literal would be non-null, if unassigned, the Literal exists.