Question: Convert an infix expression to a prefix expression
Resource: https://www.youtube.com/watch?v=8QxlrRws9OI&list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU&index=35
package additional_problems.stack; /** * Rules for infix to prefix conversion: * 1. Reverse the expression * 2. Print operands as they arrived * 3. If the stack is empty or contains ')' on the top, push incoming operator onto stack * 4. If incoming operator is '(', pop the stack elements till ')' is found * 5. If incoming operator is ')', push it into stack * 6. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack * 7. 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. * 8. 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 push the incoming operator into stack * ii. associativity R->L then push the incoming operator * 9. At the end of the stack pop and print all the operators * 10. Reverse the end result * */ public class P03InfixToPrefix { //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; } public static String reverseString(String string){ StringBuffer reversedString= new StringBuffer(""); for (int i = string.length()-1; i >=0; i--) { reversedString.append(string.charAt(i)); } return reversedString.toString(); } public static String infixToPostfix(String expression){ CharStack stack= new CharStack(expression.length()); //1. Reverse the expression String reversedExpression= reverseString(expression); StringBuffer result= new StringBuffer(""); for(int i=0; i<reversedExpression.length(); i++){ char c= reversedExpression.charAt(i); //2. Print operands as they arrived if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')) { result.append(c); } //3. If the stack is empty or contains ')' on the top, push incoming operator onto stack else if(stack.peek()==')' || stack.isEmpty()){ stack.push(c); } //4. If incoming operator is '(', pop the stack elements till ')' is found else if(c=='('){ while (stack.peek()!=')'){ result.append(stack.pop()); } stack.pop(); } //5. If incoming operator is ')', push it into stack else if(c==')'){ stack.push(c); } //6. If incoming operator has higher precedence than the operator at the top of the stack, push it on the stack else if(getPrecedence(c)>getPrecedence(stack.peek())){ stack.push(c); } //7. 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. else if(getPrecedence(c)<getPrecedence(stack.peek())){ while(getPrecedence(c)<getPrecedence(stack.peek())){ result.append(stack.pop()); } stack.push(c); } //8. 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 push the incoming operator into stack // ii. associativity R->L then push the incoming operator else if(getPrecedence(c)==getPrecedence(stack.peek())){ stack.push(c); } } //9. At the end of the stack pop and print all the operators if(!stack.isEmpty()){ while (!stack.isEmpty()){ result.append(stack.pop()); } } //10. Reverse the end result return reverseString(result.toString()); } public static void main(String [] args){ System.out.println(infixToPostfix("A*B+C/D")); } }