Data Structures 07 - Bracket Matching

Code

#include <stdbool.h>
#include <stdio.h>
#include <malloc.h>

#define STACK_MAX_SIZE 10 // Define the maximum stack size

/**
 * Represents an integer linear stack. The key is data.
 */
typedef struct CharStack {
    int top; // Stack top pointer

    char data[STACK_MAX_SIZE]; // Data array, fixed maximum length
} *CharStackPtr;

/**
 * Output the contents of the stack.
 */
void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }// End of loop
    printf("\r\n");
}// End of outputStack

/**
 * Initialize an empty character stack. This function has no error checking.
 * @param paraStackPtr Pointer to the stack. Must be a pointer to modify the stack.
 * @param paraValues Int array storing all elements.
 */
CharStackPtr charStackInit() {
    CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(struct CharStack));
    resultPtr->top = -1; // Initialize stack top to -1, indicating an empty stack

    return resultPtr;
}// End of charStackInit

/**
 * Push an element onto the stack.
 * @param paraValue The value to push.
 */
void push(CharStackPtr paraStackPtr, int paraValue) {
    // Step 1. Check space.
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("Cannot push element: stack full.\r\n");
        return;
    }// End of if

    // Step 2. Update stack top.
    paraStackPtr->top ++;

    // Step 3. Push element.
    paraStackPtr->data[paraStackPtr->top] = paraValue;
}// End of push

/**
 * Pop an element from the stack.
 * @return The popped value.
 */
char pop(CharStackPtr paraStackPtr) {
    // Step 1. Check space.
    if (paraStackPtr->top < 0) {
        printf("Cannot pop element: stack empty.\r\n");
        return '\0';
    }// End of if

    // Step 2. Update stack top.
    paraStackPtr->top --;

    // Step 3. Pop element.
    return paraStackPtr->data[paraStackPtr->top + 1];
}// End of pop

/**
 * Test the push function.
 */
void pushPopTest() {
    printf("---- pushPopTest begins. ----\r\n");
    char ch;
    
    // Initialization.
    CharStackPtr tempStack = charStackInit();
    printf("After initialization, the stack is: ");
    outputStack(tempStack);

    // Push.
    for (ch = 'a'; ch < 'm'; ch ++) {
        printf("Pushing %c.\r\n", ch);
        push(tempStack, ch);
        outputStack(tempStack);
    }// End of for

    // Pop.
    for (int i = 0; i < 3; i ++) {
        ch = pop(tempStack);
        printf("Pop %c.\r\n", ch);
        outputStack(tempStack);
    }// End of for

    printf("---- pushPopTest ends. ----\r\n");
}// End of pushPopTest

/**
 * Determine if brackets match.
 * 
 * @param paraString The given expression string.
 * @return Whether they match.
 */
bool bracketMatching(char* paraString, int paraLength) {
    // Step 1. Initialize stack, push a '#' at the bottom.
    CharStackPtr tempStack = charStackInit();
    push(tempStack, '#');
    char tempChar, tempPopedChar;

    // Step 2. Process the string.
    for (int i = 0; i < paraLength; i++) {
        tempChar = paraString[i];

        switch (tempChar) {
        case '(':
        case '[':
        case '{':
            push(tempStack, tempChar);
            break;
        case ')':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '(') {
                return false;
            } // End of if
            break;
        case ']':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '[') {
                return false;
            } // End of if
            break;
        case '}':
            tempPopedChar = pop(tempStack);
            if (tempPopedChar != '{') {
                return false;
            } // End of if
            break;
        default:
            // Do nothing.
            break;
        }// End of switch
    } // End of for

    tempPopedChar = pop(tempStack);
    if (tempPopedChar != '#') {
        return false;
    } // End of if

    return true;
}// End of bracketMatching

/**
 * Unit test.
 */
void bracketMatchingTest() {
    char* tempExpression = "[2 + (1 - 3)] * 4";
    bool tempMatch = bracketMatching(tempExpression, 17);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "( )  )";
    tempMatch = bracketMatching(tempExpression, 6);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "()()(())";
    tempMatch = bracketMatching(tempExpression, 8);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = "({}[])";
    tempMatch = bracketMatching(tempExpression, 6);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);

    tempExpression = ")(";
    tempMatch = bracketMatching(tempExpression, 2);
    printf("Is the expression '%s' bracket matching? %d \r\n", tempExpression, tempMatch);
}// End of bracketMatchingTest

/**
 * Program entry.
 */
void main() {
    // pushPopTest(); // Test push and pop functionality
    bracketMatchingTest(); // Test bracket matching functionality
}// End of main

Summary: This code implements a fixed-size character stack (maximum 10 elements), including basic operations such as initialization, push, and pop. It also includes a helper function for outputting stack contents and two test functions: pushPopTest for testing push and pop operations, and bracketMatchingTest for testing the bracket matching problem, checking whether brackets in a given string are correctly matched. The main function calls the bracket matching test function. Each function in the code has detailed comments explaining its functionality and how it works.

Running Result