Java infix to postfix homework-found in chegg
pizzaking31
Java infix to postfix
Purpose:
To create a program that will implement a stack object to convert algebraic statements from either infix notation to postfix notation or vice-versa. The program will also implement a link list data structure to track all the conversions done.
The Program should have a menu like the following:
Please select what type of conversion you would like to do:
- Infix to postfix
- Postfix to infix
- Print Equations
- Exit
If the user selects the first option the user will enter the equation minus the assignment portion of the equation. So x= a+b; would just be a+b;.
You may assume that each operand is only a single character. Use the semicolon as the string termination.
The program should keep track of each conversion and add it into a link list structure. When the user finally selects the Exit feature of the menu the List of all converted equations should be printed to the screen.
The link list node structure should be of a String Type.
You will find the Linked List and the Stack Code in the WinZip file below the assignment.
Definitions:
Infix notation: X + Y
Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."
Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets ( ) to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction.
Postfix notation (also known as "Reverse Polish notation"): X Y +
Operators are written after their operands. The infix expression given above is equivalent to A B C + * D /
The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.
Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit:
( (A (B C +) *) D /)
Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D".
Algorithms:
There are some problems with the algorithms below. First they do not handle the idea of Parenthesis and what do with the order of operations is a little confusing. Please fix the algorithm so that it makes complete sense for any Algebraic Formula.
Algorithm for Infix to Postfix:
1. Initialize an operator stack. 2. Input characters of infix string from left to right ignoring white spaces. 3. IF character = operand THEN insert it into postfix output string. 4. IF character = operator AND stack is empty, THEN push operator onto stack. 5. IF character = operator AND stack is not empty, THEN peek at the stack and compare the precedence of the popped operator with the newly read operator. IF peeked operator has less or equal precedence than the newly read character THEN leave the stack alone…ELSE move peeked operator to postfix string and pop the stack. 6. Push the newly read operator onto the operator stack. 7. When there are no more characters to read in the infix string, pop the operator stack and add the operators to the postfix string.
Algorithm for Postfix Expression Evaluator:
1. Initialize an operand stack. 2. Input characters of postfix string from left to right ignoring white spaces. 3. IF character = operand THEN push it onto operand stack. 4. IF character = operator THEN pop operand stack twice and perform operation of recently read operator on both popped operands. Push the result onto the top of the stack. 5. IF there are no more characters to be read THEN pop the last number in the operand stack and display it as the final evaluated expression result.
