Part 1:
Infix to Postfix conversion
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.
Part 2: : Evaluating the postfix expression
For this part, you will need to maintain one stack:
- A stack Evaluating the postfix expression (Using Linked list Implementation)
This step will use the queue (PostQueue) that was the result of the infix to postfix conversion, and a stack. The algorithm proceeds as follows:
1. Make an empty stack (Using Linked list Implementation)
2. Scan the postfix expression (PostQueue) one item at a time:
- If it is an operand, push onto the stack.
- If it is an operator,
- pop two numbers from the stack,
- apply the operator, and
- push the result back onto the stack.
- If the stack does not have enough operands, the expression is invalid.
- At the end of input, check the stack. If it has just one item, that is the answer. Else, the expression is invalid.