Algorithm to Convert Infix Expression to Postfix Notation
Infix to Postfix Conversion Algorithm
Infix notation is the most common form of writing expressions, where operators are placed between
operands (e.g., A + B). On the other hand, postfix notation (also called Reverse Polish Notation or
RPN) places operators after their operands (e.g., A B +).
To convert infix to postfix, we use a stack to help reorder the operators and operands.
Steps for Infix to Postfix Conversion:
1. Initialize an empty stack for operators and an empty list (or string) for the output.
2. Scan the infix expression from left to right.
• If the character is an operand (number or variable), add it directly to the output.
• If the character is an open parenthesis (, push it onto the stack.
• If the character is a close parenthesis ), pop from the stack to the output until an
open parenthesis ( is encountered at the top of the stack.
• If the character is an operator (like +, -, *, /), pop operators from the stack to the
output until you encounter an operator of lower precedence or a left parenthesis.
Push the current operator onto the stack.
3. After scanning the entire infix expression, pop any remaining operators from the stack to
the output.
Operator Precedence:
• ^ (exponentiation) > * (multiplication) = / (division) > + (addition) = - (subtraction)
• Operators with equal precedence (like * and /) are processed based on associativity: * and
/ are left-associative.
Example of Infix to Postfix Conversion:
Consider the infix expression: A + B * (C - D)
• Step-by-step conversion:
• Operand A → Add to the output: A
• Operator + → Push onto stack: +
• Operand B → Add to the output: A B
• Operator * → Push onto stack: + *
• Open parenthesis ( → Push onto stack: + * (
• Operand C → Add to the output: A B C
• Operator - → Push onto stack: + * ( -
• Operand D → Add to the output: A B C D
• Close parenthesis ) → Pop until (, output -, stack becomes + *
• End of expression → Pop remaining operators: + * -
• Postfix expression: A B C D - * +
Algorithm to Evaluate Postfix Expression
1. Initialize an empty stack.
2. Scan the postfix expression from left to right:
• If the character is an operand, push it onto the stack.
• If the character is an operator, pop two operands from the stack, apply the operator,
and push the result back onto the stack.
3. At the end of the expression, the stack will contain the result.
Example of Postfix Evaluation:
For the postfix expression A B C D - * + (where A=2, B=3, C=5, D=1):
1. Push A=2, B=3, C=5, D=1 onto the stack.
2. Apply C - D = 5 - 1 = 4, push the result 4.
3. Apply B * 4 = 3 * 4 = 12, push the result 12.
4. Apply A + 12 = 2 + 12 = 14, push the result 14.
5. The result is 14.
C Code to Implement Infix to Postfix Conversion and Evaluation
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#define MAX 100
// Structure for stack
typedef struct Stack {
int top;
char items[MAX];
} Stack;
// Stack functions
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAX - 1;
}
void push(Stack *s, char value) {
if (!isFull(s))
s->items[++(s->top)] = value;
}
char pop(Stack *s) {
if (!isEmpty(s))
return s->items[(s->top)--];
return -1;
}
char peek(Stack *s) {
if (!isEmpty(s))
return s->items[s->top];
return -1;
}
// Operator precedence
int precedence(char op) {
if (op == '^')
return 3;
if (op == '*' || op == '/')
return 2;
if (op == '+' || op == '-')
return 1;
return 0;
}
// Infix to Postfix Conversion
void infixToPostfix(char *infix, char *postfix) {
Stack s;
initStack(&s);
int k = 0;
for (int i = 0; infix[i] != '\0'; i++) {
if (isalnum(infix[i])) {
postfix[k++] = infix[i]; // If operand, add to postfix
} else if (infix[i] == '(') {
push(&s, infix[i]); // If '(', push to stack
} else if (infix[i] == ')') {
while (!isEmpty(&s) && peek(&s) != '(') {
postfix[k++] = pop(&s); // Pop until '('
}
pop(&s); // Remove '(' from stack
} else { // If operator
while (!isEmpty(&s) && precedence(peek(&s)) >= precedence(infix[i]))
{
postfix[k++] = pop(&s); // Pop operators with higher or equal
precedence
}
push(&s, infix[i]); // Push current operator to stack
}
}
while (!isEmpty(&s)) {
postfix[k++] = pop(&s); // Pop remaining operators from stack
}
postfix[k] = '\0';
}
// Evaluate Postfix Expression
int evaluatePostfix(char *postfix) {
Stack s;
initStack(&s);
int val1, val2, result;
for (int i = 0; postfix[i] != '\0'; i++) {
if (isdigit(postfix[i])) {
push(&s, postfix[i] - '0'); // Push operand to stack
} else {
val2 = pop(&s); // Pop operands from stack
val1 = pop(&s);
switch (postfix[i]) {
case '+': result = val1 + val2; break;
case '-': result = val1 - val2; break;
case '*': result = val1 * val2; break;
case '/': result = val1 / val2; break;
case '^': result = pow(val1, val2); break;
}
push(&s, result); // Push result back to stack
}
}
return pop(&s); // Final result
}
int main() {
char infix[MAX], postfix[MAX];
// Input infix expression
printf("Enter infix expression: ");
fgets(infix, MAX, stdin);
// Convert infix to postfix
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
// Evaluate the postfix expression
int result = evaluatePostfix(postfix);
printf("Result of postfix evaluation: %d\n", result);
return 0;
}
Explanation of the Code:
1. Stack Implementation:
• The Stack structure stores the operator stack with a top pointer.
• The functions push(), pop(), and peek() handle stack operations.
2. Infix to Postfix Conversion:
• infixToPostfix() function converts the given infix expression into postfix
notation using a stack to manage operators.
3. Postfix Evaluation:
• evaluatePostfix() evaluates the postfix expression by using a stack to store
operands and applying the operators in sequence.
Example Execution:
Input:
Enter infix expression: A + B * ( C - D )
Output:
Postfix expression: ABCD-*+
Result of postfix evaluation: 14
In this case, if A=2, B=3, C=5, and D=1, the result of A + B * ( C - D ) evaluates to 2 + 3
* (5 - 1) = 14.
