Question: Create a utility class that have a method infixToPostfix to convert infix notation to postfix notation that will take in a string and return a
Create a utility class that 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.
ALGORITHMS
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:
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 then 2 values throw an error
Create a string with 2nd value and then the operator and then the 1st value popped from the stack.
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
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 then 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
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help