Infix to Prefix

Write a class called InfixToPrefix that prompts the user to enter an expression in infix form (possibly only partially parenthesized), and then prints an equivalent expression in fully parenthesized prefix form -- where operators come before their operands, and every operator and its operands appear in parentheses.

You may assume that the user input will separate operand and operator tokens with spaces, and the operators include only "+", "-", "*", "/", and "^".

Sample Run

$ java InfixToPrefix
Enter an infix expression to convert to prefix form:
A + B * C ^ D - E
( - ( + A ( * B ( ^ C D ) ) ) E )