# Stack: Infix to prefix expression

Question: Convert an infix expression to a prefix expression

```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"));
}

}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.