import java.util.StringTokenizer;
public class InfixToPostfix{

	private boolean isOperator(String s){
		if(s.equals("+")|| s.equals("-")|| s.equals("*")|| s.equals("/")|| s.equals("(")|| s.equals(")"))
			return true;
		return false;
	}//private boolean isOperator(

	private int getInstackPriority(String s){ //while entering into the stack
	    if (s.equals("+")||s.equals("-"))
			return 1;
	    else if (s.equals("/")||s.equals("*"))
			return 2;
		else if(s.equals("("))
			return 3;
		else
			return 0;
	}//private int getInstackPriority..

	private int getOutstackPriority(String s){ //if already present in the stack
	    if (s.equals("+")||s.equals("-"))
			return 1;
	    else if (s.equals("/")||s.equals("*"))
			return 2;
		else if(s.equals("("))
			return -1;
		else
			return 0;
	}//private int getOutstackPriority..

	public String[] getPostfixExpr(String expr){
		StringTokenizer tokenizer=new StringTokenizer(expr,"+-/*()",true);
		String[] tokens=new String[20];
		String[] postfixExpr=new String[20];
		String[] stack=new String[20];
		int top=-1;
		int count=0;

		while(tokenizer.hasMoreTokens()){
			tokens[count]=tokenizer.nextToken();
			//System.out.println(tokens[count]);
			count++;
		}//while

		int index=0;
		for(int i=0;i<count;i++){
			if(isOperator(tokens[i])){
				if(top==-1)
					stack[++top]=tokens[i];
				else if(tokens[i].equals(")")){
					while(top>=0 && !stack[top].equals("(")){
						postfixExpr[index++]=stack[top--];
					}//while
					top--; //to remove ( from stack
				}//if(tokens[i].equals(")")
				else{
					if(getInstackPriority(tokens[i])>getOutstackPriority(stack[top]))
						stack[++top]=tokens[i];
					else{
						while(top>=0&&getInstackPriority(tokens[i])>getOutstackPriority(stack[top])){
							postfixExpr[index++]=stack[top--];
						}//while(top>=0..
					}//else
				}//else
			}//if(isOperator
			else
				postfixExpr[index++]=tokens[i];
		}//for(int i=0..
		while(top>=0) {
			postfixExpr[index++]=stack[top--];
		}//while(top>=0..
		return postfixExpr;
	}//String[] getPostfixExpr

	public static void main(String args[]){
		String expr="(A+B)*(C-D)";
		System.out.println("Infix expression : "+expr);
		InfixToPostfix obj=new InfixToPostfix();
		String[] postfix=obj.getPostfixExpr(expr);
		System.out.print("Postfix Expr : ");
		for(int i=0;postfix[i]!=null;i++)
			System.out.print(postfix[i]);
	}//main
}//class