Stack of cups Project 2: Fat Stacks Solved

Description

Operations out of Order

All around the world, mathematicians have forgotten the order of operations. No one can explain this plague that has robbed them of one of the most basic tricks in their mathematical arsenal. As a consequence, all the necessary calculations to maintain the march of commerce and further the cause of science will eventually grind to a halt. You must wield your computer wisdom to save us all.

The Mission

Your program must perform the following actions:

1. Read an expression in infix notation
2. Print a standardized version of the parsed infix expression
3. Convert the expression to postfix and print it out
4. Evaluate the postfix expression and print out the answer

Specification

Your main() method should be in a class called InfixToPostfix. It is expected that you will create additional classes to help manage your stacks and queues.

Input

To perform input properly, you will read in operators and operands using Scanner. An infix expression has the following characteristics: It will start and end with an operand. Between each operand is an operator. The exceptions to this rule are parentheses. You will see a left parenthesis '(' when you expect to see an operand. After the left parenthesis, you will still expect an operand. You will see a right parenthesis ')' when you expect to see an operator. After a right parenthesis, you will still expect to see an operator.

Supported operators include: +, -, *, and /.

If you are a member of the three-person group, you must support % (floating point modulus) as well.

If you are expecting an operand and get something that is not a correctly formatted operand, print Invalid operand. If you are expecting an operator and get something that is not one of the supported operators, print Invalid operator: followed by the symbol in question.

It is highly recommended that you store each operator and operand in an appropriate object. One possibility is that you create two separate classes, Operator and Operand designed to hold each. They may both be subclasses of a Term superclass or interface. Alternatively, you could create a single Termclass capable of holding either an operator or an operand. You will want to read the entire input into a queue that will allow you to review each token of input in order. For output purposes, supporting iteration on the queue makes a lot of sense.

You will have to perform character-by-character input to correctly read in terms. It is probably easiest to read in an entire line with your Scanner object and then cycle through the resulting String one character at a time. Operands can be any legal Java 6 double literal that is not in scientific notation, e.g. 8, +8.4, -8.4, -8.4, 0.0000000004, .51, 2. and so on. In other words, an operand may start with an optional + or -. It may optionally contain a single decimal point which has a sequence of digits 0 through 9 in front of it, behind it, or both. A legal operand must contain at least one digit. You may use the Character.isDigit() method to check to see if a char value is a digit. You should use the Double class to convert a String to a double.

If you are familiar with deterministic finite automata, constructing one can be a great aid to parsing operands.

Standardized Printing

Once you have read all the tokens into a queue or similar data structure, it is simple to print out each value with a single space between them.

For sample input:

(       ( -9+            8.4)     )

The standardized print version is:

( ( -9.0 + 8.4 ) )

Students are often tempted to keep the input in one large String. Doing so is counter-productive. It is much better to parse the data into operands and operators (and put them in a queue) when they are first read. Then, the ugly process of parsing is done once and for all. This standardized printing task is, in part, to force you to do this parsing step once and then store each operand and operator in an appropriate data structure. Doing so makes standardized printing a snap.

Conversion from Infix to Postfix

Using a stack data structure, the conversion from infix to postfix can be done with the following algorithm. The algorithm begins with a full input queue of terms, an empty stack of operators, and an empty output queue of terms.

Process the input queue, one token at a time, applying the appropriate rules depending on what kind of token you get:

• • Operand:
    Add it to the output queue.

 

• • Left Parenthesis:
    Push it onto the operator stack.

 

• • Right Parenthesis:
    Pop off everything from the operator stack and add each operator to the output queue, until you hit a left parenthesis. Then pop off the left parenthesis.

 

• Any Other Operator:
  If the stack is empty, push the new operator onto the stack. If the stack is not empty, compare the precedence of the current operator with the precedence of the operator on the top of the stack. If our operator’s precedence is less than or equal to the top’s precedence, pop the the stack and put the top element into the output queue. Continue doing so until the stack is empty or we reach an operator with a lower precedence than the new operator. Finally, put the new operator on the stack. The precedences start with (, which has the lowest, then + and -, and finally * and /, with the highest. If you are the three-person group, % has the same priority as * and /. The operator ) does not have a precedence.

