Infix to Postfix

What is an infix expression?

Expression in the form of ‘operand’ ‘operator’ ‘operand’ is called infix expression.

Example:  a+b

What is postfix expression?

Expression in the form of ‘operand’ ‘operand’ ‘operator’ is called postfix expression.

Example:  ab+

What is the need of infix to postfix conversion?

Infix expression is easy to understand for humans but the computer can’t differentiate between brackets and operators easily so we convert an infix expression to postfix expression.

How to convert infix to Postfix?

1. Scan an infix expression from left to right. Put the operand into a postfix expression. 
2. Else if the character’s precedence is greater the character in the stack or stack has ‘(‘ on the top or stack is empty then simply push the character into the stack.
3. Otherwise, pop all characters from the stack and put it into postfix expression until a character with lower precedence than scanned character or ‘(‘ is found then push the scanned character.
4. If the scanned character is ‘(‘ push it into the stack.
5. If the scanned character is ‘)‘ pop all characters from the stack and add them into postfix expression until ‘(‘ is found and remove ‘(‘ from the stack.
6. Repeat steps 1-5 for all characters.
7. Pop all characters from the stack until stack becomes empty and add them in postfix expression.

C++ code for Infix to Postfix

/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack for Stack operations 
#include<bits/stdc++.h> 
using namespace std; 

//Function to return precedence of operators 
int prec(char c) 
{ 
  if(c == '^') 
  return 3; 
  else if(c == '*' || c == '/') 
  return 2; 
  else if(c == '+' || c == '-') 
  return 1; 
  else
  return -1; 
} 

// The main function to convert infix expression 
//to postfix expression 
void infixToPostfix(string s) 
{ 
  std::stack<char> st; 
  st.push('N'); 
  int l = s.length(); 
  string ns; 
  for(int i = 0; i < l; i++) 
  { 
    // If the scanned character is an operand, add it to output string. 
    if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z')) 
    ns+=s[i]; 

    // If the scanned character is an ‘(‘, push it to the stack. 
    else if(s[i] == '(') 
    
    st.push('('); 
    
    // If the scanned character is an ‘)’, pop and to output string from the stack 
    // until an ‘(‘ is encountered. 
    else if(s[i] == ')') 
    { 
      while(st.top() != 'N' && st.top() != '(') 
      { 
        char c = st.top(); 
        st.pop(); 
      ns += c; 
      } 
      if(st.top() == '(') 
      { 
        char c = st.top(); 
        st.pop(); 
      } 
    } 
    
    //If an operator is scanned 
    else{ 
      while(st.top() != 'N' && prec(s[i]) <= prec(st.top())) 
      { 
        char c = st.top(); 
        st.pop(); 
        ns += c; 
      } 
      st.push(s[i]); 
    } 

  } 
  //Pop all the remaining elements from the stack 
  while(st.top() != 'N') 
  { 
    char c = st.top(); 
    st.pop(); 
    ns += c; 
  } 
  
  cout << ns << endl; 

} 

//Driver program to test above functions 
int main() 
{ 
  string exp = "a+b*(c^d-e)^(f+g*h)-i"; 
  infixToPostfix(exp); 
  return 0; 
} 

Java code for Infix to Postfix

/* Java implementation to convert an infix expression to postfix*/
// Note that here we use Stack class for Stack operations 

import java.util.Stack; 

class Test 
{ 
  // A utility function to return precedence of a given operator 
  // Higher returned value means higher precedence 
  static int Prec(char ch) 
  { 
    switch (ch) 
    { 
    case '+': 
    case '-': 
      return 1; 
  
    case '*': 
    case '/': 
      return 2; 
  
    case '^': 
      return 3; 
    } 
    return -1; 
  } 
  
  // The main method that converts given infix expression 
  // to postfix expression. 
  static String infixToPostfix(String exp) 
  { 
    // initializing empty String for result 
    String result = new String(""); 
    
    // initializing empty stack 
    Stack<Character> stack = new Stack<>(); 
    
    for (int i = 0; i<exp.length(); ++i) 
    { 
      char c = exp.charAt(i); 
      
      // If the scanned character is an operand, add it to output. 
      if (Character.isLetterOrDigit(c)) 
        result += c; 
      
      // If the scanned character is an '(', push it to the stack. 
      else if (c == '(') 
        stack.push(c); 
      
      // If the scanned character is an ')', pop and output from the stack 
      // until an '(' is encountered. 
      else if (c == ')') 
      { 
        while (!stack.isEmpty() && stack.peek() != '(') 
          result += stack.pop(); 
        
        if (!stack.isEmpty() && stack.peek() != '(') 
          return "Invalid Expression"; // invalid expression				 
        else
          stack.pop(); 
      } 
      else // an operator is encountered 
      { 
        while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())){ 
          if(stack.peek() == '(') 
            return "Invalid Expression"; 
          result += stack.pop(); 
      } 
        stack.push(c); 
      } 
  
    } 
  
    // pop all the operators from the stack 
    while (!stack.isEmpty()){ 
      if(stack.peek() == '(') 
        return "Invalid Expression"; 
      result += stack.pop(); 
    } 
    return result; 
  } 
  
  // Driver method 
  public static void main(String[] args) 
  { 
    String exp = "a+b*(c^d-e)^(f+g*h)-i"; 
    System.out.println(infixToPostfix(exp)); 
  } 
} 

Output:

abcd^e-fgh*+^*+i-

Reference