Infix to Prefix Conversion

In this article, we will talk about how can we convert a given infix expression to its prefix form.

Before we proceed, make sure you have some knowledge about the stack data structure. If not, you can refer to this article.

Stack Data Structure - GeeksforGeeks

What are infix and prefix expressions?

An Infix Expression is a string containing a set of operators and operands and is of the form aXb, where a and b are operands, and X denotes any binary operator like +, -, *, / or ^.

Similarly, a Prefix Expression is a string containing a set of operators and operands and is of the form Xab, where a and b are operands, and X denotes any binary operator like +, -, *, / or ^.

Want to read this story later? Save it in Journal.

Need for prefix expressions

Infix expressions can be easily understood by humans, though prefix or postfix expression is simpler to parse for a machine. The enormous favourable position in pre-/postfix expression is that there never emerges any inquiries of operator precedence. For instance, consider the infix expression a # b $ c. Presently, we don’t have any idea what those operators mean, so there are two potential relating prefix expressions: $ # a b c and # a $ b c. Without realising the rules governing these operators, the infix expression is basically useless. Or on the other hand, to place it in increasingly broad terms: it is conceivable to reestablish the parse tree from a pre-/postfix expression with no extra information, yet the equivalent isn’t valid for infix expressions.

We can obtain an equivalent postfix or prefix expression for any given infix expression. For conversion from infix to postfix, refer to this article.

Now we will see the algorithm to convert any given infix expression to its prefix form.

Algorithm

Step 1: In the input infix expression, replace ‘(‘ by ‘)’ and ‘)‘ by ‘(’ and reverse the expression. For eg, (a+b)*c becomes c*(b+a).

Step 2: Convert the modified string step 1 to its postfix form using the algorithm for infix to postfix conversion explained in the above-mentioned article.

Step 3: Reverse the expression obtained in step 2. This is the final prefix expression for the given infix expression.

Examples-
Input : a+b*c/d
Output : +a*b/cd
Input : a+(b-c^(d+e))*f
Output : +a*-b^c+def

Python Implementation

Given below is the Python implementation of the above algorithm.

JavaScript Implementation

Given below is the JS implementation of the above algorithm.

Thanks for reading! :)

📝 Save this story in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.