C Infix to Postfix Conversion and Evaluation
This C program demonstrates the conversion of an infix mathematical expression to its postfix equivalent and subsequently evaluates the postfix expression. It utilizes stack data structures for efficient processing of operators and operands, providing a clear example of algorithm implementation in C.
Standard Library Includes
The necessary header files for input/output, memory allocation, string manipulation, character type checking, and mathematical operations.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>Global Constants and Data Structures
Maximum Array Size Definition
Defines the maximum capacity for stacks and expression arrays.
#define max 100Character Stack for Infix to Postfix Conversion
A stack structure designed to hold character tokens (operators, parentheses), primarily used during the infix to postfix conversion process.
// stack for characters (used in infix to postfix)
typedef struct {
char data[max][max];
int top;
} stackchar;Integer Stack for Postfix Evaluation
A stack structure for integer values, essential for evaluating the postfix expression by storing operands and intermediate results.
// stack for integers (used in postfix evaluation)
typedef struct {
int data[max];
int top;
} stackint;Function Prototypes
Declarations for all functions used in the program, outlining their return types and parameters.
int precedence(char op);: Determines the precedence level of an arithmetic operator.int isoperator(char *token);: Checks if a given string token represents an operator.void infixtopostfix(char *infix, char postfix[][max], int *postfixlength);: Converts an infix expression string to a postfix array.int evaluatepostfix(char postfix[][max], int length);: Evaluates a postfix expression array to compute its result.
Character Stack (stackchar) Implementations
Functions to manage the character stack, crucial for handling operators and parentheses during expression conversion.
Push Character String to Stack
void pushchar(stackchar *s, char *str) {
strcpy(s->data[++(s->top)], str);
}Pop Character String from Stack
char* popchar(stackchar *s) {
return s->data[(s->top)--];
}Peek at Top Character String on Stack
char* peekchar(stackchar *s) {
return s->data[s->top];
}Check if Character Stack is Empty
int isemptychar(stackchar *s) {
return s->top == -1;
}Integer Stack (stackint) Implementations
Functions for managing the integer stack, used for operand storage and calculation during postfix evaluation.
Push Integer Value to Stack
void pushint(stackint *s, int val) {
s->data[++(s->top)] = val;
}Pop Integer Value from Stack
int popint(stackint *s) {
return s->data[(s->top)--];
}Expression Logic Functions
Operator Precedence Determination
Assigns a numerical precedence level to arithmetic operators. Higher values indicate higher precedence.
int precedence(char op) {
switch(op) {
case '^': return 3;
case '*': case '/': return 2;
case '+': case '-': return 1;
default: return 0;
}
}Operator Identification
Checks if a given token (a string) is one of the supported arithmetic operators (+, -, *, /, ^).
int isoperator(char *token) {
return strlen(token) == 1 && strchr("+-*/^", token[0]) != NULL;
}Infix to Postfix Conversion Algorithm
This function takes an infix expression, tokenizes it, and converts it into a postfix expression using principles similar to the Shunting-yard algorithm with a character stack.
void infixtopostfix(char *infix, char postfix[][max], int *postfixlength) {
stackchar stack;
stack.top = -1;
char *token = strtok(infix, " ");
*postfixlength = 0;
while (token != NULL) {
if (isdigit(token[0])) {
strcpy(postfix[(*postfixlength)++], token); // operand
} else if (strcmp(token, "(") == 0) {
pushchar(&stack, token);
} else if (strcmp(token, ")") == 0) {
while (!isemptychar(&stack) && strcmp(peekchar(&stack), "(") != 0) {
strcpy(postfix[(*postfixlength)++], popchar(&stack));
}
popchar(&stack); // remove '('
} else if (isoperator(token)) {
while (!isemptychar(&stack) && isoperator(peekchar(&stack)) &&
((precedence(token[0]) < precedence(peekchar(&stack)[0])) ||
(precedence(token[0]) == precedence(peekchar(&stack)[0]) && token[0] != '^'))) {
strcpy(postfix[(*postfixlength)++], popchar(&stack));
}
pushchar(&stack, token);
}
token = strtok(NULL, " ");
}
while (!isemptychar(&stack)) {
strcpy(postfix[(*postfixlength)++], popchar(&stack));
}
}Postfix Expression Evaluation Algorithm
Evaluates the postfix expression using an integer stack. Operands are pushed onto the stack, and operators trigger calculations with the top two stack elements.
int evaluatepostfix(char postfix[][max], int length) {
stackint stack;
stack.top = -1;
for (int i = 0; i < length; i++) {
if (isdigit(postfix[i][0])) {
pushint(&stack, atoi(postfix[i]));
} else {
int b = popint(&stack);
int a = popint(&stack);
switch(postfix[i][0]) {
case '+': pushint(&stack, a + b); break;
case '-': pushint(&stack, a - b); break;
case '*': pushint(&stack, a * b); break;
case '/': pushint(&stack, a / b); break;
case '^': pushint(&stack, (int)pow(a, b)); break;
}
}
}
return popint(&stack);
}Main Program Function
The entry point of the program, handling user input for an infix expression, performing the conversion, and displaying both the postfix form and its evaluated numerical result.
int main() {
char infix[max];
char postfix[max][max];
int postfixlength;
printf("Enter infix expression (use space between every token):\n");
fgets(infix, max, stdin);
infix[strcspn(infix, "\n")] = '\0'; // remove newline
infixtopostfix(infix, postfix, &postfixlength);
printf("\nPostfix expression:\n");
for (int i = 0; i < postfixlength; i++) {
printf("%s ", postfix[i]);
}
int result = evaluatepostfix(postfix, postfixlength);
printf("\n\nResult after evaluation: %d\n", result);
return 0;
}