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++:

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3#include <unordered_map>
4#include <set>
5
6bool AreBracketsBalanced(const std::string& inputStr) {
7    std::unordered_map<char, char> bracketMap = {
8        {'(', ')'},
9        {'[', ']'},
10        {'{', '}'}
11    };
12
13    std::set<char> openPar = {'(', '[', '{'};
14
15    std::stack<char> stack;
16
17    for (char character : inputStr) {
18        if (openPar.find(character) != openPar.end()) {
19            stack.push(character);
20        } else if (!stack.empty() && character == bracketMap[stack.top()]) {
21            stack.pop();
22        } else {
23            return false;
24        }
25    }
26    
27    return stack.empty();
28}
29
30int main() {
31    std::cout << std::boolalpha << AreBracketsBalanced("(){}[]") << std::endl;  // Output: true
32    return 0;
33}

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.

Now, we'll reverse a string, a simple yet powerful demonstration of data structure utility.

Reverse a user-input string or, in advanced applications, reorder network packets using stacks. This shows the stack's ability to alter sequence order efficiently.

Using a stack's LIFO feature, we can reverse elements. By pushing characters onto a stack and popping them out, we invert the sequence.

Here's how to implement the solution in C++:

C++
Copy to clipboard
1#include <iostream>
2#include <stack>
3#include <string>
4
5std::string ReverseString(const std::string& str) {
6    std::stack<char> stack;
7    for (char c : str) {
8        stack.push(c);
9    }
10
11    std::string reversed;
12    while (!stack.empty()) {
13        reversed += stack.top();
14        stack.pop();
15    }
16    return reversed;
17}
18
19int main() {
20    std::cout << ReverseString("Hello, World!") << std::endl;  // Output: !dlroW ,olleH
21    return 0;
22}

This solution clearly exhibits the effectiveness of stack operations. By systematically stacking and unstacking characters, we efficiently construct a reversed string.

Today, you've tackled two classic problems using stacks in C++, showcasing their practical utility. The stack's LIFO nature helped verify nested structures' correctness and reverse sequences with efficient and straightforward code. Well done on completing this lesson! The understanding you've gained is vital for solving problems where operation order is crucial. With these skills, you're better equipped for real-world scenarios involving data processing in reverse or verification of correctness.

Happy coding!