Prefix to Infix Conversion

The problem. Given a valid prefix expression — every operator written before its two operands — convert it to infix, wrapping every operation in brackets. Operands are single letters or digits, and the operators are + - * / ^. For example, *+AB-CD becomes ((A+B)*(C-D)).

Example

Input:  "*+AB-CD"        Output: "((A+B)*(C-D))"
Input:  "*-A/BC-/AKL"    Output: "((A-(B/C))*((A/K)-L))"
Input:  "A"              Output: "A"

In prefix, an operator is followed by its left operand and then its right operand — and each operand may itself be a whole expression. The Infix, prefix and postfix lesson showed how to evaluate prefix with a stack; converting is the same scan with strings instead of numbers.