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