Arithmetic Expression Evaluator- WITHOUT Stacks! Recursive Program

The purpose of this project is to gain an understanding of using recursion to solve problems.

Write a Java application or applet that asks a user to enter an arithmetic expression, and then compute and print out the result. The expression may contain parenthesis, *, /, +, - and numbers. Unary plus and minus do not need to be supported. Normal Java evaluation precedence should be used. For example:

(1 + 2) * (6 / 2 + 3) = 18

BNF (Backus-Naur Form) is commonly used in compilers to describe the language to be accepted. A BNF definition of an arithmetic expression is:

::= + |

- |

::= * |

/ |

::= {) |

|

You may use the above BNF definition as a basis for your implementation. (I would prefer the answer to use this!!) The BNF definition should show you how to call the various functions recursively if you name your functions expression, term and factor.

The solution is to use normal RECURSION. NO STACKS!! That is, have the following procedures: expression, term, and factor. You call expression first. It always calls term (based on the BNF description). Upon return it checks for a + or or end of expression string. In the case of + or it calls expression (recursively) (based on the BNF description) and then does the addition or subtraction.

You do the same for term and factor following the BNF description.

The purpose of the project is to gain an understanding of Java recursion. Therefore recursion should be used. Stacks should not be used!!!!

That is, have the following procedures: expression, term, and factor. You call expression first. It always calls term (based on the BNF description). Upon return it checks for a + or or end of expression string. In the case of + or it calls expression (recursively) (based on the BNF description) and then does the addition or subtraction.

You do the same for term and factor following the BNF description.

You dont need any stacks. Just use normal Java recursion calling : expression, term, and factor based on the BNF description.

Hope this helps!!