In this assignment you are to start with the code base posted on the course$$s page

on Canvas $($ListStack$.$java, ListNode.java, and StackDriver.java$)$ and modify the code

to implement additional functionality.

The only file you should be editing for this assignment is StackDriver.java which

already has certain functionality implemented in it such as evaluateExpr, and

isLegal. You must keep this functionality as is without editing.

Your program should implement the following functionality:

$1.$ Implement a menu$-$driven interface to be able to:

a$.$ Read an expression, check if it$$s legal $($Use existing functionality$)$

b$.$ Evaluate the inputted expression

i$.$ Only evaluate if the user inputted an expression, otherwise

indicate that no expression has been entered.

ii$.$ Once you evaluate this expression, its result should be printed

to the screen. Once evaluation is finished, the program must

require you to enter a new expression if this option is selected

again. But selecting this option should not prevent you from

performing part c with the same expression.

c$.$ Convert a fully parenthesized expression to post$-$fix notation

i$.$ Only convert if the user inputted an expression, otherwise

indicate that no expression has been entered.

ii$.$ Once you convert the expression to post$-$fix notation, you

should print the post$-$fix notation to the screen. Once the

conversion is finished, the program must require you enter a

new expression if this option is selected again. But selecting

this option should not prevent you from performing part b

with the same expression.

d$.$ Evaluate a post$-$fix notation expression

i$.$ In this option, your program should ask if the user would like

to enter a new post$-$fix expression or use the post$-$fix

expression that was converted in part c$.$

ii$.$ If the user selects to use the post$-$fix expression used in part c$,$

then you need to verify that there is an expression to evaluate,

otherwise print an error message.

iii. If the user selects to enter a new post$-$fix expression then make

sure that it is entered correctly, you have to do this manually,

no need to program the verification process.

e$.$ Quit

$2.$ The menu$-$driven interface should be an infinite loop that will only quit if the

user Quits the program, otherwise it should keep asking the user to select an

option. stack driver file import java.util.Scanner;

public class StackDriver

$\{$public static void main$($String $[]$args$)$

$\{$ Scanner in $=$ new Scanner$($System$.$in$)$;

System.out.print$("$Enter any parenthesized expression: $")$;String s $=$ in$.$nextLine$()$;

if$($isLegal$($s$))\{$

System.out.println$($s $+"$ is a legal parenthesization"$)$;

evaluateExpr$($s$)$;

$\}$else

System.out.println$($s $+"$ is a not legal parenthesization"$)$;

$\}$public static boolean isLegal$($String str$)$

$\{$int i;

ListStack s $=$ new ListStack$()$;

for$($i $=0$; i $<$ str$.$length$()$; i$++)$

if$($str$.$charAt$($i$)==\text{'}(\text{'})$

s$.$push$(\text{'}(\text{'})$;

else if$($str$.$charAt$($i$)==\text{'})\text{'})$

s$.$pop$()$;

return s$.$isEmpty$()$;

$\}$public static void evaluateExpr$($String str$)$

$\{$ int i;

ListStack s$1=$ new ListStack$()$;

ListStack s$2=$ new ListStack$()$;

for$($i $=0$; i $<$ str$.$length$()$; i$++)\{$

if$($Character$.$isDigit$($str$.$charAt$($i$)))$

s$1.$push$(($int$)($str$.$charAt$($i$)-\text{'}0\text{'}))$;

else if$($str$.$charAt$($i$)==\text{'}+\text{'}||$ str$.$charAt$($i$)==\text{'}-\text{'}||$

str$.$charAt$($i$)==\text{'}*\text{'}||$ str$.$charAt$($i$)==\text{'}/\text{'}||$

str$.$charAt$($i$)==\text{'}\%\text{'})$

s$2.$push$($str$.$charAt$($i$))$;

else if$($str$.$charAt$($i$)==\text{'})\text{'})\{$

int opnd$1,$ opnd$2$;

char oper $=$ s$2.$topAndPop$()$;

opnd$2=$ s$1.$topAndPop$()$;

opnd$1=$ s$1.$topAndPop$()$;

switch$($oper$)\{$

case $\text{'}+\text{'}$:

s$1.$push$($opnd$1+$ opnd$2)$;

break;

case $\text{'}-\text{'}$:

s$1.$push$($opnd$1-$ opnd$2)$;

break;

case $\text{'}*\text{'}$:

s$1.$push$($opnd$1*$ opnd$2)$;

break;

case $\text{'}/\text{'}$:

s$1.$push$($opnd$1/$ opnd$2)$;

break;

case $\text{'}\%\text{'}$:

s$1.$push$($opnd$1\%$ opnd$2)$;

break;$\}$ System.out.println$("$The result of the expression is: $"+$ s$1.$topAndPop$())$; liststack file public class ListStack

$\{$public ListStack$()$

$\{$ topOfStack $=$ null;

$\}$public boolean isEmpty$()$

$\{$ return topOfStack $==$ null;

$\}$public void makeEmpty$()$

$\{$ topOfStack $=$ null;

$\}$public void push$($ AnyType x $)$

$\{$ topOfStack $=$ new ListNode$($ x$,$ topOfStack $)$;$\}$public void pop$()$

$\{$ if$($ isEmpty$())$ throw new UnderflowException$($ "ListStack pop" $)$;

topOfStack $=$ topOfStack.next;

$\}$public AnyType top$()$

$\{$ if$($ isEmpty$())$throw new UnderflowException$($ "ListStack top" $)$;return topOfStack.element;

$\}$public AnyType topAndPop$()$

$\{$if$($ isEmpty$())$throw new UnderflowException$($ "ListStack topAndPop" $)$;AnyType topItem $=$ topOfStack.element;

topOfStack $=$ topOfStack.next;returntopItem;$\}$privateListNodetopOfStack;$\}$ listnode file class ListNode $\{$ public ListNode$($ AnyType theElement $)\{$ this$($ theElement, null $)$; $\}$ public ListNode$($ AnyType theElement, ListNode n $)\{$ element $=$ theElement;next $=$ n;$\}$ public AnyType element;public ListNodenext;$\}$