Recursive expression evaluator using Java

629 picture 629 · Nov 1, 2010 · Viewed 14.8k times · Source

I am going to write an expression evaluator which only does addition and subtraction. I have a simple algorithm to do that; but, I have some implementation problems.

I considered an expression as (it is a String)

"(" <expression1> <operator> <expression2> ")"

Here is my algorithm

String evaluate( String expression )

   if expression is digit
      return expression

   else if expression is "(" <expression1> <operator> <expression2> ")"
      cut the brackets out of it
      expression1 = evaluate( <expression1> )
      operator = <operator>
      expression2 = evaluate( <expression2> )

   if operator is +
      expression1 + expression2

   else if operator is -
      expression1 - expression2 

My problem is parsing <expression1>, <operator> and <expression2> from the expression. How can I do that?

Note: I'm not asking for a code. All I need is an idea to do that.

Thank you,

-Ali

Answer

The Archetypal Paul picture The Archetypal Paul · Nov 1, 2010

My problem is parsing <expression1>, <operator> and <expression2> from the expression

Don't do that, then :) When you see an opening bracket, do your recursive call to expression. At the end of the expresssion, either you find another operator (and so you're not at the end of the expression after all), or a right-bracket, in which case you return from the evaluate.