AlgoViz
HomeStack

Infix to Prefix Conversion

Medium

Reverse, convert, reverse again

Problem

Convert an infix expression to prefix.

In simple words

Reverse, convert to postfix with tweaked precedence, then reverse the result.

The idea

Reverse the expression (swapping each bracket for its mirror), run the postfix conversion with the associativity rules flipped, then reverse the result. Reusing the postfix algorithm avoids writing a second parser.

The trick

  • Swap '(' and ')' when reversing, or the barriers break.
  • Associativity flips in the reversed pass.

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-b/c)*(a/k-l) Values: 0.

1/2
Optimal
timeO(n)spaceO(n)
1reverse infix (swap brackets)2convert to postfix3reverse output

Input

array
[0]

Output

answer
—

Check yourself

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

Example

Input:
(a-b/c)*(a/k-l)
Output:
*-a/bc-/akl

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

Finished the walkthrough? Add it to your streak.