The moose likes Java in General and the fly likes Mental block on expression calculator assignment Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Mental block on expression calculator assignment" Watch "Mental block on expression calculator assignment" New topic

Mental block on expression calculator assignment

Jack Higgs

Joined: Jan 02, 2007
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?

Anu Pillai

Joined: Oct 09, 2006
Posts: 28

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:
It will help you to understand what I am talking about.
[ January 02, 2007: Message edited by: Anu Pillai ]
Ernest Friedman-Hill
author and iconoclast

Joined: Jul 08, 2003
Posts: 24199

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()".

[Jess in Action][AskingGoodQuestions]
I agree. Here's the link:
subject: Mental block on expression calculator assignment
It's not a secret anymore!