C Program to convert an infix expression to postfix
ALGORITHM :
Step 1: Start
Step 2: Define a constant MAX_SIZE to represent the maximum size of the stack.
Step 3: Declare a stack structure with necessary variables (e.g., top to keep track of the top element, and an array to store operators).
Step 4: Declare a function precedence(char operator) to return the precedence value of an operator (higher value means higher precedence).
Step 5: Input the infix expression as a string.
Step 6: Initialize an empty string (postfix) to store the postfix expression.
Step 7: Repeat the following steps for each character in the infix expression:
a. If the character is an operand, append it to the postfix string.
b. If the character is an open parenthesis '(', push it to the stack.
c. If the character is a close parenthesis ')', pop operators from the stack and append them to the postfix string until an open parenthesis is encountered. Pop and discard the open parenthesis.
d. If the character is an operator, pop operators from the stack and append them to the postfix string while their precedence is greater than or equal to the precedence of the current operator. Then, push the current operator to the stack.
Step 8: After processing all characters, pop any remaining operators from the stack and append them to the postfix string.
Step 9: Display the postfix expression.
Step 10: End
SOURCE CODE :
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
char stack[MAX_SIZE];
int top = -1;
int isEmpty() {
return (top == -1);
}
int isFull() {
return (top == MAX_SIZE - 1);
}
void push(char item) {
if (isFull()) {
printf("Stack Overflow: Cannot push %c, stack is full.\n", item);
} else {
stack[++top] = item;
}
}
char pop() {
if (isEmpty()) {
printf("Stack Underflow: Cannot pop, stack is empty.\n");
return '\0';
} else {
return stack[top--];
}
}
char peek() {
if (isEmpty()) {
return '\0';
} else {
return stack[top];
}
}
int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}
int precedence(char ch) {
if (ch == '+' || ch == '-')
return 1;
else if (ch == '*' || ch == '/')
return 2;
return 0;
}
void infixToPostfix(char infix[], char postfix[]) {
int i, j;
i = j = 0;
while (infix[i] != '\0') {
if (isdigit(infix[i]) || isalpha(infix[i])) {
postfix[j++] = infix[i++];
} else if (infix[i] == '(') {
push(infix[i++]);
} else if (infix[i] == ')') {
while (peek() != '(') {
postfix[j++] = pop();
}
pop(); // Pop the '('
i++;
} else if (isOperator(infix[i])) {
while (!isEmpty() && precedence(infix[i]) <= precedence(peek())) {
postfix[j++] = pop();
}
push(infix[i++]);
} else {
// Ignore other characters like spaces
i++;
}
}
while (!isEmpty()) {
postfix[j++] = pop();
}
postfix[j] = '\0';
}
int main() {
char infix[MAX_SIZE], postfix[MAX_SIZE];
printf("Enter an infix expression: ");
fgets(infix, sizeof(infix), stdin);
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
return 0;
}
OUTPUT :
Enter an infix expression: (a+b)*c-d/e
Postfix expression: ab+c*de/-
No comments:
Post a Comment