# Infix to Postfix

Difficulty Level Hard
Frequently asked in Amazon Paytm Samsung VMware
StackViews 220

Table of Contents

### 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

Translate »