## Description

**Infix notation** is the **notation** commonly used in arithmetical and logical formulae and statements. It is characterized by the placement of operators between operands – “infixed operators” – such as the plus sign in “2 + 2”.

**Postfix notation** is a **notation** for writing arithmetic expressions in which the operands appear before their operators. There are no precedence rules to learn, and parentheses are never needed.

**You will be creating a utility class that converts an infix expression to a postfix expression, a postfix expression to an infix expression and evaluates a postfix expression.**

The GUI is provided.

** **

** Concepts tested:**

Generic Queue

Generic Stack

Exception handling

** **

**Data Element**

** **String

** **

**Data Structures**

- Create a generic queue class called
*NotationQueue*.*NotationQueue*will implement the*QueueInterface*given you. You will be creating NotationQueue from scratch (do not use an internal object of the Queue class from java.util) - Create a generic stack class called
*NotationStack*.*NotationStack*will implement the*Stack Interface*given you. You will be creating NotationStack from scratch (do not use an internal object of the Stack class from java.util)

**Utility Class**

The *Notation *class will have a method infixToPostfix to convert infix notation to postfix notation that will take in a string and return a string, a method postfixToInfix to convert postfix notation to infix notation that will take in a string and return a string, and a method to evaluatePostfix to evaluate the postfix expression. It will take in a string and return a double.

** In the infixToPostfix method, you MUST use a queue for the internal structure that holds the postfix solution. Then use the toString method of the Queue to return the solution as a string.**

For simplicity sake:

- operands will be single digit numbers
- the following arithmetic operations will be allowed in an expression:

+ addition

– subtraction

* multiplication

/ division

**Exception Classes**

Provide the following exception classes:

- InvalidNotationFormatException – occurs when a Notation format is incorrect
- StackOverflowException – occurs when a top or pop method is called on an empty stack.
- StackUnderflowException – occurs when a push method is called on a full stack.
- QueueOverflowException – occurs when a dequeue method is called on an empty queue.
- QueueUnderflowException – occurs when a enqueue method is called on a full queue.

**GUI Driver (provided)**

- Initially neither radio button for notation is selected. When a radio button is selected, the Convert button is enabled and the appropriate label and field are visible for the user input.
- When the user selects the Convert button, the appropriate label and field with the conversion will be displayed.
- When the user selects the Evaluate button, the “answer” to the expression will be displayed.
- When the Exit button is selected, the application will close.

__ __

** **

**ALGORITHMS**

__Infix expression to postfix expression:__

__Infix expression to postfix expression:__

Read the infix expression from left to right and do the following:

If the current character in the infix is a space, ignore it.

If the current character in the infix is a digit, copy it to the postfix solution queue

If the current character in the infix is a left parenthesis, push it onto the stack

If the current character in the infix is an operator,

- Pop operators (if there are any) at the top of the stack while they have

equal or higher precedence than the current operator, and insert the popped operators in postfix solution queue

- Push the current character in the infix onto the stack

If the current character in the infix is a right parenthesis

- Pop operators from the top of the stack and insert them in postfix solution queue until a left parenthesis is at the top of the stack, if no left parenthesis-throw an error
- Pop (and discard) the left parenthesis from the stack

When the infix expression has been read, Pop any remaining operators and insert them in postfix solution queue.

__Postfix expression to infix expression__*:*

__Postfix expression to infix expression__*:*

* *

Read the postfix expression from left to right and to the following:

If the current character in the postfix is a space, ignore it.

If the current character is an operand, push it on the stack

If the current character is an operator,

- Pop the top 2 values from the stack. If there are fewer than 2 values throw an error
- Create a string with 1
^{st}value and then the operator and then the 2^{nd} - Encapsulate the resulting string within parenthesis
- Push the resulting string back to the stack

When the postfix expression has been read:

If there is only one value in the stack – it is the infix string, if more than one

value, throw an error

__Evaluating a postfix expression__

__Evaluating a postfix expression__* *

Read the postfix expression from left to right and to the following:

If the current character in the postfix expression is a space, ignore it.

If the current character is an operand or left parenthesis, push on the stack

If the current character is an operator,

- Pop the top 2 values from the stack. If there are fewer than 2 values throw an error
- Perform the arithmetic calculation of the operator with the first popped value as the right operand and the second popped value as the left operand
- Push the resulting value onto the stack

When the postfix expression has been read:

If there is only one value in the stack – it is the result of the postfix expression, if

more than one value, throw an error

** **

** **

** **

**Examples:**

** **

At startup

** **

** **

After selecting Infix to Postfix After selecting Postfix to Infix

After selecting Convert Button

After selecting Evaluate button

** **

**Grading Rubric – CMSC 204 Project #2**

** **

Name _____________________________ .

__ __

__PROGRAMMING__** **(100 pts)** **

Compiles 40 pts _____

Accuracy

Passes public JUnit tests 15 pts _____

Passes STUDENT JUnit tests 10 pts _____

Passes private instructor tests 15 pts _____

Execution: runs without errors (either run-time or logic errors) 20 pts _____

Possible Sub-total 100 pts _____

** REQUIREMENTS** (Subtracts from Programming total)

__Documentation:__

__Documentation:__

Javadoc was not provided for all student generated classes – 5 pts _____

Documentation within source code was missing or incorrect – 5 pts _____

Description of what class does was missing

Author’s Name, @author, was missing

Methods not commented properly using Javadoc @param, @return

JUnit STUDENT methods were not implemented -5 pts _____

Learning Experience (text document) -4 pts _____

In 3+ paragraphs, highlight your lessons learned and learning experience from working on this project. What have you learned? What did you struggle with? What would you do differently on your next project?

__Programming Style:__

__Programming Style:__

Incorrect use of indentation, statements, structures -10 pts _____

** Design: **Classes do not have the functionality specified, i.e.,

- Data Structures classes – 16 pts_____

- Generic Stack class
- Generic Queue class

- Utility class – Notation -15 pts_____

- Does not follow provided Javadoc
- Does not correctly handle exceptions

Possible decrements: -60 pts _____

Possible total grade: 100 pts _____