You will only need to complete two methods in InfixExpressionEvaluator class:

private String convertToPostfix(String infix) private double evaluatePostfix (String postfix)

------------------

Readme.txt

- Please see project requirements in InfixExpressionEvaluator.java

- Specification I have modified specification and requirements of this project You will need to complete two methods in InfixExpressionEvaluator class:

private String convertToPostfix(String infix) private double evaluatePostfix (String postfix)

Algorithms are given in InfixExpressionEvaluator class.

- Requirements

- A set of valid variable names (single character) and their corresponding values (double) will be needed - Assume all infix expressions are valid - Valid tokens in an expression are '(',')','+','-','*','/',and valid variable names - Display result as floting point number with at 2 decimal places

- There may be any number of blank spaces, >= 0, in between tokens and any number of parethesis. Thus, the following expressions are valid: ((a + b) - c) (( a+b)) * c / d ((((( a ))))) - Must use Java API java.util.Stack - Must not add new or modify existing data fields - Must not modify exsiting methods and implement only required methods : - You may add new private methods

- Compile and run program javac *.java // Run tests in InfixExpressionEvaluator class java QuickTest java UserInputTest

- Sample Run

================================================================================== $ java QuickTest

Variable table for quick test

Variable table :{A=5.5, B=-4.5, C=90.0, D=-5.0}

Convert infix expression to postfix expression: (A) Equivalent postfix: A

Convert infix expression to postfix expression: (A+(B+C)) Equivalent postfix: ABC++

Convert infix expression to postfix expression: (A*(B+C)) Equivalent postfix: ABC+*

Convert infix expression to postfix expression: (A-(B+C)/D) Equivalent postfix: ABC+D/-

Convert infix expression to postfix expression: A*(B+C-D) Equivalent postfix: ABC+D-*

Convert infix expression to postfix expression: A*B+(C-D)-D*B Equivalent postfix: AB*CD-+DB*-

Evaluate postfix expression: A Result : 5.50

Evaluate postfix expression: ABC++ Result : 91.00

Evaluate postfix expression: ABC+* Result : 470.25

Evaluate postfix expression: ABC+D/- Result : 22.60

Evaluate postfix expression: ABC+D-* Result : 497.75

Evaluate postfix expression: AB*CD-+DB*- Result : 47.75

==================================================================================

$ java UserInputTest

Create Variable Table, please input variable info:

Enter name and value, example: A 3.5 (enter 0 0 to exit) : A 3.5 Enter name and value, example: A 3.5 (enter 0 0 to exit) : B -4 Enter name and value, example: A 3.5 (enter 0 0 to exit) : C 9 Enter name and value, example: A 3.5 (enter 0 0 to exit) : D -5.5 Enter name and value, example: A 3.5 (enter 0 0 to exit) : 0 0

Variable table :{A=3.5, B=-4.0, C=9.0, D=-5.5}

Start to evaluate infix expressions.... Enter a valid infix expression string (enter "exit" to terminate):(((( A )))) Evaluate expression #1 : (((( A )))) Equivalent postfix: A Result : 3.50 Enter a valid infix expression string (enter "exit" to terminate):(A+B)*C/D Evaluate expression #2 : (A+B)*C/D Equivalent postfix: AB+C*D/ Result : 0.82 Enter a valid infix expression string (enter "exit" to terminate):A*B*C/D Evaluate expression #3 : A*B*C/D Equivalent postfix: AB*C*D/ Result : 22.91 Enter a valid infix expression string (enter "exit" to terminate):A+B*C+D Evaluate expression #4 : A+B*C+D Equivalent postfix: ABC*+D+ Result : -38.00 Enter a valid infix expression string (enter "exit" to terminate):((A)+B) Evaluate expression #5 : ((A)+B) Equivalent postfix: AB+ Result : -0.50 Enter a valid infix expression string (enter "exit" to terminate):exit

==================================================================================

The following is the InfixExpressionEvaluator.java:

/** * Implement methods: * private String convertToPostfix(String infix) * private double evaluatePostfix(String postfix) * * Look at algorithms in the methods */

import java.util.*;

