Expression Evaluation Using a Stack in C Programming
In computer science, stacks are fundamental data structures used for solving computational problems. One of their elegant applications is evaluating mathematical expressions. C programming, known for its efficiency and control, provides a great environment to implement stack-based algorithms. Let's delve into how to evaluate infix, postfix, and prefix expressions using stacks in C.
Why a Stack for Expression Evaluation?
Stacks follow the LIFO (Last-In, First-Out) principle, making them ideal for handling expressions with operator precedence and nested parentheses. Think of a stack of plates: the last plate you put in is the first one you take out. Operators and operands follow a similar paradigm in expressions.
Types of Expressions
Infix Notation: Operators sit between operands (e.g., A + B * C)
Postfix Notation: Operators follow their operands (e.g., AB C *)
Prefix Notation: Operators precede their operands (e.g., + A * B C)
We'll focus on postfix expression evaluation as it's the easiest to implement with a stack.
Postfix Expression Evaluation: Step-by-Step Guide
Create a Stack: Initialize a stack that can store integer values.
Scan the Expression: Traverse the postfix expression character by character.
Operands: If the scanned character is an operand (a digit), push it onto the stack.
Operators:
If the character is an operator, pop the top two operands from the stack.
Perform the operation on these operands.
Push the result back onto the stack.
Result: After processing the entire expression, the final value remaining on the stack is the result.
C Code to evaluate Postfix expression
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX_SIZE 100
// Structure for a stack
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
// Initialize the stack
void initStack(Stack *s) {
s->top = -1;
}
// Check if the stack is empty
int isEmpty(Stack *s) {
return s->top == -1;
}
// Check if the stack is full
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// Push an element onto the stack
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack Overflow\n");
return;
}
s->data[++s->top] = value;
}
// Pop an element from the stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow\n");
exit(EXIT_FAILURE);
}
return s->data[s->top--];
}
// Evaluate a postfix expression
int evaluatePostfix(char *expression) {
Stack s;
initStack(&s);
for (int i = 0; expression[i]; ++i) {
if (isdigit(expression[i])) {
push(&s, expression[i] - '0'); // Convert digit character to number
} else {
int val1 = pop(&s);
int val2 = pop(&s);
switch (expression[i]) {
case '+': push(&s, val2 + val1); break;
case '-': push(&s, val2 - val1); break;
case '*': push(&s, val2 * val1); break;
case '/': push(&s, val2 / val1); break;
}
}
}
return pop(&s);
}
int main() {
char expression[] = "235*+8-";
int result = evaluatePostfix(expression);
printf("Result = %d\n", result);
return 0;
}
Let's evaluate the postfix expression "2 3 5 * + 8 -" using a stack:
Steps:
Initialization: Create an empty stack.
Process '2':
Since '2' is an operand, push it onto the stack.
Stack: [2]
Process '3':
'3' is an operand, push it onto the stack.
Stack: [2, 3]
Process '5':
'5' is an operand, push it onto the stack.
Stack: [2, 3, 5]
Process '*':
'*' is an operator. Pop the top two operands (3 and 5).
Perform the multiplication: 3 * 5 = 15
Push the result (15) back onto the stack.
Stack: [2, 15]
Process '+':
'+' is an operator. Pop the top two operands (2 and 15).
Perform the addition: 2 + 15 = 17
Push the result (17) back onto the stack.
Stack: [17]
Process '8':
'8' is an operand, push it onto the stack.
Stack: [17, 8]
Process '-':
'-' is an operator. Pop the top two operands (17 and 8).
Perform the subtraction: 17 - 8 = 9
Push the result (9) back onto the stack.
Stack: [9]
Final Result: After processing the entire expression, the value remaining on the stack (9) is the final result of the evaluation.
Comments