Convert an infix expression into a postfix expression

Given an infix expression, convert it to the postfix expression. Assume that the infix expression is a string of tokens without any whitespace.

Input: A*B+C
Output: AB*C+

Input: (A+B)*(C/D)
Output: AB+CD/*

Input: A*(B*C+D*E)+F
Output: ABC*DE*+*F+

Input: (A+B)*C+(D-E)/F+G
Output: AB+C*DE-F/+G+

The idea is to use the stack data structure to convert an infix expression to a postfix expression. The stack is used to reverse the order of operators in postfix expression. The stack is also used to hold operators since an operator can’t be added to a postfix expression until both of its operands are processed.

The following algorithm will output a string in postfix order. We process the infix expression from left to right. For each token, four cases can arise:

1. If the current token is an opening bracket, '(' , push it into the stack.
2. If the current token is a closing bracket, ')' , pop tokens from the stack until the corresponding opening bracket ‘(‘ is removed. Append each operator at the end of the postfix expression.
3. If the current token is an operand, append it at the end of the postfix expression.
4. If the current token is an operator, push it on the top of the stack. Before doing that, first pop from the stack till we have a lower precedence operator on top, or the stack becomes empty. Append each operator at the end of the postfix expression.

Finally, append any remaining operators in the stack at the end of the postfix expression and return the postfix expression. Following is the pictorial representation of the above logic for the infix expression A*(B*C+D*E)+F :

Following is the implementation of the above algorithm in C++, Java, and Python: