Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Mental block on expression calculator assignment

 
Jack Higgs
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
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
Marshal
Pie
Posts: 24211
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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()".
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic