Infix To Prefix Conversion

Algorithm for converting Infix to Prefix:

• Reverse the Expression and parse the inputs in the expression one by one.
• If the input is an operand, then place it in the output buffer.
• If the input is an operator, push it into the stack.
• If the operator in stack has equal or higher precedence than input operator, then pop the operator  present in stack and add it to output buffer.
• If the input is an close brace, push it into the stack.
• If the input is a open brace, pop elements in stack one by one until we encounter open brace.  Discard braces while writing to output buffer.

After completing all processing, reverse the data in output buffer.  And the result will be our prefix notation of the given expression.

Infix Expression:  (a - b) / (c + d)
Reverse the given Expression: ) d + c (  /  ) b - a (
Input: )
Input is close brace.  So, place it into the stack.

|      |
|  )   |           Output:
 ------

Input: d
Place the operand in output buffer.

|      |
|  )   |          Output:  d
 ------

Input: +
Place the operator into the stack.

|       |
|  +   |
|  )   |          Output:  d
 ------

Input: c
Place the operand in output buffer
|       |
|  +   |
|  )    |         Output:  dc
 ------

Input: (
Pop '+' and ')'

|       |
|       |
|       |         Output:  dc+
 ------

Input: /
Push the operator into the stack.

|       |
|       |
|  /   |         Output:  dc+
 ------

Input: )
Push close brace into the stack.

|       |
|  )    |
|  /   |         Output:  dc+
 ------

Input: b
Place the operand in output buffer.

|       |
|  )    |
|  /    |         Output:  dc+b
 ------

Input: -
Place the operator into the stack.

|  -    |
|  )    |
|  /    |         Output:  dc+b
 -------

Input: a
Place the operand in output buffer.

|  -    |
|  )    |
|  /    |         Output:  dc+ba
 -------

Input: (
Pop all elements until we get close brace.

|       |
|       |
|  /    |         Output:  dc+ba-
 ------

No more input to parse.  So, pop all other elements from the stack

|       |
|       |
|       |         Output:  dc+ba-/
 ------

Reverse the output.
Prefix Notation:  -/ab+cd

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 Infix To Prefix Conversion:

---

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  #define OPERATORS 7

  struct node {
        int data;
        struct node *next;
  };

  struct node *top = NULL;

  /* Operators and its precedence */
  char precedence[OPERATORS][2] = { {'(', 0}, {'+', 1}, {'-', 1},
                             {'*', 2}, {'/', 2}, {'%', 2},
                             {')', 3}};

  /* create a node with given data */
  struct node* createNode(int data) {
        struct node *ptr = (struct node *) malloc(sizeof (struct node));
        ptr->data = data;
        ptr->next = NULL;
  }

  /* Push the given data into the stack */
  void push(int data) {
        struct node *ptr = createNode(data);
        if (top == NULL) {
                top = ptr;
                return;
        }
        ptr->next = top;
        top = ptr;
  }

  /* Pop the top element from the stack */

  int pop() {

        struct node *ptr;

        int data;

        if (top == NULL)

                return -1;

        ptr = top;

        top = top->next;

        data = ptr->data;

        free (ptr);

        return (data);

 }

  /* get the index of the given operator */

  int getIndex(int data) {

        int i;

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

                if (data == precedence[i][0])

                        return i;

        }

  }

  /* string reverse operation */

  void strrev(char str[]) {

        int i = 0, j = 0;

        char ptr[100];

        while (str[i] != '\0')

                i++;

        for (i = i-1; i >=0; i--) {

                ptr[j] = str[i];

                j++;

        }

        ptr[j] = '\0';

        strcpy(str, ptr);

  }

  /* infix to prefix conversion */

  void infix2prefix(char infix[], char postfix[]) {

        int i, j = 0, data;

        int index1, index2;

        for (i = 0; i < strlen(infix); i++) {

                /* if the given i/p is operand, place in output buffer */

                if (tolower(infix[i]) >= 'a' && tolower(infix[i] <= 'z'))

                        postfix[j++] = infix[i];

                else if (infix[i] == '(') {

                        /*

                         * if the i/p is open brace, pop the elements one

                         * by one until we encounter close brace

                         */

                        data = pop();

                        while (data != ')' && data != -1) {

                                postfix[j++] = data;

                                data = pop();

                        }

                } else if (infix[i] == ')') {

                        /* if the i/p is close brace, push it into stack */

                        push(infix[i]);

                } else {

                        data = pop();

                        if (data == -1) {

                                /* stack is empty.. so, push current i/p */

                                push(infix[i]);

                                continue;

                        } else if (data == ')') {

                                /*

                                 * if stack top element is close brace, then

                                 * push current input to stack

                                 */

                                push(data);

                                push(infix[i]);

                                continue;

                        }

                        index1 = getIndex(data);

                        index2 = getIndex(infix[i]);

                        /* Precedence manipulation b/w stack operator and current i/p */

                        while (precedence[index1][1] > precedence[index2][1]) {

                                postfix[j++] = data;

                                data = pop();

                                if (data == -1 || data == ')') {

                                        push(infix[i]);

                                        break;

                                }

                                index1 = getIndex(data);

                        }

                        if (data != -1) {

                                push(data);

                                push(infix[i]);

                        }

                }

        }

        /* Pop the remaining data from stack after all processing*/

        while (1) {

                if ((data = pop()) == -1)

                        break;

                postfix[j++] = data;

        }

        postfix[j] = '\0';

  }

  int main () {

        char str[100], output[100];

        printf("Enter ur Expression:");

        fgets(str, 100, stdin);

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

        strrev(str);

        infix2prefix(str, output);

        /* reverse the output to get prefix notation */

        strrev(output);

        printf("Ouput: %s\n", output);

        return 0;

  }

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

  jp@jp-VirtualBox:$ ./a.out 
  Enter ur Expression:(a-b)/(c+d)
  Ouput: /-ab+cd