0000 Postfix to Prefix conversation | MyCareerwise
View
30000
logo
Login Register

FOR FREE CONTENT

Postfix to Prefix conversation

Back to Programming

Description

Postfix: Similarly, 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: 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:  5 4 3 * - 2 +

Prefix: + - 5 * 4 3 2

 

Conversion from postfix to prefix:

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

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

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

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

      c. Push the resultant string into a stack.

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

5. Return the result.

 

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

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

Code

Time complexity:

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

 

Space complexity:

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

Related

Contributed by

Please Login to Bookmark