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. In this method, 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. In this method, 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.


prefix to postfix recursion

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

Solution 1: Use stack

Java

JavaScript

Python

Doodle

prefix to postfix stack doodle

Solution 2: Use recursion

Java

JavaScript

Python

Doodle

prefix to postfix recursion doodle

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!


Download PrefixToPostfix.java
Java Coding Interview Pocket Book (2nd Edition)
Covert prefix to postfix using stack or recursion (YouTube)

Comments are closed