public class InfixExpressionEvaluator { // This is a variable table. It contains pairs // Do not modify! Map variableValues = new HashMap<>();

/** Convert a valid infix expression to a postfix expression Must only use variable names as defined in variable table

@param infix : A valid infix expression. @return Equivalent postfix expression */

private String convertToPostfix(String infix) {

/* Task: Convert an infix expression to a postfix expression

Use Stack S to hold operator characters Valid characters are '(',')','+','-','*','/', predefined variable names Use a StringBuffer PE to hold postfix expression

Need to consider : ( & ), precedence of operators and left to right association

Step 1. Process each character ch in infix expression from left to right

switch(ch) { case operand : append to PE; break; case ( : S.push(ch); break; case ) : repeat // loop until ( { symbol = S.pop() if symbol != ( then append to PE else exit loop } break; case operator : get TopSymbol from S if S is not empty while (!S.isEmpty()) and (TopSymbol != () and (precedence(ch) <= precedence(TopSymbol)) { symbol = S.pop() append symbol to PE get TopSymbol from S if S is not empty } S.push(ch) break; } // end switch

Step 2. After scanning the whole infix expression. Append remaining operators in S into PE

while (Stack != empty) { symbol = S.pop(); append symbol to PE }

Return PE.toString() // convert StringBuffer to String

Example : (a*b+c) (d-e*f) == ab*c+def*--

Char Stack PE ( ( a ( a * (* a b (* ab + (+ ab* c (+ ab*c ) ab*c+ - - ab*c+ ( -( ab*c+ d -( ab*c+d - -(- ab*c+d e -(- ab*c+de * -(-* ab*c+de f -(-* ab*c+def ) - ab*c+def*- ab*c+def*-- */

return null; //change it } // end convertToPostfix

/** Evaluates a postfix expression. Must only use variable names as defined in variable table

@param postfix : A valid postfix expression. @return The double result of the postfix expression. */

private double evaluatePostfix(String postfix) { /* Task: Evaluate a postfix expression

Use a Stack S to hold operands Process each character ch in postfix expression from left to right

if a character is an operand : push into S if a character is an operator : pop two operands from S evaluate the result (need to consider +,-,*,/) push the result back to S Final result is in S

Hint: Use getVariableValue(X) to get value of variable X Use checkValidVariable(X) to check if X is a variable Use checkValidOperator(X) to check if X is an operator Example : Let A=2, B=3, C=4, D=5.

Evaluate postfix expr ABC+*D- 234+*5- = 2 * (3+4) 5 = 9

Char Stack 2 2 3 2,3 4 2,3,4 + 2,7 // 3 + 4 * 14 // 2 * 7 5 14,5 - 9 // 14 - 5

Result = 9

*/

return 0.0; // change it } // end evaluatePostfix

// add any additional private methods here...... // ....

//---------------------------------------------------------------- // Do not modify anything below //---------------------------------------------------------------- // Check a character op is a valid operator, i.e. +, -, * or / private boolean checkValidOperator(char op) { return ((op == '+') || (op == '-') || (op == '*') || (op == '/')); }

// Check variable var is defined in variable table private boolean checkValidVariable(char var) { return variableValues.containsKey(var); }

// Retrieve variable values from variable table private double getVariableValue(char var) { return variableValues.get(var).doubleValue(); } // Read variable values into a variable table void setupVariables() { Scanner s = new Scanner(System.in); char var = 'A'; double val = 3.5; System.out.println(" Create Variable Table, please input variable info: "); while (var != '0') { System.out.print("Enter name and value, example: A 3.5 (enter 0 0 to exit) : "); var = s.next().charAt(0); val = s.nextDouble(); if (var == '0') continue; variableValues.put(var, val); } System.out.println(" Variable table :" + variableValues); }

// This starts infix evaluations // Must enter valid infix expressions, otherwise, may get unexpected results // Enter "exit" to terminate loop void evaluate() { Scanner scanner; String inputInfix; String postfix; double result; int i=0;

System.out.println(" Start to evaluate infix expressions...."); scanner = new Scanner( System.in ); // scanner for input do { try { System.out.print( "Enter a valid infix expression string (enter \"exit\" to terminate):" );

// scan next input line inputInfix = scanner.nextLine();

if (inputInfix.equals("exit")) break; // loop

i++; System.out.println(" Evaluate expression #"+ i+" : " + inputInfix); postfix=convertToPostfix(inputInfix); System.out.println(" Equivalent postfix: " + postfix); result =evaluatePostfix(postfix); System.out.printf(" Result : %.2f ", result); } catch (Exception e) { System.out.println(" Exception...."+e.getMessage()); }

} while ( true ); // end do...while }

// Run quick tests void quickTest() { char var = 'A'; double val = 3.5; String inputInfix=null; String postfix=null;

System.out.println(" Variable table for quick test"); variableValues.put('A', 5.5); variableValues.put('B', -4.5); variableValues.put('C', 90.0); variableValues.put('D', -5.0); System.out.println(" Variable table :" + variableValues);

inputInfix="(A)"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

inputInfix="(A+(B+C))"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

inputInfix="(A*(B+C))"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

inputInfix="(A-(B+C)/D)"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

inputInfix="A*(B+C-D)"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

inputInfix="A*B+(C-D)-D*B"; System.out.println(" Convert infix expression to postfix expression: " + inputInfix); System.out.println("Equivalent postfix: " + convertToPostfix(inputInfix));

postfix="A"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

postfix="ABC++"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

postfix="ABC+*"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

postfix="ABC+D/-"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

postfix="ABC+D-*"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

postfix="AB*CD-+DB*-"; System.out.println(" Evaluate postfix expression: " + postfix); System.out.printf("Result : %.2f ", evaluatePostfix(postfix));

variableValues.clear(); }

}

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

*This QuickTest.java is just to test if InfixExpressionEvaluator works, you don't have to modify anything.

QuickTest.java

import java.util.*;

public class QuickTest

{

public static void main(String[] args)

{

InfixExpressionEvaluator expr = new InfixExpressionEvaluator();

expr.quickTest();

} // end main

}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

*This UserInputTest.java is just to test if InfixExpressionEvaluator works, you don't have to modify anything.

UserInputTest.java

import java.util.*;

public class UserInputTest

{

public static void main(String[] args)

{

InfixExpressionEvaluator expr = new InfixExpressionEvaluator();

expr.setupVariables();

expr.evaluate();

} // end main

}

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------