Algorithm for converting Infix to Postfix:
Infix Expression: (a - b) / (c + d)
Input: (
Input is open brace. So, place it into the stack.
| |
| ( | Output:
------
Input: a
Place the operand in output buffer.
| |
| ( | Output: a
------
Input: -
Place the operator into the stack.
| |
| - |
| ( | Output: a
------
Input: b
Place the operand in output buffer
| |
| - |
| ( | Output: ab
-------
Input: )
Pop '-' and '('
| |
| |
| | Output: ab-
-------
Input: /
Push the operator into the stack.
| |
| |
| / | Output: ab-
-------
Input: (
Push open brace into the stack.
| |
| ( |
| / | Output: ab-
-------
Input: c
Place the operand in output buffer.
| |
| ( |
| / | Output: ab-c
-------
Input: +
Place the operator into the stack.
| + |
| ( |
| / | Output: ab-c
-------
Input: d
Place the operand in output buffer.
| + |
| ( |
| / | Output: ab-cd
-------
Input: )
Pop all elements until we get open brace.
| |
| |
| / | Output: ab-cd+
------
No more input to parse. So, pop all other elements from the stack
| |
| |
| | Output: 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 Post-fix Conversion:
- If the input is an operand, then place it into 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 open brace, push it into the stack
- If the input is a close brace, pop elements in stack one by one until we encounter close brace. Discard braces while writing to output buffer.
Infix Expression: (a - b) / (c + d)
Input: (
Input is open brace. So, place it into the stack.
| |
| ( | Output:
------
Input: a
Place the operand in output buffer.
| |
| ( | Output: a
------
Input: -
Place the operator into the stack.
| |
| - |
| ( | Output: a
------
Input: b
Place the operand in output buffer
| |
| - |
| ( | Output: ab
-------
Input: )
Pop '-' and '('
| |
| |
| | Output: ab-
-------
Input: /
Push the operator into the stack.
| |
| |
| / | Output: ab-
-------
Input: (
Push open brace into the stack.
| |
| ( |
| / | Output: ab-
-------
Input: c
Place the operand in output buffer.
| |
| ( |
| / | Output: ab-c
-------
Input: +
Place the operator into the stack.
| + |
| ( |
| / | Output: ab-c
-------
Input: d
Place the operand in output buffer.
| + |
| ( |
| / | Output: ab-cd
-------
Input: )
Pop all elements until we get open brace.
| |
| |
| / | Output: ab-cd+
------
No more input to parse. So, pop all other elements from the stack
| |
| |
| | Output: 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
#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}};
/* creating node with the 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 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 operator in precedence array */
int getIndex(int data) {
int i;
for (i = 0; i < OPERATORS; i++) {
if (data == precedence[i][0])
return i;
}
}
/* API to do infix to postfix conversion */
void infix2postfix(char infix[], char postfix[]) {
int i, j = 0, data;
int index1, index2;
for (i = 0; i < strlen(infix); i++) {
/* given input is operator or not */
if (tolower(infix[i]) >= 'a' && tolower(infix[i] <= 'z'))
postfix[j++] = infix[i];
else if (infix[i] == ')') {
/*
* Input is close brace. So, pop all
* elements until we encounter open brace
*/
data = pop();
while (data != '(' && data != -1) {
postfix[j++] = data;
data = pop();
}
} else if (infix[i] == '(') {
/* open brace - push it into stack */
push(infix[i]);
} else {
/*
* take top element from the stack to
* check for operator precedence, to know
* whether the top element is open brace etc.
*/
data = pop();
if (data == -1) {
push(infix[i]);
continue;
} else if (data == '(') {
/*
* if top element in stack is open brace,
* then push both top(data) and current input
* into the stack.
*/
push(data);
push(infix[i]);
continue;
}
index1 = getIndex(data);
index2 = getIndex(infix[i]);
while (precedence[index1][1] >= precedence[index2][1]) {
/*
* if the operator in stack has higher precedence
* than the input operator, then pop the stack
* operator and place it in output buffer.
*/
postfix[j++] = data;
data = pop();
if (data == -1) {
push(infix[i]);
break;
} else if (data == '(') {
push(data);
push(infix[i]);
data = -1;
break;
}
index1 = getIndex(data);
}
if (data != -1) {
push(data);
push(infix[i]);
}
}
}
/* After processing all inputs, pop all other elements from stack */
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);
infix2postfix(str, output);
printf("Ouput: %s", output);
return 0;
}
Output: (C Program To Implement Infix To PostFix Conversion)
jp@jp-VirtualBox:$ ./a.out
Enter ur Expression:a+b*(c-d)/(e-f)
Ouput: abcd-*ef-/+
Enter ur Expression:a+b*(c-d)/(e-f)
Ouput: abcd-*ef-/+
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 ...(and add push the input operator to the stack) - this statement was missing. Please add it
ReplyDelete