Given a prefix math expression, which has upper letters as its variables, and four operators ‘+’, ‘-’, ‘*’, and ‘/’. Please print the infix expression and add necessary parentheses if needed.
As we know, the operators ‘*’ and ‘/’ are performed before the operators ‘+’ and ‘-’. Hence, if we want to do the latter operation first, it requires adding parentheses on it.
For example, if we have a prefix expression *+ABC, we would perform A+B first and then perform (A+B)*C. In this case, the infix expression would be (A+B)*C rather than A+B*C.
The situation above is the only situation that requires adding parentheses. If we have a prefix expression *A*BC, it seems that we should perform B*C first and then perform A*(B*C). However, whether performing A*B first or performing B*C first would lead to the same result, due to the associative property (結合律). Thus it is fine to have the infix expression be A*B*C. Since we want to add only necessary parentheses, the expression A*B*C would be the answer rather than A*(B*C).
Hint: You can combine two homework. Build a syntax tree and print the infix expression with the necessary parentheses.
The input contains one line, a prefix expression, which has only upper letters and four operators ‘+’, ‘-’, ‘*’ and ‘/’. The length of the prefix expression is less than 800.
The output is an infix expression, with some parentheses, if necessarily.