Convert Infix to Postfix notation

Infix, Prefix and Postfix expression : Infix, Postfix and Prefix Notation
Data Structure Involved: Stack

Algorithm:

Input Infix String: (P+Q)*R+(S-T)/U+V

1. Consider an empty stack to store the operators and empty output postfix string.
2. Scan the Infix expression from left to right.
3. If the character encountered is (,{,[ like braces then push it into stack.
4. If next character encountered is operand then append it to the end of output postfix string.
5. If next character is operator and stack is not empty because of having another operator on the top then first check if the next character that we want to push is having high precedence then simply push it to the stack else if having low precedence then pop the top stored character from the stack and append it into the output postfix string. Now check again if the top stack character is having low precedence or may be stack empty then push the next character into the stack.
6. Also, If next character encountered is ),},] then first pop the all operators enclosed by these parenthesis and append it to the output string. Discard the parenthesis at the end.
7. Finally append the remaining operator to the output postfix string.

Below is the detail:

Infix	Stack	Postfix
(	(
P	(	P
+	(+	P
Q	(+	PQ
)		PQ+
*	*	PQ+
R	*	PQ+R
+	+	PQ+R*
(	+(	PQ+R*
S	+(	PQ+R*S
–	+(-	PQ+R*S
T	+(-	PQ+R*ST
)	+	PQ+R*ST-
/	+/	PQ+R*ST-
U	+/	PQ+R*ST-U
+	+	PQ+R*ST-U/+
G	+	PQ+R*ST-U/+V
		PQ+R*ST-U/+V+

Output: PQ+R*ST-U/+V+