Postfix To Infix Conversion

Algorithm For Postfix To Infix Conversion:

• 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(operand + operator + operand) containing scanned operator and two popped elements. Then, 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.

7$6

|      |
|      |
+----+

Push the resultant string "7$6" into the stack.

|        |
| 7$6  |
+------+

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

|  5    |
| 7$6  |
+------+



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 "*7$6*5" string into the stack.

|          |
| 7$6*5 |
+--------+

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

|    5     |
| 7$6*5 |
+--------+


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

|              |
| 7$6*5-5   |
+------------+

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

|      1      |
| 7$6*5-5  |
+-----------+

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

|      7       |
|      1       |
| 7$6*5-5   |
+------------+

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.

|               |
|    1/7      |
| 7$6*5-5  |
+-----------+

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

|      9       | 
|    1/7      |
| 7$6*5-5   |
+------------+

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

|      9       |
|      9       | 
|    1/7      |
| 7$6*5-5   |
+------------+

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.

|              |
|   9+9      | 
|   1/7      |
| 7$6*5-5  |
+-----------+

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

|              | 
| 1/7/9+9  |
| 7$6*5-5   |
+------------+

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.

|      |
|      |
+-----+

Resultant Infix Expression: 7$6*5-5 + 1/7/9+9

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 Infix Conversion(in C):

---

  #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], buffer2[BUFSIZE];

        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;

                        }

                }

                /*

                 * scanned character is operator, pop two

                 * elements from stack, form a string composed

                 * of scanned character and the two popped

                 * element from the stack

                 */

                if (flag) {

                        pop(buffer1);

                        pop(buffer2);

                        len = strlen(buffer2);

                        buffer2[len++] = expr[i];

                        buffer2[len] = '\0';

                        strcat(buffer2, buffer1);

                        push(buffer2);

                } else {

                        /* scanned input is digit, push it into the stack */

                        buffer1[0] = expr[i];

                        buffer1[1] = '\0';

                        push(buffer1);

                }

                flag = 0;

        }

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

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

        printf("Infix: ");

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

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

        }

        printf("\n\n");

        return 0;

  }

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

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your postfix expression:76$5*5-17/99+/+
  Postfix to Infix Conversion:
  Posfix: 76$5*5-17/99+/+
  Infix: 7$6*5-5+1/7/9+9