C Language Stack Implementation and Applications

Posted on Apr 4, 2025 in Computer Engineering

C Code: Checking Parentheses Correctness

#include <stdio.h>
#include <string.h>

#define N 20

typedef struct stack {
    int a[N];
    int top;
} stack;

void push(stack *s, int x) {
    s->top++;
    s->a[s->top] = x;
}

int pop(stack *s) {
    int x;
    x = s->a[s->top];
    s->top--;
    return x;
}

int isOpenBracket(int x) {
    if (x == '{' || x == '[' || x == '(') {
        return 1;
    } else {
        return 0;
    }
}

int isCloseBracket(int x) {
    if (x == '}' || x == ']' || x == ')') {
        return 1;
    } else {
        return 0;
    }
}

int isEmpty(stack *s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

int checkParentheses(char s1[]) {
    int i, x, ele;
    stack s;
    s.top = -1;
    for (i = 0; i < strlen(s1); i++) {
        x = s1[i];
        if (isOpenBracket(x))
            push(&s, x);
        if (isCloseBracket(x)) {
            if (isEmpty(&s))
                return 0;
            else {
                ele = pop(&s);
                if (x == '}' && ele != '{')
                    return 0;
                if (x == ']' && ele != '[')
                    return 0;
                if (x == ')' && ele != '(')
                    return 0;
            }
        }
    }
    if (isEmpty(&s)) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    char s1[20];
    printf("Enter Expression = ");
    gets(s1); // Note: gets() is unsafe, consider using fgets()
    if (checkParentheses(s1)) {
        printf("\nExpression is valid...\n");
    } else {
        printf("\nExpression is invalid...\n");
    }
    return 0;
}

C Code: Stack Implementation with Array

#include <stdio.h>

#define N 20

typedef struct stack {
    int a[N];
    int top;
} stack;

void push(stack *s, int x) {
    if (s->top == N - 1)
        printf("\nStack Overflow...\n");
    else {
        s->top = s->top + 1;
        s->a[s->top] = x;
    }
}

int isEmpty(stack *s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

int pop(stack *s) {
    int x;
    if (isEmpty(s)) {
        return -1; // Indicate underflow
    } else {
        x = s->a[s->top];
        s->top = s->top - 1;
        return x;
    }
}

int peek(stack *s) {
    if (isEmpty(s))
        return -1; // Indicate stack is empty
    else
        return s->a[s->top];
}

void display(stack *s) {
    int i;
    if (isEmpty(s)) {
        printf("\nStack is empty...\n");
    } else {
        printf("Stack elements (top to bottom):\n");
        for (i = s->top; i >= 0; i--) {
            printf("\t%d\n", s->a[i]);
        }
    }
}

int main() {
    int ch, x;
    stack s;
    s.top = -1;
    while (1) {
        printf("\n--- Stack Menu ---\n");
        printf("1: Push\n");
        printf("2: Pop\n");
        printf("3: Peek\n");
        printf("4: Display\n");
        printf("5: Exit\n");
        printf("Enter choice = ");
        scanf("%d", &ch);

        if (ch == 5)
            break;

        switch (ch) {
            case 1:
                printf("\nEnter element to be pushed = ");
                scanf("%d", &x);
                push(&s, x);
                break;
            case 2:
                x = pop(&s);
                if (x == -1)
                    printf("\nStack Underflow...\n");
                else
                    printf("\nPopped Element = %d\n", x);
                break;
            case 3:
                x = peek(&s);
                if (x == -1)
                    printf("\nStack is empty...\n");
                else
                    printf("\nStack top element = %d\n", x);
                break;
            case 4:
                display(&s);
                break;
            default:
                printf("\nInvalid Choice...\n");
        }
    }
    return 0;
}

C Code: Infix to Postfix Conversion

#include <stdio.h>
#include <string.h>
#include <ctype.h> // For isalpha()

#define N 20

typedef struct stack {
    char a[N];
    int top;
} stack;

void push(stack *s, char x) {
    s->top++;
    s->a[s->top] = x;
}

char pop(stack *s) {
    char x;
    x = s->a[s->top];
    s->top--;
    return x;
}

int isEmpty(stack *s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

char stackTop(stack *s) {
    if (isEmpty(s))
        return '\0'; // Return null character if stack is empty
    return s->a[s->top];
}

int isOperand(char x) {
    // Using ctype.h for better check
    return isalpha(x);
}

int isOperator(char x) {
    if (x == '+' || x == '-' || x == '*' || x == '/')
        return 1;
    else
        return 0;
}

int priority(char x) {
    if (x == '*' || x == '/')
        return 3;
    else if (x == '+' || x == '-')
        return 2;
    else // For '(' or other characters
        return 1;
}

void convert(char infix[], char postfix[]) {
    stack s;
    s.top = -1;
    int i, k = 0;
    char x, ele;
    push(&s, '('); // Push '(' onto stack initially
    strcat(infix, ")"); // Append ')' to infix expression

    for (i = 0; i < strlen(infix); i++) {
        x = infix[i];
        if (isOperand(x))
            postfix[k++] = x;
        else if (x == '(')
            push(&s, x);
        else if (isOperator(x)) {
            while (!isEmpty(&s) && isOperator(stackTop(&s)) && priority(x) <= priority(stackTop(&s))) {
                ele = pop(&s);
                postfix[k++] = ele;
            }
            push(&s, x);
        } else if (x == ')') { // Closing parenthesis
            while (!isEmpty(&s) && stackTop(&s) != '(') {
                ele = pop(&s);
                postfix[k++] = ele;
            }
            if (!isEmpty(&s)) {
                ele = pop(&s); // Pop the '(' 
            }
        }
    }
    // No need for the final while loop because we handled '(' and ')'
    postfix[k] = '\0';
}

int main() {
    char infix[20], postfix[20];
    printf("Enter infix expression = ");
    gets(infix); // Note: gets() is unsafe, consider using fgets()
    convert(infix, postfix);
    printf("\nPostfix Expression = %s\n", postfix);
    return 0;
}

C Code: Evaluating Postfix Expressions

#include <stdio.h>
#include <string.h>
#include <ctype.h> // For isdigit()

#define N 15

typedef struct stack {
    int a[N];
    int top;
} stack;

void push(stack *s, int x) {
    s->top++;
    s->a[s->top] = x;
}

int pop(stack *s) {
    int x;
    x = s->a[s->top];
    s->top--;
    return x;
}

int isOperand(char x) {
    // Using ctype.h for better check
    return isdigit(x);
}

int evaluate(char postfix[]) {
    stack s;
    s.top = -1;
    int op1, op2, x_val, v, i;
    char x;

    for (i = 0; i < strlen(postfix); i++) {
        x = postfix[i];
        if (isOperand(x)) {
            push(&s, (int)x - '0'); // Convert char digit to int
        } else { // When x is an operator
            op1 = pop(&s);
            op2 = pop(&s);
            switch (x) {
                case '+':
                    v = op2 + op1;
                    break;
                case '-':
                    v = op2 - op1;
                    break;
                case '*':
                    v = op2 * op1;
                    break;
                case '/':
                    // Add check for division by zero if necessary
                    v = op2 / op1;
                    break;
            }
            push(&s, v);
        }
    }
    return pop(&s); // The final result is on the stack
}

int main() {
    char postfix[20]; // Increased size slightly
    int z;
    printf("Enter postfix expression = ");
    gets(postfix); // Note: gets() is unsafe, consider using fgets()
    z = evaluate(postfix);
    printf("\nResult = %d\n", z);
    return 0;
}