The main goal of Lab 10 is to enhance the students' understanding of stack operations by implementing a program to evaluate fully parenthesized Boolean expressions.
// FILE: BasicCalc.java
// This program reads a reads and evaluates a fully parenthesized arithmetic expression.
// The purpose is to illustrate a fundamental use of stacks.
//import edu.colorado.collections.CharStack;
//import edu.colorado.collections.DoubleStack;
//import edu.colorado.io.EasyReader; // From Appendix B
public class BasicCalc
{
public static void main(String[ ] args)
{
EasyReader stdin = new EasyReader(System.in);
double answer;
System.out.println("Type a fully parenthesized arithmetic expression:");
answer = readAndEvaluate(stdin);
System.out.println("That evaluates to " + answer);
}
public static double readAndEvaluate(EasyReader input)
// Precondition: The next line of characters in the EasyReader is a fully
// parenthesized arithmetic expression formed from non-negative numbers,
// parentheses, and the four operations +, -, *, and /.
// Postcondition: A line has been read from the EasyReader, including the
// newline character. This line has been evaluated and the value returned.
// Exceptions: Can throw an IllegalArgumentException if the input line is an
// illegal expression, such as unbalanced parentheses or a division by zero.
// However, some illegal expressions are not caught by this implementation.
{
final char DECIMAL = '.';
final char RIGHT_PARENTHESIS = ')';
final String SYMBOLS = "+-*/";
DoubleStack numbers = new DoubleStack( );
CharStack operations = new CharStack( );
while (!input.isEOLN( ))
{
if (Character.isDigit(input.peek( )) || (input.peek( ) == DECIMAL))
{ // Read a number and push it on the numbers stack.
numbers.push(input.doubleInput( ));
}
else if (SYMBOLS.indexOf(input.peek( )) >= 0)
{ // Read the + - * or / symbol and push it on the operations stack.
operations.push(input.charInput( ));
}
else if (input.peek( ) == RIGHT_PARENTHESIS)
{ // Evaluate the stuff on top of the stacks.
input.ignore( );
evaluateStackTops(numbers, operations);
}
else
{ // Just read and ignore all other characters.
input.ignore( );
}
}
input.skipLine( ); // Read and ignore the newline character.
if (numbers.size( ) != 1)
throw new IllegalArgumentException("Illegal input expression");
return numbers.pop( );
}
public static void evaluateStackTops(DoubleStack numbers, CharStack operations)
// Precondition: The top of the operations stack contains +, -, *, or /, and
// the numbers stack contains at least two numbers.
// Postcondition: The top two numbers have been popped from the numbers stack, and the
// top operation has been popped from the operations stack. The two numbers have been
// combined using the operation (with the second number popped as the left operand).
// The result of the operation has then been pushed back onto the numbers stack.
// Exceptions: Throws an IllegalArgumentException if the stacks are illegal or if the
// operation results in a division by zero.
{
double operand1, operand2;
// Check that the stacks have enough items, and get the two operands.
if ((numbers.size( ) < 2) || (operations.isEmpty( )))
throw new IllegalArgumentException("Illegal expression");
operand2 = numbers.pop( );
operand1 = numbers.pop( );
// Carry out an action based on the operation on the top of the stack.
switch (operations.pop( ))
{
case '+': numbers.push(operand1 + operand2);
break;
case '-': numbers.push(operand1 - operand2);
break;
case '*': numbers.push(operand1 * operand2);
break;
case '/': if (operand2 == 0)
throw new IllegalArgumentException("Division by zero");
numbers.push(operand1 / operand2);
break;
default: throw new IllegalArgumentException("Illegal operation");
}
}
}
CharStack.java:
// File: CharStack.java from the package edu.colorado.collections
// Complete documentation is available from the CharStack link in:
// http://www.cs.colorado.edu/~main/docs/
//package edu.colorado.collections;
import java.util.EmptyStackException;
/******************************************************************************
* A CharStack is a stack of char values.
*
* ensureCapacity, push,
* and trimToSize will result in an
* OutOfMemoryError when free memory is exhausted.
* Integer.MAX_VALUE). Any attempt to create a larger capacity
* results in a failure due to an arithmetic overflow.
* push method works efficiently (without needing more
* memory) until this capacity is reached.
* @param - none
* new char[10].
**/
public CharStack( )
{
final int INITIAL_CAPACITY = 10;
manyItems = 0;
data = new char[INITIAL_CAPACITY];
}
/**
* Initialize an empty stack with a specified initial capacity. Note that the
* push method works efficiently (without needing more
* memory) until this capacity is reached.
* @param initialCapacity
* the initial capacity of this stack
* initialCapacity is non-negative.
* new char[initialCapacity].
**/
public CharStack(int initialCapacity)
{
if (initialCapacity < 0)
throw new IllegalArgumentException
("initialCapacity too small " + initialCapacity);
manyItems = 0;
data = new char[initialCapacity];
}
/**
* Generate a copy of this stack.
* @param - none
* @return
* The return value is a copy of this stack. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to a CharStack before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
public Object clone( )
{ // Clone a CharStack.
CharStack answer;
try
{
answer = (CharStack) super.clone( );
}
catch (CloneNotSupportedException e)
{
// This exception should not occur. But if it does, it would probably indicate a
// programming error that made super.clone unavailable. The most comon error
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
answer.data = (char [ ]) data.clone( );
return answer;
}
/**
* Change the current capacity of this stack.
* @param minimumCapacity
* the new capacity for this stack
* minimumCapacity.
* If the capacity was already at or greater than minimumCapacity,
* then the capacity is left unchanged.
* @exception OutOfMemoryError
* Indicates insufficient memory for: new char[minimumCapacity].
**/
public void ensureCapacity(int minimumCapacity)
{
char biggerArray[ ];
if (data.length < minimumCapacity)
{
biggerArray = new char[minimumCapacity];
System.arraycopy(data, 0, biggerArray, 0, manyItems);
data = biggerArray;
}
}
/**
* Accessor method to get the current capacity of this stack.
* The push method works efficiently (without needing
* more memory) until this capacity is reached.
* @param - none
* @return
* the current capacity of this stack
**/
public int getCapacity( )
{
return data.length;
}
/**
* Determine whether this stack is empty.
* @param - none
* @return
* true if this stack is empty;
* false otherwise.
**/
public boolean isEmpty( )
{
return (manyItems == 0);
}
/**
* Get the top item of this stack, without removing the item.
* @param - none
* item
* the item to be pushed onto this stack
* Integer.MAX_VALUE will cause the stack to fail with an
* arithmetic overflow.
**/
public void push(char item)
{
if (manyItems == data.length)
{
// Double the capacity and add 1; this works even if manyItems is 0. However, in
// case that manyItems*2 + 1 is beyond Integer.MAX_VALUE, there will be an
// arithmetic overflow and the bag will fail.
ensureCapacity(manyItems*2 + 1);
}
data[manyItems] = item;
manyItems++;
}
/**
* Accessor method to determine the number of items in this stack.
* @param - none
* @return
* the number of items in this stack
**/
public int size( )
{
return manyItems;
}
/**
* Reduce the current capacity of this stack to its actual size (i.e., the
* number of items it contains).
* @param - none
* // File: EasyReader.java from the package edu.colorado.io // Complete documentation is available from the EasyReader link in: // http://www.cs.colorado.edu/~main/docs //package edu.colorado.io; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.InputStream; import java.io.InputStreamReader; import java.io.IOException; import java.io.PushbackReader; /****************************************************************************** * TheEasyReaderobject has a small collection of methods for * reading some primitive data values from an input stream or file. * *Limitations: *
* If anIOExceptionorFileNotFoundExceptionoccurs * during any operation, then the *EasyReaderprints an error message and halts the program. * The exceptions is not passed back to the calling program, * so the calling program does not need to catch any exceptions. * *Example: *
* This example declares anEasyReaderthat is attached to the * keyboard input (System.in). It then uses *doubleQueryto ask the user to enter a double number. The * square of this double number is then printed: *** *
import edu.colorado.io.EasyReader *
... *
EasyReader stdin = new EasyReader(System.in); // Attaches to keyboard *
double d; *
d = stdin.doubleQuery("Please type a double value: "); *
System.out.println("The square of that is: " + d*d); *
EasyReader class includes:
* EasyReader from an
* InputStream, from an InputStreamReader, or from
* a file name. For example, to create an EasyReader from
* System.in:
* EasyReader stdin = new EasyReader(System.in);
* EasyReader so that it reads from an
* InputStream.
* @param in
* an InputStream that this EasyReader
* will read from
* EasyReader has been initialized so that its
* subsequent input comes from the specified InputStream.
* EasyReader stdin = new EasyReader(System.in);
**/
public EasyReader(InputStream in)
{
super(new InputStreamReader(in));
}
/**
* Initialize this EasyReader so that it reads from a
* specified file.
* @param name
* the name of the file that this EasyReader
* will read from
* EasyReader has been initialized so that its
* subsequent input comes from the specified file.
* If the file does not exist, then an error message is printed
* to System.err and the program exits.
* EasyReader stdin = new EasyReader("foo.txt");
**/
public EasyReader(String name)
{
super(makeFileReader(name));
}
/**
* Initialize this EasyReader so that it reads from an
* InputStreamReader.
* @param in
* an InputStreamReader that this EasyReader
* will read from
* - Postcondition:
-
* This
EasyReader has been initialized so that its subsequent
* input comes from the specified InputStreamReader.
**/
public EasyReader(InputStreamReader isr)
{
super(isr);
}
/**
* Read a character from this EasyReader.
* @param - none
* @return
* a character that's been read
* - Note:
* This method reads and throws away whitespace. Then it reads and
* returns the next character. If end-of-file has been reached, then
* it returns ASCII value zero.
**/
public char charInput( )
{
readSpaces( );
return readChar( );
}
/**
* Read a character from a complete line of this
EasyReader.
* @param - none
* @return
* a character that's been read
* - Note:
-
* This method is indentical
charInput() with an added
* activation of skipLine() just before returning.
**/
public char charInputLine( )
{
char answer = charInput( );
skipLine( );
return answer;
}
/**
* Print a prompt, then read and return a character from this
* EasyReader.
* @param prompt
* a prompt to print
* - Postcondition:
-
* The prompt has been printed to
System.out. Then a
* character has been read and returned with charInputLine.
**/
public char charQuery(String prompt)
{
char answer;
System.out.print(prompt);
return charInputLine( );
}
/**
* Read a double number from this EasyReader.
* @param - none
* @return
* a double number that's been read
* String:
* Double.valueOf.
* NumberFormatException
* occurs, then the method returns Double.NaN and an immediate
* activation of isFormatProblem() will return true.
**/
public double doubleInput( )
{
final char POINT = '.';
StringBuffer input = new StringBuffer( );
readSpaces( );
input.append(readSign( ));
input.append(readDigits( ));
if (peek( ) == POINT)
{ // Read the decimal point and fractional part.
input.append(readChar( ));
input.append(readDigits( ));
}
if (Character.toUpperCase(peek( )) == 'E')
{ // Read the E and exponent.
input.append(readChar( ));
input.append(readSign( ));
input.append(readDigits( ));
}
try
{
formatProblem = false;
return Double.valueOf(input.toString( )).doubleValue( );
}
catch (NumberFormatException e)
{
formatProblem = true;
return Double.NaN;
}
}
/**
* Read a double value from a complete line of this EasyReader.
* @param - none
* @return
* a double value that's been read
* doubleInput( ) with an added
* activation of skipLine( ) just before returning.
**/
public double doubleInputLine( )
{
double answer = doubleInput( );
skipLine( );
return answer;
}
/**
* Print a prompt, then read and return a double value from this
* EasyReader.
* @param prompt
* a prompt to print
* System.out. Then a double
* value has been read and returned with doubleInputLine.
* doubleInputLine encounters a format problem, but
* !isEOF(), then the user is prompted to type a new
* input line until a correct double value is provided. If end-of-file
* is reached, then the method returns Double.NaN and
* an immediate activation of isFormatProblem() will return
* true.
**/
public double doubleQuery(String prompt)
{
double answer;
System.out.print(prompt);
answer = doubleInputLine( );
while (formatProblem)
{
System.out.print("Invalid response. Please type a double value: ");
if (isEOF( ))
return Double.NaN;
answer = doubleInputLine( );
}
return answer;
}
private static void handleException(Exception e)
// Print an error message and halt the program.
{
System.err.println("Exception:" + e);
System.err.println("EasyReader will cause program to halt.");
System.exit(0);
}
/**
* Read and discard one character.
* @param - none
* EasyReader.
* @param - none
* @return
* an integer that's been read
* String:
* Integer.parseInt.
* NumberFormatException
* occurs, then the method returns Integer.MIN_VALUE and an
* immediate activation of isFormatProblem() will return true.
**/
public int intInput( )
{
String input = null;
readSpaces( );
input = readSign( ) + readDigits( );
try
{
formatProblem = false;
return Integer.parseInt(input);
}
catch (NumberFormatException e)
{
formatProblem = true;
return Integer.MIN_VALUE;
}
}
/**
* Read an integer from a complete line of this EasyReader.
* @param - none
* @return
* an integer that's been read
* intInput( ) with an added
* activation of skipLine( ) just before returning.
**/
public int intInputLine( )
{
int answer = intInput( );
skipLine( );
return answer;
}
/**
* Print a prompt, then read and return an integer from this
* EasyReader.
* @param prompt
* a prompt to print
* System.out. Then an
* integer has been read and returned with intInputLine.
* intInputLine encounters a format problem, but
* !isEOF(), then the user is prompted to type a new
* input line until a correct int value is provided. If end-of-file
* is reached, then the method returns Integer.MIN_VALUE
* and an immediate activation of isFormatProblem() will return
* true.
**/
public int intQuery(String prompt)
{
int answer;
System.out.print(prompt);
answer = intInputLine( );
while (formatProblem)
{
System.out.print("Invalid response. Please type an integer value: ");
if (isEOF( ))
return Integer.MIN_VALUE;
answer = intInputLine( );
}
return answer;
}
/**
* Determine whether this EasyReader has reached the
* end-of-file.
* @param - none
* @return
* If this EasyReader has reached the end of file
* (reading all characters up to but not including EOF), then the return
* value is true; if an attempt to read causes an IOException,
* then the return value is also
* true; otherwise the return value is false.
*
*
EasyReader stdin = new EasyReader(System.in);
*
int sum = 0;
*
System.out.println("Type one int per line & press ctrl-z to end:");
*
while (!stdin.isEOF( ))
*
sum += stdin.intInputLine( );
*
System.out.println("Total sum: " + sum);
*
**/
public boolean isEOF( )
{
return (readAhead( ) == EOF_VALUE);
}
/**
* Determine whether the next input character is an end-of-line.
* @param - none
* @return
* If the next input character is a newline ('\n') or carriage return
* ('\r'), then the return value is true; if isEOF(), then the
* return value is also true; if an attempt to read causes an
* IOException, then
* the return value is also true; otherwise the return value is false.
**/
public boolean isEOLN( )
{
int next = readAhead( );
return (next == '\n') || (next == '\r') || (next == EOF_VALUE);
}
/**
* Determine whether there was an incorrectly formatted input to the most
* recent input operation.
* @param - none
* @return
* A true return value indicates that the most recent activation of an
* input methods had an IOException OR was given input of the wrong form
* (such as "abc" instead of an integer). Note that the return value is
* applicable to only the MOST RECENT activation of these input methods:
*
*
doubleInput, intInput
*
doubleInputLine, intInputLine
*
doubleQuery, intQuery
*
**/
public boolean isFormatProblem( )
{
return formatProblem;
}
private static FileReader makeFileReader(String name)
// Create and return a FileReader to read from the named file. If the file doesn’t exist then print
// an error message and halt the program.
{
try
{
return new FileReader(name);
}
catch (FileNotFoundException e)
{
handleException(e);
return null;
}
}
/**
* Make the computation pause for a specified number of milliseconds.
* @param milliseconds
* the number of milliseconds to pause
* EasyReader
* (but don't read it).
* @param - none
* @return
* The return value is the next character that will be read from this
* EasyReader. If there is no next character (because of
* the end-of-file marker), then the return value is '\0'.
**/
public char peek( )
{
int next = readAhead( );
if (next == EOF_VALUE)
return ZERO_CHAR;
else
return (char) next;
}
/**
* Print a prompt, then read and return a YES/NO answer from this
* EasyReader.
* @param prompt
* a prompt to print
* stringQuery(prompt) has been called to ask a question
* and read the answer, which is considered true if it begins with
* "Y" or "y" and false if it begins with "N" or "n". If the answer did
* not begin with a lower- or upper-case Y or N, then the process is
* repeated until a correct Yes/No answer is provided. If EOF is reached,
* then false is returned.
**/
public boolean query(String prompt)
{
String answer;
System.out.print(prompt + " [Y or N] ");
answer = stringInputLine( ).toUpperCase( );
while (!answer.startsWith("Y") && !answer.startsWith("N"))
{
System.out.print("Invalid response. Please type Y or N: ");
if (isEOF( ))
return false;
answer = stringInputLine( ).toUpperCase( );
}
return answer.startsWith("Y");
}
private int readAhead( )
// Peek ahead and return the next character (or -1 for EOF).
{
int next = EOF_VALUE;
try
{
next = read( );
if (next == EOF_VALUE)
{
// End-of-file was encountered. We pause 1 second to allow the
// ctrl-z from the keyboard to be processed since it blocks output
// to the screen on some systems.
pause(1000);
}
else
unread(next);
}
catch (IOException e)
{
handleException(e);
}
return next;
}
private char readChar( )
// Read and return the next character (or -1 for EOF).
{
int next = EOF_VALUE;
try
{
next = read( );
if (next == EOF_VALUE)
{
next = ZERO_CHAR;
// End-of-file was encountered. We pause 1 second to allow the
// ctrl-z from the keyboard to be processed since it blocks output
// to the screen on some systems.
pause(1000);
}
}
catch (IOException e)
{
handleException(e);
}
return (char) next;
}
private String readDigits( )
// Read a sequence of digits and return the sequence as a String.
{
StringBuffer buffer = new StringBuffer( );
while (Character.isDigit(peek( )))
buffer.append(readChar( ));
return buffer.toString( );
}
private String readSign( )
// Read a + or - sign (if one is present) and return the read characters as a string.
{
StringBuffer buffer = new StringBuffer(1);
char possibleSign;
possibleSign = peek( );
if ((possibleSign == '-') || (possibleSign == '+'))
buffer.append(readChar( ));
return buffer.toString( );
}
private String readSpaces( )
// Read a sequence of whitespace characters and return the sequence as a String.
{
StringBuffer buffer = new StringBuffer( );
while (Character.isWhitespace(peek( )))
buffer.append(readChar( ));
return buffer.toString( );
}
/**
* Read and discard the rest of the current input line.
* @param - none
* String (up to whitespace) from this
* EasyReader.
* @param - none
* @return
* a String that's been read
* String from a complete line of this
* EasyReader.
* @param - none
* @return
* a String that's been read
* String.
**/
public String stringInputLine( )
{
StringBuffer buffer = new StringBuffer( );
while (!isEOLN( ) && !isEOF( ))
buffer.append(readChar( ));
skipLine( );
return buffer.toString( );
}
/**
* Print a prompt, then read and return a String from this
* EasyReader.
* @param prompt
* a prompt to print
* System.out. Then a
* String has been read and returned with
* stringInputLine.
**/
public String stringQuery(String prompt)
{
System.out.print(prompt);
return stringInputLine( );
}
/**
* A demonstration program.
* To run the demonstration:
* java edu.colorado.io.EasyReader
**/
public static void main(String[ ] args)
{
EasyReader stdin = new EasyReader(System.in);
double d = stdin.doubleQuery("Double: ");
if (stdin.isFormatProblem( ))
System.out.println("A format error resulted in " + d);
else
System.out.println(d + " is a fine double number.");
int i = stdin.intQuery("Int: ");
if (stdin.isFormatProblem( ))
System.out.println("A format error resulted in " + i);
else
System.out.println(i + " is a fine integer.");
String s = stdin.stringQuery("String: ");
if (stdin.isFormatProblem( ))
System.out.println("A format error resulting in " + s);
else
System.out.println('"' + s + '"' + " is a fine String.");
int sum = 0;
System.out.println("Type one int per line & press ctrl-z to end:");
while (!stdin.isEOF( ))
sum += stdin.intInputLine( );
System.out.println("Total sum: " + sum);
}
}