Prefix to postfix (2 solutions) – Code

In mathematics expressions, there are infix, prefix and postfix notations. Infix notation is characterized by the placement of operators between operands. For example, the plus sign in 2 + 2. Prefix notation is a notation in which operators precede their operands, such as + 3 4. Postfix notation is a notation in which operators follow their operands, for example 3 4 +.

We usually use Stack to convert prefix to postfix. We start from the back of expression and scan each character. If the character is letter, we push the operands in stack. If the character is operator, such as +,-, * or /, we pop items from stack and compose postfix. Then push the new expression in stack.

This question can be also solved using recursion. We start from the beginning of the expression. If the character is operator, it calls itself to move on to next iteration. Otherwise compose the postfix.

Google Interview Question (CareerCup):
convert Prefix to Postfix using recursion
+ * A B / C D -> A B * C D / +

Java Code:

Output:
prefix: +*AB/CD
postfix(stack): AB*CD/+
postfix(recursion): AB*CD/+

O Notation:
Time complexity: O(n)
Space complexity: O(n)

Note:
If you have any questions or want to put comments, please post at youtube. I will answer you!

Action Items:
Download PrefixToPostfix.java
Convert prefix to postfix tutorial
Blackout Math puzzle using Stacks at github

Comments are closed