Homework SourseDo not modify this file LispExpressionException It is
/************************************************************************************
*
* Do not modify this file.
*
* LispExpressionException
*
* It is used by LispExpressionEvaluator
*
*************************************************************************************/
LispExpressionException
package PJ2;
public class LispExpressionException extends RuntimeException
{
public LispExpressionException()
{
this(\"\");
}
public LispExpressionException(String errorMsg)
{
super(errorMsg);
}
}
--------------------------------------------------------------------------------------------------
LispExpressionEvaluator
*
* 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.0)
* 17.5
*
* Requirements:
*
* - Design and implement an algorithm that uses SimpleLinkedStack class 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 StackInterface and SimpleLinkedStack in this project.
(*** DO NOT USE Java API Stack class ***)
* - Must throw LispExpressionException to indicate errors
* - Must not add new or modify existing data fields
* - Must implement methods in SimpleLinkedStack class.
* - Must implement these methods in LispExpressionEvaluator class:
*
* public LispExpressionEvaluator()
* public LispExpressionEvaluator(String inputExpression)
* public void reset(String inputExpression)
* public double evaluate()
* private void solveCurrentParenthesisOperation()
*
* - You may add new private methods
*
*************************************************************************************/
package PJ2;
import java.util.*;
public class LispExpressionEvaluator
{
// Current input Lisp expression
private String currentExpression;
// Main expression stack, see algorithm in evaluate()
private StackInterfaceallTokensStack;
private StackInterface currentOperandsStack;
// default constructor
// set currentExpression to \"\"
// create stack objects
public LispExpressionEvaluator()
{
// add statements
}
// constructor with an input expression
// set currentExpression to inputExpression
// create stack objects
public LispExpressionEvaluator(String inputExpression)
{
// add statements
}
// set currentExpression 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 allTokensStack and push them onto
// currentOperandsStack until you find an operator
// Apply the operator to the operands on currentOperandsStack
// Push the result into allTokensStack
//
private void solveCurrentParenthesisOperation()
{
// add statements
}
/**
* This funtion evaluates current Lisp expression in currentExpression
* 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 allTokensStack
* Step 3 If you see \"(\", next token should be an operator
* Step 4 If you see an operator, push operator object onto the allTokensStack
* Step 5 If you see \")\" // steps in solveCurrentParenthesisOperation() :
* Step 6 Pop operands and push them onto currentOperandsStack
* until you find an operator
* Step 7 Apply the operator to the operands on currentOperandsStack
* Step 8 Push the result into allTokensStack
* Step 9 If you run out of tokens, the value on the top of allTokensStack 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 currentExpression
Scanner currentExpressionScanner = new Scanner(currentExpression);
// Use zero or more white space as delimiter,
// which breaks the string into single character tokens
currentExpressionScanner = currentExpressionScanner.useDelimiter(\"\\\\s*\");
// Step 1: Scan the tokens in the string.
while (currentExpressionScanner.hasNext())
{
// Step 2: If you see an operand, push operand object onto the allTokensStack
if (currentExpressionScanner.hasNextInt())
{
// This force scanner to grab all of the digits
// Otherwise, it will just get one char
String dataString = currentExpressionScanner.findInLine(\"\\\\d+\");
// more ...
}
else
{
// Get next token, only one char in string token
String aToken = currentExpressionScanner.next();
//System.out.println(\"Other: \" + aToken);
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 allTokensStack
// Step 5: If you see \")\" // steps in solveCurrentParenthesisOperation() :
default: // error
throw new LispExpressionException(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 allTokensStack is
// is the result of the expression.
//
// return result
return 0.0; // return the correct result
}
//=====================================================================
// 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 (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\");
}
}
Stack interface -
/**
An interface for the ADT stack.
Do not modify this file
*/
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();
/** Removes all data from this stack */
public void clear();
} // end StackInterface
/**
An interface for the ADT stack.
Do not modify this file
*/
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();
/** Removes all data from this stack */
public void clear();
} // end StackInterface
simplelinkedstack.java
/**
A class of stacks whose entries are stored in a chain of nodes.
Implement all methods in SimpleLinkedStack class using
the inner Node class.
Main Reference : text book or class notes
Do not change or add data fields
Do not add new methods
You may access Node object fields directly, i.e. data and next
*/
package PJ2;
public class SimpleLinkedStack<T> implements StackInterface<T>
{
// Data fields
private Node topNode; // references the first node in the chain
private int count; // number of data in this stack
public SimpleLinkedStack()
{
// add stataments
} // end default constructor
public void push(T newData)
{
// add stataments
} // end push
public T peek()
{
// add stataments
return null;
} // end peek
public T pop()
{
// add stataments
return null;
} // end pop
public boolean empty()
{
// add stataments
return false;
} // end empty
public int size()
{
// add stataments
return -1;
} // end isEmpty
public void clear()
{
// add stataments
} // 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 \',\'
return \"\";
}
/****************************************************
private inner node class
Do not modify this class!!
you may access data and next directly
***************************************************/
private class Node
{
private T data; // entry in list
private Node next; // link to next node
private Node (T dataPortion)
{
data = dataPortion;
next = null; // set next to NULL
} // end constructor
private Node (T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode; // set next to refer to nextNode
} // end constructor
} // end Node
/****************************************************
Do not modify: Stack test
****************************************************/
public static void main (String args[])
{
System.out.println(\"\ \"+
\"*******************************************************\ \"+
\"Sample Expected output:\ \"+
\"\ \"+
\"OK: stack is empty\ \"+
\"Push 3 data: 10, 30, 50\ \"+
\"Print stack [50,30,10,]\ \"+
\"OK: stack size is 3\ \"+
\"OK: peek stack top is 50\ \"+
\"OK: stack is not empty\ \"+
\"Pop 2 data: 50, 30\ \"+
\"Print stack [30,10,]\ \"+
\"Print stack [10,]\ \"+
\"OK: stack pop data is 30\ \"+
\"Clear stack\ \"+
\"Print stack []\ \"+
\"\ \"+
\"*******************************************************\");
System.out.println(\"\ Your Test output:\ \");
StackInterface<Integer> s = new SimpleLinkedStack<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
Solution
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#define Max 20
int st[Max], top=-1;
void push(int ch)
{
if (top == Max-1)
{
printf(\"Stack is full\ \");
}
else
{
top++;
st[top]=ch;
}
}
int pop()
{
int ch;
if (top==-1)
{
printf(\"Stack is empty\ \");
}
else
{
ch=st[top];
top--;
}
return ch;
}
void dispstack()
{
int k;
printf(\"stack Content: \");
for (k=top; k>=0; k--)
{
printf(\"%d, \", st[k]);
}
printf(\"\ \");
}
int PreEval(char s[25])
{
char temp[25];
int i,val=0,ch1,ch2,j=0;
i=0; top=-1;
while (s[i]!=\'\\0\')
{
/*if operand is countered print it*/
if ( (s[i]>=48 && s[i]<=57) )
{
j=0;
temp[j]=s[i];
j++;
temp[j]=\'\\0\';
push(atoi(temp));
}
else
{
ch2=pop();
ch1=pop();
switch(s[i])
{
case \'+\' :{
val=ch2+ch1;
break;
}
case \'-\' :{
val=ch2-ch1;
break;
}
case \'*\' :{
val=ch2*ch1;
break;
}
case \'/\' :{
val=ch2/ch1;
break;
}
}
push(val);
}
i++;
}
val=pop();
return val;
}
void main()
{
char s[25],s1[25];
int val;
clrscr();
printf(\"enter a Prefix expression for evaluation\ \");
scanf(\"%s\",s);
strcpy(s1,strrev(s));
val= PreEval(s1);
printf(\"Value of Prefix Expression=%d\ \", val);
getch();
}
