Stack Applications: Balanced Parentheses

Welcome to the next lesson in our exploration of linear data structures. In our previous session, you built a fully functional stack in C, complete with dynamic resizing. You now have a solid understanding of how a stack is implemented and its core Last-In, First-Out (LIFO) operations like push, pop, and peek.

Today, we'll put that powerful tool to work. Our goal is to solve a problem using a stack, specifically validating balanced parentheses in a string. This is a classic computer science problem with direct applications in the real world, such as parsing code in a compiler or evaluating mathematical expressions. You'll see firsthand how the LIFO principle is the key to an elegant and efficient solution.

1. Understanding the "Balanced Parentheses" Problem

First, what does it mean for parentheses to be "balanced"? It's more than just having an equal number of opening and closing brackets. The order and nesting also matter. An expression like ([)] is unbalanced, even though it has one of each type of bracket.

The following video provides an excellent introduction to the problem, defining what makes an expression balanced and explaining why a simple counting approach is insufficient.

The core rules for a valid string of parentheses are:

1. Same Type Matching: Every opening bracket must be closed by a bracket of the same type. ( must be closed by ).
2. Correct Order: Brackets must be closed in the correct order. The most recently opened bracket must be the first one to be closed.
3. Complete Pairing: Every closing bracket must have a corresponding opening bracket.

2. The LIFO Insight: Developing the Algorithm

The rule "the most recently opened bracket must be the first one to be closed" should sound familiar. This is a perfect description of Last-In, First-Out (LIFO) behavior, which is precisely what a stack provides.

Let's develop the algorithm based on this insight:

• We can scan the expression string from left to right.
• When we encounter an opening bracket ((, [, or {), we need to "remember" it because it needs a matching closer later. A great way to remember it is to push it onto a stack.
• When we see a closing bracket (), ], or }), we must check if it matches the most recently opened bracket. Where is that bracket? It's at the top of our stack!
  • So, we pop from the stack and check if the popped bracket is the correct opening partner for the current closing bracket.
  • If they match, we continue.
  • If they don't match, or if the stack was empty when we tried to pop, we have found an error, and the string is unbalanced.

After scanning the entire string, if the stack is empty, it means every opening bracket found its match. If the stack is not empty, it means there are unclosed opening brackets.

The next part of the mycodeschool video walks through this exact logic.

Let's formalize the algorithm:

1. Initialize an empty stack.
2. Iterate through each character of the input string from left to right.
3. If the character is an opening bracket ((, [, {), push it onto the stack.
4. If the character is a closing bracket (), ], }):
   a. Check if the stack is empty. If it is, there's no matching opener, so return unbalanced.
   b. Pop the top element from the stack.
   c. Check if the popped element is the corresponding opening bracket for the current closing bracket. If not, the types are mismatched, so return unbalanced.
5. After the loop finishes, check if the stack is empty.
   a. If it is empty, all brackets were matched correctly. Return balanced.
   b. If it is not empty, there are unclosed opening brackets. Return unbalanced.

This process is visualized clearly in the diagram below.

3. Your Turn: C Implementation

Now, let's implement this in C. You will adapt the dynamic stack you built in the previous lesson. Since we need to store characters like (, ), etc., you'll need to modify your stack to hold char data instead of int.

Step 1: Adapt Your Stack for char

Take your code from the last lesson and make the following changes:

• In the Stack struct definition, change int* collection; to char* collection;.
• In createStack, change the malloc for the collection to (char*)malloc(...).
• In push, the parameter should be char item, and the realloc call should be adjusted for sizeof(char).
• The pop and peek functions should return a char.

Step 2: Implement the isBalanced Function

Below is a C program structure. Copy your modified stack implementation into it, and then complete the logic for the isBalanced function based on the algorithm we just defined.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h> // For strlen

/*
 * ==========================================================
 * YOUR MODIFIED STACK IMPLEMENTATION (for char type) GOES HERE
 * ==========================================================
 * - Stack struct
 * - createStack
 * - destroyStack
 * - isEmpty
 * - push
 * - pop
 * - peek
 */

// Placeholder for your Stack struct
typedef struct {
    char* collection;
    int capacity;
    int size;
} Stack;

// Prototypes for your stack functions
Stack* createStack(int initialCapacity);
void destroyStack(Stack* s);
bool isEmpty(Stack* s);
void push(Stack* s, char item);
char pop(Stack* s);

/*
 * ==========================================================
 * THE BALANCED PARENTHESES LOGIC
 * ==========================================================
 */

// Helper function to check if two characters are a matching pair
bool isMatchingPair(char open, char close) {
    if (open == '(' && close == ')') return true;
    if (open == '[' && close == ']') return true;
    if (open == '{' && close == '}') return true;
    return false;
}

// Function to check if an expression is balanced
bool isBalanced(char* exp) {
    int len = strlen(exp);
    Stack* s = createStack(len); // A stack of size 'len' is worst-case scenario

    // Iterate through the expression string
    for (int i = 0; i < len; i++) {
        // If it's an opening bracket, push it.
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            // YOUR CODE HERE: push the character onto the stack
        }
        // If it's a closing bracket...
        else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            // YOUR CODE HERE:
            // 1. Check if the stack is empty. If so, it's unbalanced.
            // 2. Pop the top character.
            // 3. Check if the popped char and current char form a matching pair using isMatchingPair().
            //    If not, it's unbalanced.
        }
    }

    // After the loop, the expression is balanced ONLY if the stack is empty.
    // YOUR CODE HERE:
    // 1. Check if the stack is empty. Store this result in a boolean variable.
    // 2. Destroy the stack to free memory.
    // 3. Return the boolean result.
    
    // This is just a placeholder return
    return false; 
}


