Convert Infix Expression To Postfix Expression

Convert Infix Expression To Postfix Expression

Given an infix expression and convert it to a postfix expression.

A mathematical expression, e.g. (3+4), can be notated as Infix ("3+4"), Postfix ("34+"), and Prefix ("+34") expressions.
Infix expressions are human readable notations while postfix ones are machine friendly notations. Usually, human inputs are in infix format which are converted to postfix expressions in a computer and then evaluated to get the output result (see previous post for evaluation).

For example,
Given "3 + 4", return "34+".
Given "3*(4+5)-6/(1+2)", return "345+*612+/-".

Solution

Intuitively, for digits, we can simply append it to the output string, but for operators, we need a stack to keep previous ones and pop them to the output string as needed.

Let's go through several examples first.

"3 + 4 - 5" -> "34+5-"    // pop '+' before '-' since they have the same precedence
"3 + 4 * 5" -> "345*+"    // didn't pop '+' until '*' get popped since '*' has higher precedence than '+'
"3^2^2+4" -> "322^^4+"    // didn't pop '^' until '+' comes in since '^' is right-associative

Now, we know what we are going to handle this problem:
For each read-in character from the given string,

• If it is a digit, append to output;
• If it is a left parenthesis, push it to stack;
• If it is a right parenthesis, pop out operators from stack and append to output until hit a left parenthesis (if left one doesn't exist, throw exception), also pop out the left parenthesis but no need to append to output;
• If it is an operator,
• while the top of stack is an operator and is left-associative and has higher or the same precedence, pop it out and append to output;
• push the new one to stack.

This algorithm is known as Shunting Yard Algorithm. It runs in time O(n) in average and takes O(m) extra spaces in worst case, where n is the length of the given string and m is the number of operators.

 public static String infixToPostfix(String expr) {  
   StringBuilder postfix = new StringBuilder();  
   Stack<Character> stack = new Stack<Character>();  
   
   // read in tokens  
   for (int i=0; i<expr.length(); ++i) {  
     char c = expr.charAt(i);  
     if (isDigit(c)) {  
       postfix.append(c);  
     } else if (isOp(c)) {  
       while (isLeftAssociative(c) && !stack.isEmpty() && getPreced(stack.peek()) >= getPreced(c)) {  
         postfix.append(stack.pop());  
       }  
       stack.push(c);  
     } else if (c == '(') {  
       stack.push(c);  
     } else if (c == ')') {  
       while (!stack.isEmpty() && stack.peek() != '(') {  
         postfix.append(stack.pop());  
       }  
       if (stack.isEmpty()) {  
         throw new IllegalArgumentException("mismatched parentheses.");  
       }  
       stack.pop(); // pop '(' without adding to output  
     } else if (c == ' ') {  
       // do nothing  
     } else {  
       throw new IllegalArgumentException("Invalid input.");  
     }  
   }  
   
   // empty stack  
   while (!stack.isEmpty()) {  
     char c = stack.pop();  
     if (c == '(') {  
       throw new IllegalArgumentException("mismatched parentheses.");  
     }  
     postfix.append(c);  
   }  
   
   return postfix.toString();  
 }  
   
 private static boolean isLeftAssociative(char op) {  
   switch (op) {  
   case '+':  
   case '-':  
   case '*':  
   case '/':  
     return true;  
   case '^':  
     return false;  
   }  
   throw new IllegalArgumentException("Invalid input.");  
 }  
   
 private static int getPreced(char op) {  
   switch (op) {  
   case '+':  
   case '-':  
     return 1;  
   case '*':  
   case '/':  
     return 2;  
   case '^':  
     return 3;  
   case '(':  
   case ')':  
     return -1;  
   }  
   throw new IllegalArgumentException("Invalid input.");  
 }  
   
 private static boolean isDigit(char c) {  
   return (c >= '0' && c <= '9');  
 }  
   
 private static boolean isOp(char c) {  
   switch (c) {  
   case '+':  
   case '-':  
   case '*':  
   case '/':  
   case '^':  
     return true;  
   }  
   return false;  
 }