Readme.txt

- Please see project requirements in InfixExpressionEvaluator.java

- Specification

Taken from Project 4, Chapter 5, Page 177

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

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

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();

}

}

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

QuickTest.java

import java.util.*;

public class QuickTest

{

public static void main(String[] args)

{

InfixExpressionEvaluator expr = new InfixExpressionEvaluator();

expr.quickTest();

} // end main

}

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

UserInputTest.java

import java.util.*;

public class UserInputTest

{

public static void main(String[] args)

{

InfixExpressionEvaluator expr = new InfixExpressionEvaluator();

expr.setupVariables();

expr.evaluate();

} // end main

}