IN JAVA: WRITE THE ENTIRE THING!!! AND FOLLOW THE DIRECTIONS VERY CAREFULLY!!!

Have both ArrayStack and LinkedStack and StackInterface implemented in your code

(the files ArrayStack.java and LinkedStack.java together with Node.java

Problem 7.

In the language Lisp, each of the four basic arithmetic operators appears before an arbitrary number of operands, which are separated by spaces. The resulting expression is enclosed in parentheses. The operators behave as follows:

• (+ a b c ...) returns the sum of all the operands, and (+) returns 0.
• (− a b c ...) returns a − b − c − ..., and (− a) returns −a. The minus operator must have at least one operand.
• (* a b c ...) returns the product of all the operands, and (*) returns 1.
• (/ a b c ...) returns a / b / c /..., and (/ a) returns 1 / a. The divide operator must have at least one operand.

You can form larger arithmetic expressions by combining these basic expressions using a fully parenthesized prefix notation. For example, the following is a valid Lisp expression:

(+ (− 6) (* 2 3 4) (/ (+ 3) (*) (− 2 3 1)))

This expression is evaluated successively as follows:

(+ (− 6) (* 2 3 4) (/ 3 1 −2))

(+ −6 24 −1.5)

16.5

Design and implement an algorithm that uses a stack to evaluate a legal Lisp expression composed of the four basic operators and integer values. Assume that the integer values in an input string are one-digit numbers. Write a program that reads such expressions and demonstrates your algorithm.

Note, although the operands in the initial string are integers, intermediate results and the final result must be a real value (i.e. of type double).

Bonus points (up to 10): allow multidigit input.

Suggestions.

1. use two stacks: operatorStack and valueStack.
2. operatorStack contains Characters
3. open parentheses are put in the valueStack to indicate when you stop popping values upon encountering closed parenthesis.
4. The numerical values and ‘(‘ must be of the same type. You can do it in three different ways:
5. Allocate a stack of Double and define a special constant for representing ‘(‘: this constant should be something that is unlikely a result of calculation (e.g. 1.234567e257)
6. Allocate a stack of String and treat numbers and ‘(‘ as Strings, convert String to double during calculations, and convert double to String for pushing the value;
7. define a class having a numerical field, a Character field, and a boolean flag for selecting which field to use, and allocate a stack of this type.