The traditional method of writing mathematical expressions is called infix expressions.
It is written as . The operator is placed between two operands (e.g., A+B or (A*B)/Q).
Infix expressions are easy to understand and evaluate for humans but hard for computers to parse due to operator precedence, associativity rules, and parentheses.
To make parsing easier for computers, we use postfix and prefix notations.

In a prefix expression, the operator is placed before the operands.
The expression is in the form .
Prefix expressions work similarly to postfix expressions. While evaluating, operators are applied immediately to the operands on the right of the operator.
Prefix expressions are also called Polish notation.

Reverse the given infix expression.
Scan the expression from left to right.
When an operand is encountered, print it directly.
If the operator is encountered and the stack is empty, push the operator into the stack.
If the incoming operator has higher precedence than the top of the stack, push it into the stack.
If the incoming operator has the same precedence as the top of the stack, push it into the stack.
If the incoming operator has lower precedence than the top of the stack, pop and print the top of the stack. Then, test the incoming operator against the top of the stack again and continue popping operators from the stack until it finds an operator with lower or the same precedence.
If the incoming operator has the same precedence as the top of the stack and the incoming operator is '^', pop the top of the stack until the condition is met. If not, push the '^' operator.
If the operator is ')', push it into the stack.
If the operator is '(', pop all operators from the stack until a ')' is encountered.
If the top of the stack is ')', push the operator onto the stack.
At the end of the expression, pop and print all remaining operators from the stack.
Finally, reverse the output and print it as the prefix expression.

Code

1234