public static int precedence(String operator) {
		switch (operator) {
		case ("+"):
			return 1;
		case ("-"):
			return 1;
		case ("*"):
			return 2;
		case ("/"):
			return 2;
		case ("^"):
			return 3;
		case ("("):
			return 4;
		}
		return -1;
	}

	public static boolean isOperator(String input) {
		return input.matches("[\\+\\-\\*\\/\\(\\)]");
	}

	public static String infixToPreFix(String input) {
		Stack<String> operands = new Stack<String>();
		Stack<String> operators = new Stack<String>();
		String[] arr = input.split(" ");

		for (int i = 0; i < arr.length; i++) {

			if (!isOperator(arr[i])) {
				operands.push(arr[i]);
//				System.out.println("push " + arr[i]);
				continue;
			}

			if (arr[i].equals("(") || arr[i].equals(")")) {
				evaluateParentheses(operators, operands, arr[i]);
//				System.out.println("( or )");
				continue;
			}

//			System.out.println("eval " + arr[i]);
			pushOperatorPrefix(operands, operators, arr[i]);
		}

		System.out.println(operands);
		return operands.pop();
	}

	public static void evaluateParentheses(Stack<String> operators, Stack<String> operands, String input) {

		if (input.equals("(")) {
			operators.push(input);

		} else if (input.equals(")")) {

			while (!operators.isEmpty() && !operators.peek().equals("(")) {
				String operand2 = operands.pop();
				String operand1 = operands.pop();
				String operator = operators.pop();

				operands.push(" " + operator + " " + operand1 + " " + operand2);
			}

			// pops (
			operators.pop();
		}
	}

	public static void pushOperatorPrefix(Stack<String> operands, Stack<String> operators, String operator) {

		while (!operators.isEmpty() && precedence(operator) <= precedence(operators.peek()) && !operators.peek().equals("(")) {
			String op2 = operands.pop();
			String op1 = operands.pop();
			operands.push(" " + operators.pop() + " " + op1 + " " + op2);
		}
		operators.push(operator);
	}