CSCI 162 — Lab 6

Due: Sunday November 04, 2018 @ 11:59PM

Postfix Evaluator

Handout Code is available HERE

Goals

Overview

For this assignment, you'll build a postfix expression evaluator class (PostfixEvaluator). This class will use a stack to hold the numbers. You can interact with your code through an applet that calls it. There are also JUnit tests which your program needs to pass.

You do NOT write the stack, the token scanner, the applet, or the JUnit tests. You write the expression evaluator class from scratch. There are several supporting files in the handout file.

Specification

Create a PostfixEvaluator class that has a public static evaluate method. That method takes in a String as input and returns the String result of evaluating the input as a postfix expression. Use the algorithm we've discussed in class and in the book.

For example, an expression of

15 4 * 24 - 0.5 * 100 3 7 + / *

should result in 180.0.

You must use a Stack of Double in your evaluation.

Input numbers can be real numbers (normal notation) but may NOT be negative. The result may be negative.

Allowed operations are addition(+), subtraction(-), multiplication(*), and division(/). Any other operator should cause an error message to be printed.

The evaluate method returns a string. That string is the value of the postfix expression if it is well-formed and leaves the stack empty. If there are extra values on the stack, the method returns an error message which may include the result but must note that it is not valid.

If an exception occurs, your code should catch it and return a string describing the problem. Your program should not throw any exceptions. Your messages should be very similar to the following.

Unusual or exceptional condition Message
input string is empty or all spaces or tabs No input.
EmptyStackException Stack Underflow. Not enough operands on stack.
ArithmeticException Infinity
values remain on stack after end of input Computed answer, but values remain on stack.
evaluation ended before end of input Computed answer, but not all input used.
parentheses in input ( has no meaning here

Implementation Details

The PostfixEvaluator class does not have a constructor and does not create any instances. It does not have instance variables. It has a public static evaluate method that takes in a String and returns a String as noted above.

In your solution you want to have a private static method (not visible outside the class) that takes a stack and the Character operator and performs the operation. Any exceptions raised in that method are handled in the evaluate method. If you use a switch statement remember the "break" statements.

You are provided TokenScanner and Token classes you must use. Do NOT modify them. They have Javadoc comments. The TokenScanner class breaks a string into parts called Tokens. You can ask the Tokens whether they are numbers or operators and handle them appropriately. These classes have Javadoc comments and pages. You may also read the code.

Construct a TokenScanner by passing in a String. The String argument passed in to the evaluate method is what you need to tokenize. Write a loop using hasNextToken and nextToken much as you would for a Scanner.

The Token class is documented and has methods isOperator( ), isNumber( ), numberValue( ), and operatorCharValue( ). Note that Token recognizes left and right parentheses although they are not part of valid postfix expressions. They are valid for infix expressions. There is also information about operator precedence in Token. Ignore it.

Your evaluate method should catch a variety of exceptions. For some of those (NoSuchElementException and ArithmeticException), the action can be return e.getMessage( ). Your code should not let any reasonable exceptions escape; the JUnit tests attempt to raise the exceptions we expect your program to handle. If you pass those tests, the exception handling is okay.

Here is sample code for catching and handling multiple exceptions:

try
{
  // code that we are attempting
}
catch (ExceptionType1 e)
{
  // code that handles the exception
}
catch (ExceptionType2 e)
{
  // code that handles the exception
}

For Example:

try
{
  // some code
}
catch (ArithmeticException e)
{
  // returns the message associated with the exception
  return e.getMessage ();
}
catch (EmptyStackException e)
{
  return "Stack Underflow. Not enough operands on stack.";
}

Ideas for Getting Started

  1. Understand the problem and the many resources you have.
  2. Copy the files and create a project.
  3. Create a PostfixEvaluator class with an evaluate method. Have it return its input as its result.
  4. Run the PostfixApplet.
  5. Write the loop that uses TokenScanner to break the input into Tokens. Look at the Tokens either by printing them to System.out or building a String and returning that.
  6. Keep enhancing until you're done. Be sure to run the JUnit tests to try to uncover bugs.

Submission

Submit this program as Lab 6: Postfix Evaluator

Grading