Expression evaluation using stacks

In this homework assignment, you will be implementing an expression evaluator that evaluates

arithmetic expressions consisting of operations $+,-,*,/,**,\%$ and number operands.

For example $2+4*3\mathrm{.}1$ should be evaluated as $2+(4*3\mathrm{.}1)$ instead of $(2+4)*3\mathrm{.}1$ since $*$ has a

higher precedence than $+.$

We will first convert the given infix expression to the postfix expression which can then be

evaluated easily using a stack. You need to use operator precedence rules to arrive at the unique

postfix expression that can be evaluated in one way.

For example $2+4*3\mathrm{.}1$ should be converted to $243\mathrm{.}1*+$ since $*$ has a higher precedence than

$+.$ In general, $**$ has highest precedence followed by $*,/($which have equal precedence$)$ and then

followed by $+,-($which have equal precedence$).$ In case of operators with equal precedence, we

use left$-$to$-$right order of evaluation. For example $2/4*3\mathrm{.}1$ should be converted to $24/3\mathrm{.}1*.$

You can force order of evaluation using parentheses which may be nested. For example, $(4*(3-$

$2))**-2$ should be converted to $432-*-2**.$

You are provided a starter file for ExpressionEvaluator.java. You also need to download the

following files : ExpressionToken.java, OperatorToken.java, OperandToken.java. You will

be completing the following functions in ExpressionEvaluator.java.

Do not change classes OperatorToken.java, OperandToken.java or any of the function

signatures or the class name in ExpressionEvaluator.java. Note that the function should throw

an exception for an invalid expression as indicated in the Javadoc for the function.

$/**$

$*$ Convert Infix expression given as a list of operator and operand tokens to

$*$ a postfix expression as a list of operator and operand tokens

$*$ @param infixExpr

$*$ @return

$*$ @throws Exception when the expression is not valid

$*$ such as insufficient number of operators or operands e$.$g$.4*25,4*$

$2+$

$*$ or not having balanced parentheses e$.$g$.(4*(5+3)$

$*/$

public static List convertToPostFix$($List

infixExpr$)$ throws Exception $\{...\}$

$/**$

$*$ Evaluate postfix expression given as a list of operator and operand tokens

$*$ and return the result

$*$ @param postfixExpr

$*$ @return

$*$ @throws Exception when the expression is not valid

$*$ such as insufficient number of operators or operands e$.$g$.452*,4$

$*/$

public static double postFixEval$($List postfixExpr$)$ throws

Exception $\{..\}$

In implementing the convertToPostfix$()$ function, check operator precedence by using the function precedes$()$ of OperatorToken class. For example

if $($currentToken$.$precedes$($topOfStackToken$))\{...\}$

Also Complete evalDirect$()$ function that first parses the infix expression

into tokens as before but then directly evaluates the infix expression instead of converting it into post fix. You will get credit only if all the unit tests pass

Code to edit:

import java.util.ArrayList;

import java.util.List;

import java.util.Stack;

import java.util.Iterator;

public class ExpressionEvaluator $\{$

$//$ Use this function for applying operator in postfixEval$()$

private static double applyOp$($OperatorToken opType, double op$1,$ double op$2)\{$

switch$($opType$)\{$

case ADD:

return op$1+$ op$2$;

case SUBTRACT:

return op$1-$ op$2$;

case MULTIPLY:

return op$1*$ op$2$;

case DIVIDE :

return op$1/$ op$2$;

case MOD :

return op$1\%$ op$2$;

case EXP:

return Math.pow$($op$1,$op$2)$;

default:

return $0\mathrm{.}0$;

$\}$

$\}$

$/**$

$*$ Parse an expression into a list of operator and operand tokens

$*$ @param str

$*$ @return

$*/$

public static List parseExpr$($String str$)\{$

List expr $=$ new ArrayList$<>()$;

String $[]$ strTokList $=$ str$.$split$("\backslash \backslash$s$+")$;

for $($String strTok : strTokList$)\{$

String str$1=$ strTok.trim$()$;

if $($str$1.$isEmpty$())\{$

continue;

$\}$

OperatorToken operToken $=$ OperatorToken.opType$($str$1)$;

expr.add$($operToken $==$ null $?$ new OperandToken$($str$1)$ : operToken$)$;

$\}$

return expr;

$\}$

$/**$

$*$ Convert Infix expression given as a list of operator and operand tokens to

$*$ a postfix expression as a list of operator and operand tokens

$*$ @param infixExpr

$*$ @return

$*$ @throws Exception when the expression is not valid

$*$ such as insufficient number of operators or operands e$.$g$.4*25,4*2+$

$*$ or not having balanced parentheses e$.$g$.(4*(5+3)$

$*/$

public static List convertToPostFix$($List infixExpr$)$ throws Exception $\{$

$/**$

$*$ Complete the code here only for homework.