AlgoViz
HomeStack

Postfix to Prefix Conversion

Medium

Left to right, operator first

Problem

Convert a postfix expression to prefix.

In simple words

Scan left to right; for each operator, pop two operands and put the operator in front.

The idea

Postfix is read left to right: push operands, and on an operator pop two and push the operator followed by them. The second value popped is the left operand, which is the detail that trips people up.

The trick

  • Second pop is the left operand — build `op + left + right`.

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 — abc/-ak/l-* Values: 0.

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

Input

array
[0]

Output

answer
—

Check yourself

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

Example

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

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

Finished the walkthrough? Add it to your streak.