# Stack: Infix to Postfix Expression

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

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