package alok.examples;
 
import java.util.Scanner;
import java.util.Stack;
 
/*
 * This is a code snippet to convert a simple Infix Expression to a Postfix one.
 * NOTE : It would not work for expressions containing paranthesis. It only takes into 
 * account operators for the following operations:
 * 1. Multiplication
 * 2. Division
 * 3. Modulus
 * 4. Addition
 * 5. Subtraction
 * 
 * The precedence of the operations is shown below. Lower level operations have a higher 
 * precedence, so here, operations in Level 1 have higher precedence than those mentioned
 * in Level 2. 
 * Operations mentioned in the same level have equal precedence.
 *  
 * Level 1. Multiplication, Division, Modulus
 * Level 2. Addition, Subtraction  
 */
public class Infix2Postfix {
 
	private Stack<String> stack;
	private String infixExp;
	private String postfixExp = "";
 
	public Infix2Postfix(String exp){
 
		String str = "";
		infixExp = exp;
		stack = new Stack<String>();
 
		for (int i=0;i<infixExp.length();i++){
			/* 
			 * If the character is a letter or a digit we append it to the postfix 
			 * expression directly. 
			 */
			str = infixExp.substring(i,i+1);
			if(str.matches("[a-zA-Z]|\\d"))
				postfixExp += str;
			else if (isOperator(str)){
				/*
				 * If the stack is empty we directly push the current char into it.
				 */
				if (stack.isEmpty()){
					stack.push(str);
				}
				else{
					/*
					 * If the current character is an operator, we need to check the stack 
					 * status then, if the stack top contains an operator with lower
					 * precedence, we push the current character in the stack else we pop
					 * the character from the stack and add it to the postfix string. This 
					 * continues till we either find an operator with lower precedence in the 
					 * stack or we find the stack to be empty.
					 */
					String stackTop = stack.peek();
					while (getPrecedence(stackTop,str).equals(stackTop)&& !(stack.isEmpty())){
						postfixExp += stack.pop();
						if (!(stack.isEmpty()))
							stackTop = stack.peek();
					}
					stack.push(str);
				}
			}
		}
		// In the end just append all the operators from the stack to the postfix expression.
		while(!(stack.isEmpty()))
			postfixExp += stack.pop();
		// Print out the postfix expression
		System.out.println("The postfix form of the expression you entered is: " + postfixExp);
	}
 
	/*
	 * Returns true if 'ch' is an operator, false o/w
	 */ 
	private boolean isOperator(String ch){
 
		String operators = "*/%+-";
		if (operators.indexOf(ch) != -1)
			return true;
		else
			return false;
	}
 
	/*
	 * Returns the operator with higher precedence among 'op1' & 'op2', if they have equal
	 * precedence, the first operator in the argument list (op1) is returned.
	 */ 
	private String getPrecedence(String op1, String op2){
 
		String multiplicativeOps = "*/%";
		String additiveOps = "+-";
 
		if ((multiplicativeOps.indexOf(op1) != -1) && (additiveOps.indexOf(op2) != -1))
			return op1;
		else if ((multiplicativeOps.indexOf(op2) != -1) && (additiveOps.indexOf(op1) != -1))
			return op2;
		else if((multiplicativeOps.indexOf(op1) != -1) && (multiplicativeOps.indexOf(op2) != -1))
			return op1;
		else 
			return op1;
	}		
 
	public static void main(String[] args){
 
		System.out.println("Enter an expression in the Infix form:");
		Scanner scanner = new Scanner(System.in);
 
		String expression = scanner.nextLine();
		new Infix2Postfix(expression);
	}
}