int main() {
    char exp1[] = "{[()]}";
    char exp2[] = "{[(])}";
    char exp3[] = "{{{";
    char exp4[] = "())";
    char exp5[] = "a+b"; // No parentheses
    char exp6[] = "";    // Empty string

    printf("Expression '%s' is %s\n", exp1, isBalanced(exp1) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp2, isBalanced(exp2) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp3, isBalanced(exp3) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp4, isBalanced(exp4) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp5, isBalanced(exp5) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp6, isBalanced(exp6) ? "balanced" : "not balanced");

    return 0;
}

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

/*
 * ==========================================================
 * MODIFIED STACK IMPLEMENTATION (for char type)
 * ==========================================================
 */
typedef struct {
    char* collection;
    int capacity;
    int size;
} Stack;

Stack* createStack(int initialCapacity) {
    if (initialCapacity <= 0) initialCapacity = 1; // Handle 0-length strings
    Stack* s = (Stack*)malloc(sizeof(Stack));
    if (s == NULL) return NULL;
    s->collection = (char*)malloc(initialCapacity * sizeof(char));
    if (s->collection == NULL) {
        free(s);
        return NULL;
    }
    s->capacity = initialCapacity;
    s->size = 0;
    return s;
}

void destroyStack(Stack* s) {
    if (s != NULL) {
        free(s->collection);
        free(s);
    }
}

bool isEmpty(Stack* s) {
    return s->size == 0;
}

void push(Stack* s, char item) {
    if (s->size == s->capacity) {
        int newCapacity = s->capacity * 2;
        char* newCollection = (char*)realloc(s->collection, newCapacity * sizeof(char));
        if (newCollection == NULL) {
            // In a real app, handle this error more gracefully
            printf("Error: Stack resize failed.\n");
            return;
        }
        s->collection = newCollection;
        s->capacity = newCapacity;
    }
    s->collection[s->size] = item;
    s->size++;
}

char pop(Stack* s) {
    if (isEmpty(s)) {
        return '\0'; // Sentinel for underflow
    }
    s->size--;
    return s->collection[s->size];
}

/*
 * ==========================================================
 * THE BALANCED PARENTHESES LOGIC
 * ==========================================================
 */

bool isMatchingPair(char open, char close) {
    if (open == '(' && close == ')') return true;
    if (open == '[' && close == ']') return true;
    if (open == '{' && close == '}') return true;
    return false;
}

bool isBalanced(char* exp) {
    int len = strlen(exp);
    // Handle empty string as a balanced case
    if (len == 0) {
        return true;
    }
    Stack* s = createStack(len);
    if (s == NULL) {
        printf("Failed to create stack.\n");
        return false; // Cannot perform check
    }

    for (int i = 0; i < len; i++) {
        if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') {
            push(s, exp[i]);
        }
        else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') {
            if (isEmpty(s)) {
                destroyStack(s);
                return false; // Closing bracket with no opener
            }
            char topChar = pop(s);
            if (!isMatchingPair(topChar, exp[i])) {
                destroyStack(s);
                return false; // Mismatched types
            }
        }
    }

    bool stackIsEmpty = isEmpty(s);
    destroyStack(s); // Free memory before returning
    return stackIsEmpty;
}

int main() {
    char exp1[] = "{[()]}";
    char exp2[] = "{[(])}";
    char exp3[] = "{{{";
    char exp4[] = "())";
    char exp5[] = "a+b"; // No parentheses
    char exp6[] = "";    // Empty string

    printf("Expression '%s' is %s\n", exp1, isBalanced(exp1) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp2, isBalanced(exp2) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp3, isBalanced(exp3) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp4, isBalanced(exp4) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp5, isBalanced(exp5) ? "balanced" : "not balanced");
    printf("Expression '%s' is %s\n", exp6, isBalanced(exp6) ? "balanced" : "not balanced");

    return 0;
}

Conclusion

In this lesson, you applied your knowledge of stacks to solve a practical and important problem. You have seen how a data structure's inherent properties—in this case, LIFO—can make a seemingly complex problem quite straightforward to solve.

Key Takeaways:

• The "balanced parentheses" problem is a classic example of where stacks excel.
• The core of the algorithm relies on the LIFO principle: push opening brackets, and pop to match them with closing brackets.
• The three conditions for an unbalanced expression are:
  1. A closing bracket appears while the stack is empty.
  2. A closing bracket does not match the type of the opening bracket at the top of the stack.
  3. The stack is not empty after the entire string has been processed.
• You successfully adapted a generic data structure (your integer stack) for a new data type (char), a common task in software development.

Preview of the Next Lesson:
We will now turn our attention to another fundamental linear data structure: the Queue. While a stack operates on a "Last-In, First-Out" basis, a queue uses a "First-In, First-Out" (FIFO) principle, just like a checkout line at a store. We will explore the Queue ADT, its primary operations, and how it differs from a stack.