After all the input has been processed, pop whatever is left in the stack and add it to the output queue. Then print the contents of the output queue.

Evaluating the Postfix Expression

Evaluating the postfix expression requires a stack as well, but this time the stack is made up of operands. Process the postfix expression term by term. If the term is an operand, push it onto the stack. If the term is an operator, pop two operands off the stack and apply the operator to them. Then, push the result back onto the stack. When you have exhausted the input, the final answer should be the only thing left on the stack.

Storing Variables (Three-person Group Only)

If you are in a three-person group, you must also provide the ability to store variables. Unlike the regular program, your program should allow multiple expressions to be entered. You should continue accepting expressions until the user enters quit.

In addition to the normal expressions, you also have to accept assignments. An assignment consists of a variable name followed by an equal sign (=), followed by an expression, as in the following.

Enter infix expression: value1 = 15 - 1
Standardized infix: value1 = 15.0 - 1.0
Postfix expression: value1 = 15.0 1.0 -
Answer: 14.0

Variables do not need declaration and are all effectively of type double. After a variable is assigned, it can appear in future expressions anywhere that an operand could appear. When it appears in an expression, it should be treated as if it contains the value it was most recently assigned. For example, after the previous assignment, the following expression could be evaluated.

Enter infix expression: 2 + value1
Standardized infix: 2.0 + value1
Postfix expression: 2.0 value1 +
Answer: 16.0

Storing a variable and its value requires a symbol table, map, or dictionary. These terms all refer to a data structure that contains a list of keys (in this case, the variable name, a String) and the corresponding value associated with each key (in this case, the variable value, a double). For this project, you are not expected to implement a symbol table efficiently since that is a topic for the rest of the course. You may wish to refer to section 3.1 in the textbook, which discusses symbol tables at a conceptual level and gives a linked-list implementation of one.

Any legal Java 6 identifier can be used for a variable. A legal identifier starts with an uppercase letter, a lowercase letter, or an underscore (_) and is then followed by zero or more characters, which can be letters, digits, or underscores.

In addition to the errors listed in the next section, the three-person group must check for the following errors. These errors should be reported before standardized infix would normally be printed.

1. Illegal Assignment: If an expression contains an equal sign, the equal sign must be the second token (the first operator), and the first token must be a legal variable name. Otherwise, print Illegal assignment.
2. Uninitialized variable: If a variable appears in an expression (either a simple expression or the right side of an equal sign), it must have been defined before. Otherwise, if the variable name does not appear in your symbol table, print Uninitialized variable.

Errors

You are required to check for five possible errors:

1. Invalid Operand: If the next token of input should be an operand, but it is not a properly formatted float literal, print Invalid operand and exit the program.
2. Invalid Operator: If the next token of input should be an operator, but the symbol you find (ignoring spaces, of course) is an invalid operator character, print Invalid operator: and the invalid character and exit the program.
3. Missing Operand: If the last term in the input sequence is an operator other than the right parenthesis, it must be the case that the last operation has no second operand. In this case, print Missing operand and exit the program.
4. Unbalanced Right Parenthesis: If, while converting the infix expression to a postfix expression, you encounter a right parenthesis and pop operators off your stack but find no corresponding left parenthesis, print Unbalanced right parenthesis ')' and exit the program.
5. Unbalanced Left Parenthesis: If, at the end of the conversion from infix a postfix, when doing the final popping of all the remaining operators, you encounter a left parenthesis (which much not have had a corresponding right parenthesis) print Unbalanced left parenthesis '(' and exit the program.

Sample Output

The following are a few simple cases of sample output for you to check against. User input is marked in green.

Normal Cases

Enter infix expression: (5-6)*7
Standardized infix: ( 5.0 - 6.0 ) * 7.0
Postfix expression: 5.0 6.0 - 7.0 *
Answer: -7.0

