You will only need to complete two methods in InfixExpressionEvaluator class: pr
ID: 3702026 • Letter: Y
Question
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<E>
- 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 <name,value> pairs
// Do not modify!
Map<Character,Double> 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<Character> 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<Double> 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
}
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Explanation / Answer
I am only providing method body of the methods asked.
int precedence(char c){
if(c=='+' || c=='-')return 1;
if(c=='*' || c=='/')return 2;
return -1;
}
private String convertToPotfix(String infix){
/**
Map<Character,Integer> precedence = new HashMap<>();
precedence.put('+',1);
precedence.put('-',1);
precedence.put('*',2);
precedence.put('/',2);
**/
Stack<Character> S=new Stack<>();
StringBuilder postfix=new StringBuilder();
for(int i=0;i<infix.length();i++) {
char ch=infix.charAt(i);
if(ch=='(') {
S.push(ch);
}else if(ch==')') {
while(!S.empty()) {
char symbol=S.pop();
if(symbol=='(')break;
postfix.append(symbol);
}
}else if(checkValidOperator(ch)) {
//ch is an operator
while(!S.empty() && S.peek()!='(') {
if(precedence(ch)<=precedence(S.peek())) {
char symbol=S.pop();
postfix.append(symbol);
}else {
break;
}
}
S.push(ch);
}else if(checkValidVariable(ch)) {
postfix.append(ch);
}
}
while(!S.empty()) {
postfix.append(S.pop());
}
return postfix.toString();
}
private double evaluatePostfix (String postfix){
Stack<Double> S=new Stack<>();
for(int i=0;i<postfix.length();i++) {
char ch=postfix.charAt(i);
if(checkValidVariable(ch)) {
//operand
S.push(getVariableValue(ch));
}else if(checkValidOperator(ch)) {
double y=S.pop();
double x=S.pop();
switch (ch)
{
case '+':S.push(x+y);break;
case '*':S.push(x*y);break;
case '-':S.push(x-y);break;
case '/':S.push(x/y);break;
}
}
}
return S.pop();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.