Find prefix of following postfix AB*CD/+

Concept

A postfix (Reverse Polish) expression places each binary operator immediately after its two operands, while a prefix (Polish) expression places each operator immediately before its two operands. Converting postfix to prefix is a single left-to-right stack scan: push every operand; on each operator, pop the two most recent sub-expressions and build a new sub-expression by writing the operator first, then the operands in their original left-to-right order (the second-popped sub-expression is the left operand, the first-popped is the right operand).

Application

Scan the postfix string AB*CD/+ left to right, maintaining a stack of partial prefix strings:

1. Read A — an operand. Stack: [A].

2. Read B — an operand. Stack: [A, B].

3. Read * — pop the top two (second-from-top is the first operand): pop B then A, form *AB, push it. Stack: [*AB].

4. Read C — an operand. Stack: [*AB, C].

5. Read D — an operand. Stack: [*AB, C, D].

6. Read / — pop D then C, form /CD, push it. Stack: [*AB, /CD].

7. Read + — pop /CD then *AB, form + with operands *AB and /CD, giving +*AB/CD. Stack: [+*AB/CD].

The single remaining stack entry is the prefix expression: +*AB/CD.

Cross-check

Convert the prefix result back to infix to confirm it matches the original. +*AB/CD means + ( *AB , /CD ) = (A*B) + (C/D). The given postfix AB*CD/+ also evaluates to (A*B)+(C/D): AB* gives A*B, CD/ gives C/D, and the trailing + adds them. Both forms describe the same expression tree, so +*AB/CD is the correct prefix.