Problem-solving with Stacks in C++

Welcome back! Today, we're exploring stack operations in C++. In this lesson, we will apply the concept of the stack's Last-In, First-Out (LIFO) principle to solve two specific problems that will enhance your understanding of stack operations.

In programming, ensuring the proper nesting and closing of structures like parentheses is crucial. It's akin to making sure each stack of boxes has its correct lid. We'll create a function to confirm that a string of brackets is properly nested and balanced.

Misbalanced parentheses can lead to errors, similar to losing a vital piece in a puzzle. Our function acts as a meticulous organizer, ensuring every opening parenthesis is matched by a closing one in the correct order.

The stack data structure suits this problem well due to its LIFO nature. It helps track the order of opening and closing brackets, guaranteeing all braces are closed in their proper sequence.

We'll use a std::unordered_map to map each opening bracket to its corresponding closing bracket alongside an empty std::stack. As we iterate through each character in the string, an opening bracket is pushed onto the stack. A closing bracket is checked against the top of the stack to ensure it matches the last opened bracket. If any mismatch or imbalance occurs, the function will return false.

Let's build the solution using C++:

#include <iostream>
#include <stack>
#include <unordered_map>
#include <set>

bool AreBracketsBalanced(const std::string& inputStr) {
    std::unordered_map<char, char> bracketMap = {
        {'(', ')'},
        {'[', ']'},
        {'{', '}'}
    };

    std::set<char> openPar = {'(', '[', '{'};

    std::stack<char> stack;

    for (char character : inputStr) {
        if (openPar.find(character) != openPar.end()) {
            stack.push(character);
        } else if (!stack.empty() && character == bracketMap[stack.top()]) {
            stack.pop();
        } else {
            return false;
        }
    }
    
    return stack.empty();
}

int main() {
    std::cout << std::boolalpha << AreBracketsBalanced("(){}[]") << std::endl;  // Output: true
    return 0;
}

The function returns false in the following cases:

1. Encountering a closing bracket with an empty stack.
2. Finding a mismatched closing bracket for the latest opened bracket.
3. The stack is non-empty after processing, meaning unmatched opening brackets are present.