Prefix to postfix (2 solutions) – stack and recursion

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.

How to convert prefix to postfix using recursion?

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:
convert Prefix_to_Postfix using recursion
+ * A B / C D -> A B * C D / +

Java

JavaScript

Python

Doodle

prefix to postfix stack doodle

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

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


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

Comments are closed