This is a CSC220 Programming Project #2 (There are some attached files which i w
ID: 3811754 • Letter: T
Question
This is a CSC220 Programming Project #2 (There are some attached files which i will copy paste below)
=============================
- You need to implement LispExpressionEvaluator.java which uses Java API Stack
See project requirements in LispExpressionEvaluator.java(given below)
- Use PJ2_Test.java to test correctness of your program
- Compile programs (you are in directory containing Readme file):
javac PJ2/*.java
javac *.java
- Run programs (you are in directory containing Readme file):
// Run main() method tests in LispExpressionEvaluator class
java PJ2.LispExpressionEvaluator
// Run main test program
java PJ2_Test
LispExpressionEvaluator.java( attached file 1 under folder PJ2)
/************************************************************************************
*
* CSC220 Programming Project#2
*
* Due Date: 23:55pm, Wednesday, 4/5/2017
* Upload LispExpressionEvaluator.java to ilearn
*
* Specification:
*
* Taken from Project 7, Chapter 5, Page 178
* I have modified specification and requirements of this project
*
* Ref: http://www.gigamonkeys.com/book/ (see chap. 10)
*
* In the language Lisp, each of the four basic arithmetic operators appears
* before an arbitrary number of operands, which are separated by spaces.
* The resulting expression is enclosed in parentheses. The operators behave
* as follows:
*
* (+ a b c ...) returns the sum of all the operands, and (+ a) returns a.
*
* (- a b c ...) returns a - b - c - ..., and (- a) returns -a.
*
* (* a b c ...) returns the product of all the operands, and (* a) returns a.
*
* (/ a b c ...) returns a / b / c / ..., and (/ a) returns 1/a.
*
* Note: + * - / must have at least one operand
*
* You can form larger arithmetic expressions by combining these basic
* expressions using a fully parenthesized prefix notation.
* For example, the following is a valid Lisp expression:
*
* (+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)) (+ 1))
*
* This expression is evaluated successively as follows:
*
* (+ (- 6) (* 2 3 4) (/ 3 1 -2) (+ 1))
* (+ -6 24 -1.5 1)
* 17.5
*
* Requirements:
*
* - Design and implement an algorithm that uses Java API stacks to evaluate a
* valid Lisp expression composed of the four basic operators and integer values.
* - Valid tokens in an expression are '(',')','+','-','*','/',and positive integers (>=0)
* - Display result as floting point number with at 2 decimal places
* - Negative number is not a valid "input" operand, e.g. (+ -2 3)
* However, you may create a negative number using parentheses, e.g. (+ (-2)3)
* - There may be any number of blank spaces, >= 0, in between tokens
* Thus, the following expressions are valid:
* (+ (-6)3)
* (/(+20 30))
*
* - Must use Java API Stack class in this project.
* Ref: http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
* - Must throw LispExpressionEvaluatorException to indicate errors
* - Must not add new or modify existing data fields
* - Must implement these methods :
*
* public LispExpressionEvaluator()
* public LispExpressionEvaluator(String inputExpression)
* public void reset(String inputExpression)
* public double evaluate()
* private void evaluateCurrentOperation()
*
* - You may add new private methods
*
*************************************************************************************/
package PJ2;
import java.util.*;
public class LispExpressionEvaluator
{
// Current input Lisp expression
private String inputExpr;
// Main expression stack & current operation stack
private Stack<Object> inputExprStack;
private Stack<Double> evaluationStack;
// default constructor
// set inputExpr to ""
// create stack objects
public LispExpressionEvaluator()
{
// add statements
}
// constructor with an input expression
// set inputExpr to inputExpression
// create stack objects
public LispExpressionEvaluator(String inputExpression)
{
// add statements
}
// set inputExpr to inputExpression
// clear stack objects
public void reset(String inputExpression)
{
// add statements
}
// This function evaluates current operator with its operands
// See complete algorithm in evaluate()
//
// Main Steps:
// Pop operands from inputExprStack and push them onto
// evaluationStack until you find an operator
// Apply the operator to the operands on evaluationStack
// Push the result into inputExprStack
//
private void evaluateCurrentOperation()
{
// add statements
}
/**
* This funtion evaluates current Lisp expression in inputExpr
* It return result of the expression
*
* The algorithm:
*
* Step 1 Scan the tokens in the string.
* Step 2 If you see an operand, push operand object onto the inputExprStack
* Step 3 If you see "(", next token should be an operator
* Step 4 If you see an operator, push operator object onto the inputExprStack
* Step 5 If you see ")" // steps in evaluateCurrentOperation() :
* Step 6 Pop operands and push them onto evaluationStack
* until you find an operator
* Step 7 Apply the operator to the operands on evaluationStack
* Step 8 Push the result into inputExprStack
* Step 9 If you run out of tokens, the value on the top of inputExprStack is
* is the result of the expression.
*/
public double evaluate()
{
// only outline is given...
// you need to add statements/local variables
// you may delete or modify any statements in this method
// use scanner to tokenize inputExpr
Scanner inputExprScanner = new Scanner(inputExpr);
// Use zero or more white space as delimiter,
// which breaks the string into single character tokens
inputExprScanner = inputExprScanner.useDelimiter("\s*");
// Step 1: Scan the tokens in the string.
while (inputExprScanner.hasNext())
{
// Step 2: If you see an operand, push operand object onto the inputExprStack
if (inputExprScanner.hasNextInt())
{
// This force scanner to grab all of the digits
// Otherwise, it will just get one char
String dataString = inputExprScanner.findInLine("\d+");
// more ...
}
else
{
// Get next token, only one char in string token
String aToken = inputExprScanner.next();
char item = aToken.charAt(0);
switch (item)
{
// Step 3: If you see "(", next token shoube an operator
// Step 4: If you see an operator, push operator object onto the inputExprStack
// Step 5: If you see ")" // steps in evaluateCurrentOperation() :
default: // error
throw new LispExpressionEvaluatorException(item + " is not a legal expression operator");
} // end switch
} // end else
} // end while
// Step 9: If you run out of tokens, the value on the top of inputExprStack is
// is the result of the expression.
//
// return result
return 0.0;
}
//=====================================================================
// DO NOT MODIFY ANY STATEMENTS BELOW
//=====================================================================
// This static method is used by main() only
private static void evaluateExprTest(String s, LispExpressionEvaluator expr, String expect)
{
Double result;
System.out.println("Expression " + s);
System.out.printf("Expected result : %s ", expect);
expr.reset(s);
try {
result = expr.evaluate();
System.out.printf("Evaluated result : %.2f ", result);
}
catch (LispExpressionEvaluatorException e) {
System.out.println("Evaluated result :"+e);
}
System.out.println("-----------------------------");
}
// define few test cases, exception may happen
public static void main (String args[])
{
LispExpressionEvaluator expr= new LispExpressionEvaluator();
String test1 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)) (+ 0))";
String test2 = "(+ (- 632) (* 21 3 4) (/ (+ 32) (* 1) (- 21 3 1)) (+ 0))";
String test3 = "(+ (/ 2) (* 2) (/ (+ 1) (+ 1) (- 2 1 )) (/ 1))";
String test4 = "(+ (/2)(+ 1))";
String test5 = "(+ (/2 3 0))";
String test6 = "(+ (/ 2) (* 2) (/ (+ 1) (+ 3) (- 2 1 ))))";
String test7 = "(+ (*))";
String test8 = "(+ (- 6) (* 2 3 4) (/ (+ 3) (* 1) (- 2 3 1)) (+ ))";
evaluateExprTest(test1, expr, "16.50");
evaluateExprTest(test2, expr, "-378.12");
evaluateExprTest(test3, expr, "4.50");
evaluateExprTest(test4, expr, "1.50");
evaluateExprTest(test5, expr, "Infinity or LispExpressionEvaluatorException");
evaluateExprTest(test6, expr, "LispExpressionEvaluatorException");
evaluateExprTest(test7, expr, "LispExpressionException");
evaluateExprTest(test8, expr, "LispExpressionException");
}
}
LispExpressionEvaluator.java ( attached file 2 under the folder PJ 2)
/************************************************************************************
*
* Do not modify this file.
*
* LispException class
*
* It is used by LispExpressionEvaluator
*
*************************************************************************************/
package PJ2;
public class LispExpressionEvaluatorException extends RuntimeException
{
public LispExpressionEvaluatorException()
{
this("");
}
public LispExpressionEvaluatorException(String errorMsg)
{
super(errorMsg);
}
}
PJ2_Test.java ( another seperate file given with the project)
import PJ2.*;
import java.util.*;
// Do not modify this file.
//
// Simple test program which allows user to input Lisp expr string
// To terminate: type "exit"
public class PJ2_Test
{
public static void main (String args[])
{
// create a LispExpressionEvaluator object
LispExpressionEvaluator expr= new LispExpressionEvaluator();
// scan input expr string
Scanner scanner;
// current expr string and its result
String inputExpr;
double result;
int i=0;
scanner = new Scanner( System.in ); // scanner for input
do
{
try
{
System.out.print( " input an expression string:" );
// scan next input line
inputExpr = scanner.nextLine();
if (inputExpr.equals("exit"))
break; // loop
i++;
System.out.println("Evaluate expression #"+ i+" :" + inputExpr);
expr.reset(inputExpr);
result = expr.evaluate();
System.out.printf("Result : %.2f ", result);
} // end try
catch ( LispExpressionEvaluatorException e )
{
System.err.printf( " Exception: %s ", e);
} // end catch exception here, continue to next loop
} while ( true ); // end do...while
} // end main
}
Explanation / Answer
Answer:
package PJ2;
//PJ2_TEST
import java.util.Scanner;
public class PJ2_TEST
{
public static void main (String args[])
{
// create a LispExpressionEvaluator object
LispExpressionEvaluator expr= new LispExpressionEvaluator();
// scan input expr string
Scanner scanner;
// current expr string and its result
String inputExpr;
double result;
int i=0;
scanner = new Scanner( System.in ); // scanner for input
do
{
try
{
System.out.print( " input an expression string:" );
// scan next input line
inputExpr = scanner.nextLine();
if (inputExpr.equals("exit"))
break; // loop
i++;
System.out.println("Evaluate expression #"+ i+" :" + inputExpr);
expr.reset(inputExpr);
result = expr.evaluate();
System.out.printf("Result : %.2f ", result);
} // end try
catch (LispExpressionException e )
{
System.err.printf( " Exception: %s ", e);
} // end catch exception here, continue to next loop
} while ( true ); // end do...while
} // end main
}
package PJ2;
public class LinkedStack<T> implements StackInterface<T>
{
// Data fields
private Node<T> topNode; // references the first node in the chain
private int count; // number of data in this stack
public LinkedStack()
{
// add stataments
topNode = null;
count=0;
} // end default constructor
public void push(T newData)
{
// add stataments
Node<T> newNode = new Node<T>(newData, topNode);
topNode = newNode;
count++;
} // end push
public T peek()
{
// add stataments
T top = null;
if (topNode != null)
top = topNode.getData();
return top;
} // end peek
public T pop()
{
// add stataments
T top = peek();
if (topNode != null)
{
topNode = topNode.getNextNode();
count--;
}
return top;
} // end pop
public boolean empty()
{
// add stataments
return topNode == null;
} // end empty
public int size()
{
// add stataments
return count;
} // end isEmpty
public void clear()
{
// add stataments
topNode = null;
count=0;
} // end clear
public String toString()
{
// add stataments
// note: data class in stack must implement toString() method
// return a list of data in Stack, separate them with ','
String result = "[";
Node<T> currentNode=topNode; // references the first node in the chain
while (currentNode != null) {
result = result + currentNode.getData() + ",";
currentNode = currentNode.getNextNode();
}
result = result + "]";
return result;
}
public static void main (String args[])
{
LinkedStack<Integer> s = new LinkedStack<Integer>();
if (s.empty())
System.out.println("OK: stack is empty");
else
System.out.println("Error: stack is not empty");
s.push(10);
s.push(30);
s.push(50);
System.out.println("Push 3 data: 10, 30, 50");
System.out.println("Print stack " + s);
if (s.size() == 3)
System.out.println("OK: stack size is 3");
else
System.out.println("Error: stack size is " + s.size());
if (s.peek() == 50)
System.out.println("OK: peek stack top is 50");
else
System.out.println("Error: peek stack top is " + s.size());
if (!s.empty())
System.out.println("OK: stack is not empty");
else
System.out.println("Error: stack is empty");
System.out.println("Pop 2 data: 50, 30");
s.pop();
System.out.println("Print stack " + s);
int data=s.pop();
System.out.println("Print stack " + s);
if (data == 30)
System.out.println("OK: stack pop data is 30");
else
System.out.println("Error: stack pop data is " + data);
System.out.println("Clear stack");
s.clear();
System.out.println("Print stack " + s);
}
} // end Stack
//LispExpressionException.java
package PJ2;
public class LispExpressionException extends RuntimeException
{
public LispExpressionException()
{
this("");
}
public LispExpressionException(String errorMsg)
{
super(errorMsg);
}
}
//Node.java
package PJ2;
class Node<T>
{
private T data; // entry in stack
private Node<T> next; // link to next node
Node(T aData)
{
this(aData, null);
} // end constructor
Node(T aData, Node<T> nextNode)
{
data = aData;
next = nextNode;
} // end constructor
T getData()
{
return data;
} // end getData
void setData(T aData)
{
data = aData;
} // end setData
Node<T> getNextNode()
{
return next;
} // end getNextNode
void setNextNode(Node<T> nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
//StackInterface.java
package PJ2;
public interface StackInterface<T>
{
/** Gets the current number of data in this stack.
@return the integer number of entries currently in the stack*/
public int size();
/** Adds a new data to the top of this stack.
@param aData an object to be added to the stack */
public void push(T aData);
/** Removes and returns this stack's top data.
@return either the object at the top of the stack or,
if the stack is empty before the operation, null */
public T pop();
/** Retrieves this stack's top data.
@return either the data at the top of the stack or
null if the stack is empty */
public T peek();
/** Detects whether this stack is empty.
@return true if the stack is empty */
public boolean empty();
}
//LispExpressionEvaluator.java
package PJ2;
import java.util.*;
public class LispExpressionEvaluator{
// Current input Lisp expression
private String currentExpr;
// Main expression stack, see algorithm in evaluate()
private LinkedStack<Object> tokensStack;
private LinkedStack<Double> currentOpStack;
// default constructor
// set currentExpr to ""
// create LinkedStack objects
public LispExpressionEvaluator(){
currentExpr="";
tokensStack = new LinkedStack<Object>();
currentOpStack = new LinkedStack<Double>();
}
// constructor with an input expression
// set currentExpr to inputExpression
// create LinkedStack objects
public LispExpressionEvaluator(String inputExpression){
// add statements
currentExpr=inputExpression;
tokensStack = new LinkedStack<Object>();
currentOpStack = new LinkedStack<Double>();
}
// set currentExpr to inputExpression
// clear stack objects
public void reset(String inputExpression)
{
// add statements
if(inputExpression == null)
{
throw new LispExpressionException();
}
currentExpr=inputExpression;
tokensStack.clear();
currentOpStack.clear();
}
// This function evaluates current operator with its operands
// See complete algorithm in evaluate()
//
// Main Steps:
// Pop operands from tokensStack and push them onto
// currentOpStack until you find an operator
// Apply the operator to the operands on currentOpStack
// Push the result into tokensStack
//
private void evaluateCurrentOperation(){
double result=0;
if(tokensStack.empty() ){
throw new LispExpressionException("Error, the stack is empty");
}
Object oper = tokensStack.pop();
while ( oper instanceof String ) {
double value = Double.parseDouble(String.valueOf(oper));
currentOpStack.push(value);
if(tokensStack.empty() ){
throw new LispExpressionException("Error1");
}
else{
oper = tokensStack.pop();
}
}
try{
String aToken = oper.toString() ;
char item = aToken.charAt(0);
switch (item) {
case '+':
if(currentOpStack==null || currentOpStack.empty()){
throw new LispExpressionException("error.add");
}
while (!currentOpStack.empty() ) {
result += currentOpStack.pop();
}
tokensStack.push(String.valueOf(result));
break;
case '-':
if(currentOpStack==null || currentOpStack.empty()){
throw new LispExpressionException("error.sub");
}
result = currentOpStack.pop();
if (currentOpStack.empty()) {
result = -result;
tokensStack.push(String.valueOf(result));
}
else {
while(!currentOpStack.empty()) {
result -= currentOpStack.pop();
}
tokensStack.push(String.valueOf(result));
}
break;
case '*':
if(currentOpStack==null || currentOpStack.empty()){
throw new LispExpressionException("error.mult");
}
result = 1;
while ( !currentOpStack.empty() ) {
result *= currentOpStack.pop();
}
tokensStack.push(String.valueOf(result));
break;
case '/':
if(currentOpStack==null || currentOpStack.empty()){
throw new LispExpressionException("error.div");
}
result = currentOpStack.pop();
if (currentOpStack.empty()) {
result = 1/result;
tokensStack.push(String.valueOf(result));
}
else {
while(!currentOpStack.empty()) {
result /=currentOpStack.pop();
}
tokensStack.push(String.valueOf(result));
}
break;
case '(':
default:
throw new LispExpressionException(item + " is not a legal expression operator");
}
}
catch ( LispExpressionException e){
throw new LispExpressionException( e.getMessage());
}
}
/**
* This funtion evaluates current Lisp expression in currentExpr
* It return result of the expression
*
* The algorithm:
*
* Step 1 Scan the tokens in the string.
* Step 2 If you see an operand, push operand object onto the tokensStack
* Step 3 If you see "(", next token should be an operator
* Step 4 If you see an operator, push operator object onto the tokensStack
* Step 5 If you see ")" // steps in evaluateCurrentOperation() :
* Step 6 Pop operands and push them onto currentOpStack
* until you find an operator
* Step 7 Apply the operator to the operands on currentOpStack
* Step 8 Push the result into tokensStack
* Step 9 If you run out of tokens, the value on the top of tokensStack is
* is the result of the expression.
*/
public double evaluate(){
Scanner currentExprScanner = new Scanner(currentExpr);
currentExprScanner = currentExprScanner.useDelimiter("\s*");
while (currentExprScanner.hasNext()){
if (currentExprScanner.hasNextInt()){
String dataString = currentExprScanner.findInLine("\d+");
tokensStack.push(dataString);
}
else{
try{
String aToken = currentExprScanner.next();
char item = aToken.charAt(0);
switch (item){
case '(':
aToken = currentExprScanner.next();
item = aToken.charAt(0);
switch (item){
case '+':
tokensStack.push(item);
break;
case '-':
tokensStack.push(item);
break;
case '*':
tokensStack.push(item);
break;
case '/':
tokensStack.push(item);
break;
default:
throw new LispExpressionException(item + " is not a legal expression operator");
}
break;
case ')':
evaluateCurrentOperation();
break;
default:
throw new LispExpressionException(item + " is not a legal expression operator");
} // end switch
}//end try
catch ( LispExpressionException e){
throw new LispExpressionException( e.getMessage());
}//end catch
} // end else
} // end while
double result= Double.parseDouble(String.valueOf(tokensStack.pop()));
if (!tokensStack.empty()){
throw new LispExpressionException ("This stack still has values, but there is no operand");
}
return result;
}
// This static method is used by main() only
private static void evaluateExprTest(String s, LispExpressionEvaluator expr, String expect)
{
Double result;
System.out.println("Expression " + s);
System.out.printf("Expected result : %s ", expect);
expr.reset(s);
try {
result = expr.evaluate();
System.out.printf("Evaluated result : %.2f ", result);
}
catch (LispExpressionException e) {
System.out.println("Evaluated result :"+e);
}
System.out.println("-----------------------------");
}
// define few test cases, exception may happen
public static void main (String args[])
{
LispExpressionEvaluator expr= new LispExpressionEvaluator();
//expr.setDebug();
String test1 = "(+ (- 6) ( 2 3 4) (/ (+ 3) ( 1) (- 2 3 1)) (+ 1))";
String test2 = "(+ (- 632) ( 21 3 4) (/ (+ 32) ( 1) (- 21 3 1)) (+ 0))";
String test3 = "(+ (/ 2) ( 2) (/ (+ 1) (+ 1) (- 2 1 ))( 1))";
String test4 = "(+ (/2)(+ 1))";
String test5 = "(+ (/2 3 0))";
String test6 = "(+ (/ 2) (* 2) (/ (+ 1) (+ 3) (- 2 1 ))))";
String test7 = "(+ (*))";
String test8 = "(+ (- 6) ( 2 3 4) (/ (+ 3) ( 1) (- 2 3 1)) (+ ))";
evaluateExprTest(test1, expr, "17.50");
evaluateExprTest(test2, expr, "-378.12");
evaluateExprTest(test3, expr, "4.50");
evaluateExprTest(test4, expr, "1.5");
evaluateExprTest(test5, expr, "Infinity or LispExpressionException");
evaluateExprTest(test6, expr, "LispExpressionException");
evaluateExprTest(test7, expr, "LispExpressionException");
evaluateExprTest(test8, expr, "LispExpressionException");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.