AlgoViz
HomeStack

Prefix to Infix Conversion

Medium

Scan right to left, combine two operands

Problem

Convert a prefix expression (+a*bc) to infix ((a+(b*c))).

In simple words

Scan right to left; pop two operands for each operator and wrap them in brackets.

The idea

Walk from the right pushing operands; on an operator, pop two and push the bracketed string joining them. Right-to-left is what makes an operator's operands already available on the stack.

The trick

  • The first popped operand is the left one in prefix.
  • Wrap each combination in brackets to preserve the grouping.

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 — *+ab-cd Values: 0.

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

Input

array
[0]

Output

answer
—

Check yourself

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

Example

Input:
*+ab-cd
Output:
((a+b)*(c-d))

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

Finished the walkthrough? Add it to your streak.