An infix expression is one in which operators are located between their operands. This is how we are accustomed to writing expressions in standard mathematical notation. In postfix notation, the operator immediately follows its operands. Examples of infix expressions are:
One advantage of postfix is that unlike infix, no parentheses are necessary. Another advantage is that postfix expressions are easily evaluated using a stack.
This project will require you to create a Java program that will take an input file consisting of several lines of infix notation mathematical calculations, convert them to postfix notation (using the first algorithm in Part1), and evaluate them (using the second algorithm in Part2). The results of the calculations will then be printed to an output file. This project will build on your array and linked list implementations, using them to create your own implementations of stacks and queues for each of the algorithms.
This part will use both a stack and queue in order to convert expressions from infix to postfix notation.
The stack and queue will be implemented by you, using your linked list implementation from labs.
For this part, you will need to maintain two queues and one stack:
- A stack for conversion Infix to Postfix (Using Array Implementation)
- A queue for accumulation the digits of the operand (NumQueue) (Using Array Implementation)
- A queue to store the Postfix notation (PostQueue) (Using Linked list Implementation)
Each value will be read from the input line, and dealt with in the following manner:
1. When an operand is read, add it into( NumQueue)
2. When an operator is read
- Convert (NumQueue) into a single floating number, add it into(PostQueue) immediately
- Pop the stack elements and add them to the queue (PostQueue) one by one until the top of the stack has an element of lower precedence
- Then push it into stack.
- When a close-parenthesis [‘)'] is found, pop all the stack elements and add them to the queue (PostQueue) one by one until an open-parenthesis [‘(‘] is found
- When we reach the end of input, pop everything that remains on the stack and add to the queue (PostQueue) one by one.
- Notes : [‘)'] has the lowest precedence when in the stack but has the highest precedence when in the input
When finished converting one statement into a queue in postfix notation, pass the queue (PostQueue) to the next step - the postfix expression evaluator.