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 +. This post introduces how to convert an expression from prefix to postfix. There are two methods, stack and recursion. We use letters as operands in the expression.

The common approach is to 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 a letter, we push the operands in stack. If the character is an operator, such as +,-, * or /, we pop two items from the stack. They are two operands. We concatenate two operands and the operator as one string. It is a postfix sub-expression. Then push the new expression in stack. At the end, the top element in stack is the final postfix expression.

We can also use recursion. In this method, we start from the beginning of the expression. Since in an infix expression, the first character is always operator. The recursive method removes the first character and save it to an variable op. Next the method calls itself twice recursively to get the following two operands, saved as op1 and op2. Then declare a list to store a postfix sub-expression. This expression store op1, op2, and op as elements of list in sequence. When the last recursion returns from call stacks, the list has the final postfix expression.

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

What are the methods to convert prefix to postfix ?

There are two methods. One is using stack. You start from the back of infix, push operands in a stack. If the input is an operator, you pop operands, and concatenate operands and operator as a postfix, and save it back to the stack. Another method is using recursion. Since the first term in infix is always operator, you remove it and save it as op. Call the recursive method twice to get two operands. Declare a list to save two operands and op in sequence in the list. The return from all recursions (call stacks) is the final postfix expression.

Comments are closed