This blog is under construction

Sunday, 26 May 2013

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



1 comment:

  1. Conversion from Prefix to Postfix

    The algorithm for converting a Prefix expression to a Postfix notation is as follows:

    Accept a prefix string from the user.
    Start scanning the string from right one character at a time.
    If it is an operand, push it in stack.
    If it is an operator, pop opnd1, opnd2 and concatenate them in the order (opnd1, opnd2, optr) as follows:
    strcpy(arr,opnd1);
    strcat(arr,opnd2);
    stracat(arr,optr);

    Push the result in the stack.

    Repeat these steps until arr of input prefix string ends.
    Pop the remaining element of the stack, which is the required Postfix notation equivalent to a given Prefix notation.

    ReplyDelete