In this lab you will write a program to read in and evaluate apostfix arithmetic expressionusing a stack, as outlined in class.

Step 1. Create a public class Postfix1 inside Postfix1.java and add a main method. Now write a static method to read in a line of text that is purportedly a postfix arithmetic expression from the console (without prompting), and split it into tokens eliminating white space. The tokens should be placed in an array of Strings. At this stage do not verify that this is a genuine expression. Your method is in effect just reading in a line of tokens and placing them in an array no matter what they are. Your method should have the following signature,

String[] readExpr()

and should return an array whose length is the number of tokens on the line. Now write a method to write the selfsame expression out on one line by itself given the array, with one space between each token. The signature of this method should be as follows

void writeExpr(String[] expr)

Test your methods together to be sure they work.

Now write a method to determine if a string is one of the operators + - * permitted in expressions in this lab. Your method should have the following signature.

boolean isOperator(String s)

Now write a method to check the syntax of a postfix expression represented as an array of Strings. Your method should have the following signature.

boolean checkSyntax(String[] expr)

and should silently return true if all array entries are either valid operators (tested with the isOperator method) or can be converted to doubles. Otherwise an error message of the form exemplified as follows should be output and false returned. Use writeExpr to output the expression in such a message.

1.0 2.0 + 3.2 9.1 / 15 *                  ^

Not a number or valid operator.

The caret should indicate the first character of the offending token. Write a main method that reads in an expression and runs checkSyntax on it, and if the syntax is correct prints out the expression using writeExpr followed by a second line of "Syntax correct".

Step 2.Copy Postfix1.java to Postfix2.java, renaming the public class suitably. Write a (not public) class DoubleStack in Postfix2.java to represent a stack of numbers of type double. You may assume that not more that 1000 numbers will be placed upon a DoubleStack. Your stack should be implemented as discussed at length in class, as an integer indicating how many numbers are currently on the stack, along with an array the initial part of which contains the numbers on the stack. Your stack should implement the usual methods for a stack with the following signatures.

DoubleStack() //constructor for a new empty stack

boolean empty() //whether the stack is empty

double pop() //remove and return the top element; throw an error if empty

void push(double x) //add x to the top of the stack

Now modify the main method in Postfix2.java to read a postfix expression from the console on one line, and if its syntax is incorrect act as in step 1. Otherwise either print out its value on a line by itself, or one of the error messages below as appropriate. Note that the message "Syntax correct" is not wanted in this step. Your new main method should use a DoubleStack along with the machinery you created in step 1 to do this.

Specifically, the expression should be evaluated as discussed in class, by iterating through the sequence of numbers and operators; when a number is encountered push it onto the stack and when an operator is encountered, first pop its right operand off the stack, then pop its left operand off the stack, combine these two with the operator, and push the result back on the stack. The result should be a single number on the stack.

If an operation is attempted and there are not at least two numbers on the stack to combine then print out a message in the following form.

Too few operands for +

1.0 2.0 * + 4.3 +

          ^

The caret should indicate the position of the offending operator inside the entire expression. If the stack contains more than one number when expression evaluation is complete then print out the following message.

Too few operators to produce a single result.