Problem Overview:
Infix Expression: The expression where operators are placed between operands. For example: A + B.
Postfix Expression (also called Reverse Polish Notation): The operators are placed after their operands. For example: A B +.
Steps to Convert Infix to Postfix:
- Use a stack to store operators until they are needed.
- Operands (like A, B, etc.) are directly added to the postfix output.
- Operators are pushed to the stack but can only be popped when they follow the precedence and associativity rules.
- Parentheses: Opening parentheses
(are pushed to the stack, and when a closing parenthesis)is encountered, the stack is popped to the output until the corresponding(is found.
Precedence Rules:
+and-have the same precedence (low).*,/, and%have the same precedence (higher than+and-).^(exponentiation) has the highest precedence.- Associativity of
^is right-to-left, while the others are left-to-right.
Now, let’s write a C program based on this logic.
#include <stdio.h>
#include <ctype.h> // for isdigit() function
#include <stdlib.h> // for exit() function
#define MAX 100 // maximum size of the stack
// Stack structure
char stack[MAX];
int top = -1; // initialize stack top pointer
// Function to push elements onto the stack
void push(char c)
{
if (top == (MAX - 1))
{
printf("Stack Overflow\n");
exit(1); // terminate the program
}
stack[++top] = c;
}
// Function to pop elements from the stack
char pop() {
if (top == -1)
{
printf("Stack Underflow\n");
exit(1);
}
return stack[top--];
}
// Function to check precedence of operators
int precedence(char symbol)
{
switch (symbol)
{
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default:
return 0;
}
}
// Function to determine if it's an operator
int isOperator(char symbol)
{
return (symbol == '+' || symbol == '-' || symbol == '*' || symbol == '/' || symbol == '^' || symbol == '%');
}
// Function to convert infix to postfix
void infixToPostfix(char infix[])
{
char postfix[MAX]; // result string for postfix
int i = 0, j = 0; // i for infix, j for postfix
while (infix[i] != '\0')
{
char current = infix[i];
// If the current character is an operand, add it to postfix
if (isalnum(current))
{
postfix[j++] = current;
}
// If the current character is '(', push it to the stack
else if (current == '(')
{
push(current);
}
// If the current character is ')', pop until '(' is found
else if (current == ')')
{
while (top != -1 && stack[top] != '(')
{
postfix[j++] = pop();
}
pop(); // remove '(' from the stack
}
// If the current character is an operator
else if (isOperator(current))
{
while (top != -1 && precedence(stack[top]) >= precedence(current))
{
postfix[j++] = pop();
}
push(current); // push current operator to stack
}
i++;
}
// Pop all remaining operators from the stack
while (top != -1)
{
postfix[j++] = pop();
}
postfix[j] = '\0'; // null-terminate the postfix string
printf("Postfix Expression: %s\n", postfix);
}
// Main function to drive the program
int main()
{
char infix[MAX];
printf("Enter an Infix Expression: ");
scanf("%s", infix);
infixToPostfix(infix); // Call the conversion function
return 0;
}
Explanation of the Code:
- Stack Operations:
push()adds an operator or parenthesis to the stack.pop()removes and returns the top element from the stack.
- Operator Precedence:
- The
precedence()function assigns priority to operators (^has the highest, then* / %, and finally+ -).
- The
- Main Conversion Logic:
- Loop through each character in the infix expression:
- If the character is an operand (letter or digit), it’s directly added to the output (postfix).
- If it’s an opening parenthesis
(, it’s pushed to the stack. - If it’s a closing parenthesis
), we pop from the stack to the output until an opening parenthesis is encountered. - If it’s an operator, we pop operators from the stack to the output while their precedence is higher than or equal to the current operator.
- After the loop ends, any remaining operators in the stack are popped and added to the output.
- Loop through each character in the infix expression:
Sample Output
Enter an Infix Expression: A+B*C
Postfix Expression: ABC*+
Key Notes:
- Parentheses help override operator precedence. For example, in
(A+B)*C, the addition is done before multiplication. - Without parentheses, the normal precedence of operators will apply.
This program demonstrates how to correctly convert an infix expression to a postfix expression using stack operations in C language.
