An arithmetic expression can be represented in three differentformats: infix, prefix, and postfix. In the infix notation, theoperator comes between two operands. In the postfix notation, theoperator comes after its two operands. For example, an expressiona/b can be transformed to ab/. The following are some examples ofthe postfix expressions:

2+6*4 Its postfix notation is 2 6 4 * +

2-3+5/4*9-1 Its postfix expression is 2 3 – 5 4 / 9 * + 1 -

For this assignment, write a JAVA program that reads an postfixexpression and evaluates the postfix expression.Your program should display the following menu repeatedly:

1. Read an expression in postfix notation.

// Read an infix expression and print out the string forverification.

2. Evaluate the postfix expression.

0. Exit.

For the input string, you can make the followingassumptions:

Input strings are error-free

+, -, *, / are the only operators used

All operand are positive integers consisting of one or moredigits.

Space appears in the input string to separate the operands andoperators.

Implement a class StackLink, which is a stackimplemented by a linked list (Do not use the JAVApredefined class java.util.LinkedList). Your program should usestack operations to evaluate the postfixexpression. The following figure shows how stacks can help.

The following are some results when your run the program:

C:'>java Homework4

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

1

Enter a postfix expression: 32 15 2 * + 36 4 / -

The entered infix expression is: 32 15 2 * + 36 4 / -

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

2

32 15 2 * + 36 4 / - = 53

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

1

Enter a postfix expression: 3 4 / 15 * 9 / 6 8 * + 7 - 54 +

The entered infix expression is: 3 4 / 15 * 9 / 6 8 * + 7 - 54+

Select from:

1. Read an expression in postfix notation.

2. Evaluate the postfix expression

0. Exit.

2

3 4 / 15 * 9 / 6 8 * + 7 - 54 + = 95

Select from:

1. Read an expression in infix notation.

2. Convert infix to postfix.

3. Evaluate the postfix expression

0. Exit.

0

Goodbye.