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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Junilu Lacar
• Rob Spoor
• Paul Clapham
Saloon Keepers:
• Tim Holloway
• Tim Moores
• Jesse Silverman
• Stephan van Hulst
• Carey Brown
Bartenders:
• Al Hobbs
• Piet Souris
• Frits Walraven

# Mental block on expression calculator assignment

Greenhorn
Posts: 5
• Number of slices to send:
Optional 'thank-you' note:
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
__________________

Greenhorn
Posts: 28
• Number of slices to send:
Optional 'thank-you' note:
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 ]

author and iconoclast
Posts: 24203
44
• Number of slices to send:
Optional 'thank-you' note:
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()".

 With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.