FOR FREE MATERIALS

Prefix to Postfix Conversion

Back to Programming

Description

Prefix: Similarly, the expression in which the operator appears before the operands is known as prefix expression. For example, +ab, where a and b are operands, + is an operator that appears before the operands a and b.

Postfix: The expression in which the operator appears after the operands is known as postfix expression. For example, ab+, where a and b are operands, + is an operator that appears after the operands a and b.

Prefix: + - 5 * 4 3 2

Postfix: 5 4 3 * - 2 +

Conversion from prefix to postfix:

There is rules/algorithm for converting an expression from prefix to postfix. The rules are:

The postfix expression should be scanned from left to right.
If the symbol is an operand then it will be pushed into the stack.
If the symbol is an operator then

a. Pop the top two operand op1, op2 from the stack.

b. Put the operator after two recently pop operand and form a string like (op1 op2 +).

c. Push the resulting string into the stack.

4. After completion of the iteration when the stack contains only one string then we can treat this string as a postfix expression.

5. Return the result.

Input: + - 5 * 4 3 2 (Prefix)

So, output: 5 4 3* - 2 + (Postfix)

Code

Time complexity:

To convert prefix to postfix we have to scan n symbols. So, Time complexity for prefix to postfix conversion is O(n).

Space complexity:

We require n stack to convert prefix to postfix. So, space complexity is O(n).

Contributed by

Debashis Roy Faculty of Computer Science Department, JCC College, University of Calcutta

Please Login to Bookmark