AlgoViz
HomeStack

Prefix to Postfix Conversion

Medium

Right to left, operator last

Problem

Convert a prefix expression to postfix.

In simple words

Scan right to left; for each operator, pop two operands and append the operator after them.

The idea

Same right-to-left scan, but when combining two popped operands the operator is appended after them instead of between. Only the concatenation order differs from the infix version.

The trick

  • Build `left + right + op`; the operand order is preserved.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — *-a/bc-/akl Values: 0.

1/2
Optimal
timeO(n)spaceO(n)
1scan right->left; push operands2on operator: pop a,b; push a+b+op

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
*-a/bc-/akl
Output:
abc/-akl/-*

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.