Question: Convert an infix expression to a postfix expression
Resources:
package additional_problems.stack; /** * Rules for infix to postfix conversion: * 1. print operands as they arrived * 2. If the stack is empty or contains a left parenthesis on the top, push incoming operator onto stack * 3. If incoming operator is '(', push it into stack * 4. If incoming operator is ')', pop the stack elements till left parenthesis is found * 5. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack * 6. If incoming operator has lower precedence than the top of the stack, pop and print the top of the stack, Then test the * incoming operator with the top of the stack. * 7. If incoming operator has the same precedence as the top of the stack use the associativity rule * i. associativity L->R (i.e *and/ or +and-) then pop and print top of the stack and then push the incoming operator * ii. associativity R->L then push the incoming operator * 8. At the end of the stack pop and print all the operators * * * Created by aarushi on 6/7/21. */ public class P02InfixToPostfix { //method that returns the precedence of operators //the higher precedence operators would return a higher value public static int getPrecedence(char operator){ if (operator=='+' || operator=='-'){ return 1; } else if (operator=='*' || operator=='/'){ return 2; } else if (operator=='^'){ return 3; } return -1; } //method that converts infix to postfix expression public static void infixToPostfix(String string){ CharStack stack= new CharStack(string.length()); for(int i=0; i<string.length(); i++) { char c = string.charAt(i); //1. print operands as they arrived if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { System.out.print(c); } //2. If the stack is empty or contains a left parenthesis on the top, push incoming operator onto stack //3. If incoming operator is '(', push it into stack else if (stack.isEmpty() || stack.peek() == '(' || c=='(') { stack.push(c); } //4. If incoming operator is ')', pop the stack elements till left parenthesis is found else if (c == ')') { while (stack.peek() != '(') { System.out.print(stack.pop()); } stack.pop(); } //5. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack else if (getPrecedence(stack.peek())<getPrecedence(c)){ stack.push(c); } //6. If incoming operator has lower precedence than the top of the stack, pop and print the top of the stack, Then test the // incoming operator with the top of the stack. //7. If incoming operator has the same precedence as the top of the stack use the associativity rule else if(getPrecedence(stack.peek())>getPrecedence(c) || getPrecedence(stack.peek())==getPrecedence(c)){ while(getPrecedence(stack.peek())>getPrecedence(c) || getPrecedence(stack.peek())==getPrecedence(c)){ System.out.print(stack.pop()); } stack.push(c); } } //8. At the end of the stack pop and print all the operators if(!stack.isEmpty()){ while (!stack.isEmpty()){ System.out.print(stack.pop()); } } } public static void main(String [] args){ infixToPostfix("a+b*(c^d-e)^(f+g*h)-i"); } }