Win a copy of The Java Performance Companion this week in the Performance forum!

# Mental block on expression calculator assignment

Jack Higgs
Greenhorn
Posts: 5
Write a program in Java that takes as input a mathematical expression consisting of decimal numbers and the four basic mathematical operators (addition, subtraction, multiplication and division) and nested mathematical expressions, and evaluates this expression.

Some examples:
� 5 + 6 * 2
� (5 + 4) * (4 - 2)
� (4 + (2 * (2 - 1))) * 1.2

Any ideas as to how I could go about this? Any general algorithms would be good (I'm certainly not asking any of you to supply detailed code, as that would defeat the object). I think you have to use a composite design pattern?

Cheers
__________________

Anu Pillai
Greenhorn
Posts: 28
Hi,

I think you can take a look at "Expression Tree" (Google). Its a way of representing equations like you have described in a tree structure and later evaluating them. Or you can use a stack also. While I was learning Java, we had an exercise to do the same. And we implemented it using stack. The point is that you can google for data structures and you will defenitely get links.

Here is one link I found: http://www.cs.colostate.edu/~anderson/cs200/expression.html
[ January 02, 2007: Message edited by: Anu Pillai ]

Ernest Friedman-Hill
author and iconoclast
Marshal
Posts: 24211
35
Hi Jack,

Welcome to JavaRanch!

Very roughly, you solve this in two steps:

1) Read the input and build a tree data structure out of it
2) Execute the expressions in the tree.

#2 is the easy one. Your tree may indeed be made up using the composite design pattern, in which case evaluating the tree becomes trivial, essentially a single (recursive) method call which walks the tree. In turn, step 1 breaks down into two stages:

1) "Lexical analysis", in which the individual "tokens" (numbers, operators, parens) are recognized
2) "Parsing", in which the tokens are arranged into a tree according to a set of expression-recognition rules.

#1 is the easy one this time. Step 2 is potentially complex and potentially tedious, which is why there are many parser generators which let you describe the "grammar" of your little language, and then generate a parser that understands this grammar (ANTLR is a good Java one.) But you can also do it yourself. You would have a set of methods that called each other to recognize appropriate sub-expressions; each of those would just have a chain of if-equal-then-else statements which branched to other methods. "If the current token is an open paren then call recognizeParentheziedExpression(); else if it's a number then call recognizeSimpleExpression(): else error()".

 It is sorta covered in the JavaRanch Style Guide.