Postfix To Prefix Conversion

Algorithm To Convert An Expression From Postfix To Prefix Notation:

• If the scanned character is a digit, then push it into the stack.
• If the scanned character is an operator, then pop two elements from the stack.  Form a string containing scanned operator and two popped elements.  Push the resultant string into the stack.

Example:  7  6  $  5  * 5 - 1  7  /  9  9  +  /  +

Step 1:  Scanned character is a digit '7'.  So, push it into the stack.

|      |

|  7  |

+-----+

Step 2:  Scanned character is a digit '6'.  So, push it into the stack.

|  6  |

|  7  |

+-----+

Step 3:  Scanned character is an operator '$'.  Pop two elements from the stack and form a string containing the scanned operator and two popped elements.

$76

|      |

|      |

+-----+

Push the resultant string "$76" into the stack.

|        |

| $76  |

+------+

Step 4:  Scanned character is a digit '5'.  So, push it into the stack.

|  5    |

| $76  |

+------+

Step 5:  Scanned character is an operator '*'.  So, pop two elements from the stack and form  a string containing the scanned operator and two popped elements.  Then, push the resultant "*$765" string into the stack.

|          |

| *$765 |

+--------+

Step 6:  Scanned character is digit '5'.  Push it into the stack.

|    5     |

| *$765 |

+--------+

Step 7:  Scanned character is an operator '-'.  Pop '5' and "*$765" from the stack.  Form a string containing the scanned operator and two popped elements.  Push the resultant string into the stack

|              |

| -*$7655  |

+-----------+

Step 8:  Scanned character is digit '1'.  Push it into the stack.

|      1      |

| -*$7655  |

+-----------+

Step 9:  Scanned character is digit '7'.  Push it into the stack.

|      7       |

|      1       |

| -*$7655   |

+------------+

Step 10:  Scanned character is an operator '/'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|               |

|    /17      |

| -*$7655  |

+-----------+

Step 11:  Scanned character is a digit '9'.  Push it into the stack.

|      9       | 

|    /17      |

| -*$7655   |

+------------+

Step 12:  Scanned character is a digit '9'.  Push it into the stack.

|      9       |

|      9       | 

|    /17      |

| -*$7655   |

+------------+

Step 13:  Scanned character is an operator '+'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|              |

|   +99      | 

|    /17     |

| -*$7655  |

+-----------+

Step 14:  Scanned character is an operator '/'.

|              | 

| //17+99  |

| -*$7655   |

+------------+

Step 15:  Scanned character is an operator '+'.  Pop top two elements from the stack.  Form a string containing the scanned operator and two popped elements, push the resultant string into the stack.

|      |

|      |

+-----+

+ - * $ 7655//17+99

Resultant Prefix Expression: + - * $ 7655//17+99

See Also:
C Program To Implement Postfix To Infix Conversion
C Program To Implement Postfix To Prefix Conversion
C Program To Implement Infix To Prefix Conversion
C Program To Implement Infix To Postfix Conversion
How To Evaluate Postfix Expressions
C Program To Evaluate Postfix Expression Using Array
C Program To Evaluate Postfix Expression Using Linked List
How To Balance The Given Expressions
C Program For Balancing Expressions Using Array
C Program For Balancing Expressions Using Linked List

Example Program To Implement Postfix To Prefix Conversion:

---

  #include <stdio.h>
  #include <string.h>

  #define BUFSIZE 100

  char operator[] = {'/', '*', '+', '-', '%', '$'};
  char stack[BUFSIZE][BUFSIZE];
  int top = -1;

  /* push input string into the stack */
  void push(char *substr) {
        char *temp;
        if (top >= BUFSIZE -1) {
                printf("Stack Overflow\n");
        } else {
                top++;
                strcpy(stack[top], substr);
        }
        return;
  }

  /* pop top element from the stack & append input string with top element */
  void pop(char *res) {
        if (top == -1) {
                printf("Stack Underflow\n");
                return;
        } else {
                strcpy(res, stack[top]);
                top--;
        }
        return;
  }

  int main() {

        char expr[BUFSIZE], buffer1[BUFSIZE];

        char str[BUFSIZE], buffer2[BUFSIZE], op[2];

        int i, j, len, flag = 0;

        printf("Enter your postfix expression:");

        fgets(expr, 100, stdin);

        expr[strlen(expr) - 1] = '\0';

        for (i = 0; expr[i] != '\0'; i++) {

                if (expr[i] == ' ')

                        continue;

                for (j = 0; j < 6; j++) {

                        if (expr[i] == operator[j]) {

                                flag = 1;

                                break;

                        }

                }

                if (flag) {

                        /*

                         * scanned char is an operator.  So, pop

                         * two elements from the stack and form a

                         * string composed on scanned char & two

                         * popped elements

                         */

                        pop(buffer1);

                        pop(buffer2);

                        op[0] = expr[i];

                        op[1] = '\0';

                        strcpy(str, op);

                        strcat(str, buffer2);

                        strcat(str, buffer1);

                        push(str);

                } else {

                        /* scanned character is digit, push it into ths stack */

                        op[0] = expr[i];

                        op[1] = '\0';

                        push(op);

                }

                flag = 0;

        }

        printf("Postfix to Prefix Conversion:\n");

        printf("Posfix: %s\n", expr);

        printf("Prefix: ");

        for (i = 0; i <= top; i++) {

                printf("%s",stack[i]);

        }

        printf("\n\n");

        return 0;

  }

  Output: ( C Program To Implement Postfix To Prefix Conversion)

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your postfix expression:76$5*5-17/99+/+
  Postfix to Prefix Conversion:
  Posfix: 76$5*5-17/99+/+
  Prefix: +-*$7655//17+99