Untitled

 avatar
irfann
plain_text
6 months ago
4.0 kB
7
Indexable
Never
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
// Stack ADT using an array
typedef struct {
 char items[MAX_SIZE];
 int top;
} Stack;
// Stack operations
void initialize(Stack* stack) {
 stack
->top = 
-1;
}
bool isEmpty(Stack* stack) {
 return stack
->top == 
-1;
}
bool isFull(Stack* stack) {
 return stack
->top == MAX_SIZE 
- 1;
}
void push(Stack* stack, char item) {
 if (isFull(stack)) {
 printf("Stack overflow!
\n");
 return;
 
}
 stack
->top++;
 stack
->items[stack
->top] = item;
}
char pop(Stack* stack) {
 if (isEmpty(stack)) {
 printf("Stack underflow!
\n");
 return '
\0';
 
}
 char item = stack
->items[stack
->top];
 stack
->top--
;
 return item; }
char peek(Stack* stack) {
 if (isEmpty(stack)) {
 printf("Stack is empty!
\
n");
 return '
\0';
 
}
 return stack
->items[stack
->top];
}
// Helper function to check if a character is an operator
bool isOperator(char c) {
 return (c == '+' || c == '-' || c == '*' || c == '/');
}
// Helper function to get the precedence of an operator
int precedence(char c) {
 switch (c) {
 case '+':
 case '-':
 return 1;
 case '*':
 case '/':
 return 2;
 default:
 return 0;
 }
}
// Function to perform infix to postfix conversion
void infixToPostfix(char* infix, char* postfix) {
 Stack stack;
 initialize(&stack);
 int postfixIndex = 0;
 int length = strlen(infix);
 for (int i = 0; i < length; i++) {
 char currentChar = infix[i];
 if (isalnum(currentChar)) {
 postfix[postfixIndex++] = currentChar;
 } else if (isOperator(currentChar)) {
 while (!isEmpty(&stack) && precedence(peek(&stack)) >= precedence(currentChar)) {
 postfix[postfixIndex++] = pop(&stack);
 }
 push(&stack, currentChar);
 } else if (currentChar == '(') {
 push(&stack, currentChar);
 } else if (currentChar == ')') {
 while (!isEmpty(&stack) && peek(&stack) != '(') {
 postfix[postfixIndex++] = pop(&stack);
 }
 pop(&stack); // Pop '('
 }
 }
 while (!isEmpty(&stack)) {
 postfix[postfixIndex++] = pop(&stack);
 }
 postfix[postfixIndex] = '\0';
}
// Function to perform infix to prefix conversion
void infixToPrefix(char* infix, char* prefix) {
 // Reverse the infix expression
 int length = strlen(infix);
 char reversedInfix[MAX_SIZE];
 int j = 0;
 for (int i = length - 1; i >= 0; i--) {
 reversedInfix[j++] = infix[i];
 }
 reversedInfix[j] = '\0';
 // Convert reversed infix to postfix
 char postfix[MAX_SIZE];
 infixToPostfix(reversedInfix, postfix);
 // Reverse the postfix expression to get the prefix expression
 length = strlen(postfix);
 j = 0;
 for (int i = length - 1; i >= 0; i--) {
 prefix[j++] = postfix[i];
 }
 prefix[j] = '\0';
}
// Function to evaluate postfix expression
int evaluatePostfix(char* postfix) {
 Stack stack;
 initialize(&stack);
 int length = strlen(postfix);
 for (int i = 0; i < length; i++) {
 char currentChar = postfix[i];
 if (isdigit(currentChar)) {
 push(&stack, currentChar - '0');
 } else if (isOperator(currentChar)) {
 int operand2 = pop(&stack);
 int operand1 = pop(&stack);
 switch (currentChar) {
 case '+':
 push(&stack, operand1 + operand2);
 break;
 case '-':
 push(&stack, operand1 - operand2);
 break;
 case '*':
 push(&stack, operand1 * operand2);
 break;
 case '/':
 push(&stack, operand1 / operand2);
 break;
 default:
 printf("Invalid operator!\n");
 return 0;
 }
 }
 }
 return pop(&stack);
}
int main() {
 char infixExpression[MAX_SIZE], postfixExpression[MAX_SIZE], 
prefixExpression[MAX_SIZE];
 printf("Enter an infix expression: ");
 gets(infixExpression);
 infixToPostfix(infixExpression, postfixExpression);
 printf("Postfix expression: %s\n", postfixExpression);
 infixToPrefix(infixExpression, prefixExpression);
 printf("Prefix expression: %s\n", prefixExpression);
 int result = evaluatePostfix(postfixExpression);
 printf("Postfix expression evaluation result: %d\n", result);
 return 0;
}
Leave a Comment