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 are some steps (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)
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