3. Prefix Expression Evaluation

3.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 ( * 2 3 ) ).

Your team is 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: ( + 1 2 3 4 ) evaluates to 10. This also works for - and /. ( - 10 1 2 3 ) 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 : value

or: value value_list

Operator: + or - or / or *

3.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 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 the names of all team members.
• 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 (base case), just return its value. If e isnt an integer, it must be 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.3. Required Main Class

A series of prefix expressions followed by done.3.4. Required Input

3.4 Required Input

A series of prefix expressions followed by done.

3.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).

Enter an expression: 3

Evaluates to 3

Enter an expression: ( + 1 2 )

Evaluates to 3

Enter an expression: ( / 16 3 )

Evaluates to 5

Enter an expression: ( - 10 1 2 3 )

Evaluates to 4

Enter an expression: ( / 120 2 3 4 )

Evaluates to 5

Enter an expression: ( + 1 ( - 12 10 ) 3 ( / 20 5 ) 5 ( * 2 3 ) )

Evaluates to 21

Enter an expression: ( + ( - ( * ( / 12 4 ) 2 ) ( + 3 7 ) ) 10 )

Evaluates to 6

A series of prefix expressions followed by done.