Prefix Expression Evaluation

$3\mathrm{.}1.$ Problem Description

Mathematical expressions usually use infix notation in which the operator is in between the operands: $(1+(2*3)).$ With prefix notation, the operator comes first: $(+1(*23)).$

You are to write a program that evaluates expressions written in prefix notation. The values will be all integers and the only operators you need to handle are $+,-,*,$ and $/,$ all of which retain their traditional meanings.

Note that with prefix notation, we are not limited to just two operands. That is$,$ we can add any number of values: $(+1234)$ evaluates to $10.$ This also works for $-$ and $/.(-10123)$ is interpreted as $10-1-2-3$ and evaluates to $4.$

Here is the recursive definition of your expressions:

expression: integer$\_$value

or: $($ operator value$\_$list $)$

value$\_$list : expression

or: expression value$\_$list

Operator: $+$ or $-$ or $/$ or $*$

$3\mathrm{.}2.$ Notes

$$ Your program can assume that the input is well$-$formed. For example, there will be no bad operators, floating point values, unmatched parentheses, or missing arguments. All the tokens in the input will be separated by whitespace $($space$,$ tab, or newline$)$ which means that you can use Scanner.getNext$()$ to get each token.

$$ Your program is to continue to accept expressions until the user enters $$done$.$ Ignore case on this comparison.

$$ Your output must include your name.

$$ Your solution must be recursive.

$$ Turn in only your source file: PrefixEvaluation.java.

$$ Make sure your class is not in a package $($that is$,$ it is in the default package$).$

$$ Hint: Consider writing a single recursive method int eval$($String e$)$ which evaluates e$.$ If e is an integer $($the base case$),$ just return its value. If e isn$$t an integer, it must be start with a $(($recursive case$).$ Read the operator next, then read, evaluate and store $($ArrayList$?)$ expressions until you find the matching $).$ Once you have your values $($the operands to the operation$),$ perform the required operation and return its result.

$3\mathrm{.}3.$ Required Main Class

PrefixEvaluation

$3\mathrm{.}4.$ Required Input

A series of prefix expressions followed by $$done$.$

Page $7$

$3\mathrm{.}5.$ Required Output

For each expression, evaluate the expression and print the result. You can use the examples below as a set of test cases. Your output should look like the following $($input is in GREEN$).$

Prefix Evaluation $$ Your Name

Enter an expression: $3$

Evaluates to $3$

Enter an expression: $(+12)$

Evaluates to $3$

Enter an expression: $(/163)$

Evaluates to $5$

Enter an expression: $(-10123)$

Evaluates to $4$

Enter an expression: $(/120234)$

Evaluates to $5$

Enter an expression: $(+1(-1210)3(/205)5(*23))$

Evaluates to $21$

Enter an expression: $(+(-(*(/124)2)(+37))10)$

Evaluates to $6$

Enter an expression: DoneI need help