#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100 // Maximum stack size
// Structure for the stack
struct Stack {
char items[MAX_SIZE]; // For infix-to-postfix (operators)
int top;
};
// Function to initialize the stack
void initStack(struct Stack* stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// Function to push an item onto the stack
void push(struct Stack* stack, char item) {
if (isFull(stack)) {
printf("Stack overflow!\n");
exit(1);
}
stack->items[++stack->top] = item;
}
// Function to pop an item from the stack
char pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n");
exit(1);
}
return stack->items[stack->top--];
}
// Function to peek at the top item of the stack
char peek(struct Stack* stack) {
if (isEmpty(stack)) {
return '\0';
}
return stack->items[stack->top];
}
// Function to check if a character is an operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
// Function to get the precedence of an operator
int precedence(char op) {
if (op == '+' || op == '-') {
return 1;
}
if (op == '*' || op == '/') {
return 2;
}
return 0; // For parentheses or non-operators
}
// Function to convert infix expression to postfix
void infixToPostfix(const char* infix, char* postfix) {
struct Stack stack;
initStack(&stack);
int j = 0; // Index for postfix string
for (int i = 0; infix[i] != '\0'; i++) {
char c = infix[i];
// Skip spaces
if (isspace(c)) {
continue;
}
// If operand (letter or digit), add to postfix
if (isalnum(c)) {
postfix[j++] = c;
}
// If opening parenthesis, push to stack
else if (c == '(') {
push(&stack, c);
}
// If closing parenthesis, pop until opening parenthesis
else if (c == ')') {
while (!isEmpty(&stack) && peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
if (!isEmpty(&stack) && peek(&stack) == '(') {
pop(&stack); // Remove '('
}
}
// If operator
else if (isOperator(c)) {
while (!isEmpty(&stack) && precedence(peek(&stack)) >= precedence(c)) {
postfix[j++] = pop(&stack);
}
push(&stack, c);
}
}
// Pop remaining operators from stack
while (!isEmpty(&stack)) {
char op = pop(&stack);
if (op != '(') {
postfix[j++] = op;
}
}
postfix[j] = '\0'; // Null-terminate the postfix string
}
// Structure for integer stack (for evaluation)
struct IntStack {
int items[MAX_SIZE];
int top;
};
// Integer stack operations
void initIntStack(struct IntStack* stack) {
stack->top = -1;
}
int isIntEmpty(struct IntStack* stack) {
return stack->top == -1;
}
int isIntFull(struct IntStack* stack) {
return stack->top == MAX_SIZE - 1;
}
void pushInt(struct IntStack* stack, int item) {
if (isIntFull(stack)) {
printf("Stack overflow!\n");
exit(1);
}
stack->items[++stack->top] = item;
}
int popInt(struct IntStack* stack) {
if (isIntEmpty(stack)) {
printf("Stack underflow!\n");
exit(1);
}
return stack->items[stack->top--];
}
// Function to evaluate a postfix expression
int evaluatePostfix(const char* postfix, int values[]) {
struct IntStack stack;
initIntStack(&stack);
for (int i = 0; postfix[i] != '\0'; i++) {
char c = postfix[i];
// Skip spaces
if (isspace(c)) {
continue;
}
// If operand (digit), push its value
if (isdigit(c)) {
pushInt(&stack, values[c - '0']);
}
// If operator, pop two operands, compute, and push result
else if (isOperator(c)) {
int b = popInt(&stack); // Second operand
int a = popInt(&stack); // First operand
int result;
switch (c) {
case '+': result = a + b; break;
case '-': result = a - b; break;
case '*': result = a * b; break;
case '/':
if (b == 0) {
printf("Division by zero!\n");
exit(1);
}
result = a / b;
break;
}
pushInt(&stack, result);
}
}
return popInt(&stack); // Final result
}
// Main function to test infix-to-postfix conversion and evaluation
int main() {
char infix[MAX_SIZE];
char postfix[MAX_SIZE];
int values[10]; // Store values for digits 0-9
// Get infix expression
printf("Enter an infix expression (e.g., (2 + 3) * 4): ");
fgets(infix, MAX_SIZE, stdin);
infix[strcspn(infix, "\n")] = '\0'; // Remove newline
// Convert to postfix
infixToPostfix(infix, postfix);
printf("Postfix expression: %s\n", postfix);
// Get values for operands (assuming digits 0-9)
printf("Enter values for operands (digits 0-9):\n");
for (int i = 0; i < 10; i++) {
printf("Value for %d: ", i);
scanf("%d", &values[i]);
}
// Evaluate postfix expression
int result = evaluatePostfix(postfix, values);
printf("Evaluation result: %d\n", result);
return 0;
}
Output:
Comments
Post a Comment