import java.util.Iterator;
import java.util.Vector;

public class RPN {

	
	protected static RpnQueue rQueue = new RpnQueue();
	protected static RpnStack rStack = new RpnStack();
	
	public RPN() {

	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		/*
		double ergebnis = 3+4*2 / Math.pow(Math.pow((1-5), 6), 1);	
		/*
		 * 
		 */
		//double ergebnis2 = 8.0 / 4096.0;
		//System.out.println( ergebnis2 ); 
		
		
		try {
			System.out.println("Given formula: " + args[0]);
			System.out.println("RPN formula: " + toRPN(args[0]));
			System.out.println("RPN result: " + evaluateRPN(toRPN(args[0])));
			
		} catch (FormulaFormatException e) {
			
			e.printStackTrace();
		}
		
	}

	public static String toRPN (String infixFormula) throws FormulaFormatException {
		
		rQueue = new RpnQueue();
		rStack = new RpnStack();
		
		String ret = "";
		
		for (int i = 0; i < infixFormula.length(); i++) {
						
			// check if current character is a number
			if (isNumber(infixFormula.charAt(i))) {
			
				rQueue.add(infixFormula.charAt(i));
				
			}
			// character is an operator
			else {
				
				// check if an operator already exists in stack
				if (!rStack.isEmpty()) {
					try {

						// check for open round bracket
						if (infixFormula.charAt(i) == '(') {
							
							rStack.add(infixFormula.charAt(i));
							
						}
						else if (infixFormula.charAt(i) == ')') {
							
							// get all from stack until open bracket found
							while (rStack.getFirst() != '(') {
								Character c = rStack.remove();
								if (c != '(') {
									
									// add operator to queue only if 
									// it is not a parenthesis
									rQueue.add(c);
								}
							}
							
							if (rStack.getFirst() == '(') {
								rStack.remove();
							}
							
						}
						// check if operator is higher than the one on the stack
						else if (isHigher(infixFormula.charAt(i), rStack.getFirst())) {
							
							rStack.add(infixFormula.charAt(i));
						}
						else {
							
							Character c = rStack.remove();
							
							// add operator to queue only if 
							// it is not a parenthesis
							rQueue.add(c);

							// push new operator onto stack
							rStack.add(infixFormula.charAt(i));
						}
					} catch (EmptyException e) {
						
						e.printStackTrace();
					}

				}
				else {
					
					rStack.add(infixFormula.charAt(i));
				}

				
			}
		}
		
		Iterator iter;
		
		iter = rQueue.charList.iterator();
		while(iter.hasNext()) {
		  ret += iter.next().toString();
		}
			
		iter = rStack.charList.iterator();
		while(iter.hasNext()) {
			// if stack contains bracket something is wrong ...
			if ( iter.next().toString().equals("(") || iter.next().toString().equals(")")) throw new FormulaFormatException("");

			ret += iter.next().toString();
		}
		
		return ret;
	}

	public static double evaluateRPN(String RPNformula) throws FormulaFormatException {
		
		Vector results = new Vector();
		
		double n1 = 0, 
			   n2 = 0,
			   result = 0;
		
		for (int i = 0; i < RPNformula.length(); i++) {
			
			if (isNumber(RPNformula.charAt(i))) {
				
				// push into results
				results.add(0,RPNformula.charAt(i));
				
			}
			else {
				
				n2 = Double.parseDouble(results.remove(0).toString());
				n1 = Double.parseDouble(results.remove(0).toString());
					
				switch (RPNformula.charAt(i)) {
				case '+':
					result = n1 + n2;
					break;
				case '-':
					result = n1 - n2;
					break;
				case '*':
					result = n1 * n2;
					break;
				case '/':
					result = n1 / n2;
					break;
				case '^':
					result = Math.pow(n1, n2);
					break;
				default:
					break;
				}
				
				//push result back
				results.add(0,result);	
			}
		}
		return Double.parseDouble(results.get(0).toString());
	}
	
	protected static boolean isNumber(char c) {
		
		try {
			int i = Integer.parseInt(String.valueOf(c));
			return true;
		}
		catch (Exception e) {
			return false;
		}
	}
	
	protected static boolean isHigher(char c1, char c2) {
		
		// all are higher than open parenthesis
		if ( (c1 == '-' || c1 == '+' || c1 == '*' || c1 == '/') && (c2 == '(') ) {
			return true;
		}

		if ( (c1 == '*' || c1 == '/') && (c2 == '+' || c2 == '-') ) {
			return true;
		}
		
		// power is always higher, also if c2 is power too
		if (c1 == '^'){
			return true;
		}

		return false;
	}
}