Enter infix expression: 602000000000000000000000 - 14.231 * +800000000000000000000
Standardized infix: 6.02E23 - 14.231 * 8.0E20
Postfix expression: 6.02E23 14.231 8.0E20 * -
Answer: 5.906152E23

Enter infix expression: 9
Standardized infix: 9.0
Postfix expression: 9.0
Answer: 9.0

Enter infix expression: ((((((6 - 42))))))
Standardized infix: ( ( ( ( ( ( 6.0 - 42.0 ) ) ) ) ) )
Postfix expression: 6.0 42.0 -
Answer: -36.0

Error Cases

Enter infix expression: egg + 2
Invalid operand

Enter infix expression: 4 & 5
Invalid operator: &

Enter infix expression: 10 +
Missing operand

Enter infix expression: (2 + 2
Standardized infix: ( 2.0 + 2.0
Unbalanced left parenthesis '('

Enter infix expression: 2 + 2)
Standardized infix: 2.0 + 2.0 )
Unbalanced right parenthesis ')'

Testing

In a problem like this, testing is of crucial importance. There are many different ways that your program can fail, and you want to check them all.

A short, but not nearly exhaustive list of test cases you want to cover includes:

• Each of the four operations separately
• Combinations of the four operations
• Use of parentheses to disambiguate
• More parentheses than are necessary
• Double values preceded by a minus sign
• Double values preceded by an optional plus sign
• Double values using scientific notation
• A single value with no operators
• Expressions with no spaces
• Expressions with unusual spacing
• Expressions long enough to require your stack or queue to perform a reallocation (assuming you are using array based stacks or queues)
• Error cases with a single bad operand
• Error cases with multiple bad operands
• Error cases with a single bad operator
• Error cases with multiple bad operators
• Error cases with unbalanced left parentheses
• Error cases with unbalanced right parentheses

For this project, you are required to create a large number of test cases, record them, and record the output of your program with each test case. A document containing this information is one of the items you must turn in.

Hints

• • Start early. This project is tough. Do everything you can to work smoothly with your partner.

 

• • This project is supposed to cover stacks and queues. You are required to implement at least one stack class. You’ll need stacks for both operators and operands. You can get around the problem of coding multiple stacks by making a generic stack. Or, you can make a stack able to hold a class that can contain either an operand or an operator. Or you can make operands and operators subclasses of a common superclass and hold references to the superclass in your stack. In my solution, I used a generic stack and also made operands and operators subclasses of a superclass.

 

• • A pure stack has a very small number of methods: push(), pop(), peek(), and maybe size() or isEmpty(). Data structures are supposed to make our lives easier. If you want to keep everything in a stack, but occasionally access the elements like an array or with an iterator, that’s fine. You don’t have to have a pure stack. Instead of using queues, I implemented a get() operator on my stack class. Objects were only added or removed with push() and pop(), but I could read any of them I wanted to. Additionally, feel free to implement your stack with an array or a linked list, but I highly recommend an array. It’s easier, faster, and any element can be accessed in O(1) time.

 

• • Work incrementally. Compile constantly. This project is nicely laid out into a few steps. Get input parsing working first. Then, implement your stack. Then, get infix to postfix working. Then, compute the answer. Write some kind of printing function early so that it’s easy to see the current state of your terms.

 

• • Write clean code.

 

• • No outside classes other than Scanner, String, and the Double and Character wrapper classes should be used.

 

• There are lots of error cases to detect, and most of them happen while in the middle of doing something else. How can you handle all these errors? Well, exception handling is a great tool. In my implementation, I created five custom exception classes corresponding to each of the errors: InvalidOperandException, InvalidOperatorException (which takes a char value in its constructor to hold the unexpected operator), MissingOperandException, UnbalancedLeftParenthesisException, and UnbalancedRightParenthesisException. You don’t have to make your own exceptions, but it makes handling the errors easy, mostly because you can handle them all in one place.