Welcome back! As we dive further into stack operations in C#, remember how these structures serve similar functions in programming as they do in simple physical tasks. For instance, when you stack plates, the last one you put on top is the first one you'll take off when setting the table. A computer's stack allows us to temporarily put away pieces of data, just as we can pile those plates and retrieve them later in the reverse order of how we placed them away. Today, we will apply the last-in, first-out principle to solve two specific problems that will solidify your understanding of stack operations in C#.

Validating nested structures such as parentheses is common in computing — it's like ensuring that a series of opened boxes are correctly closed. We will create a function to verify that a string of parentheses is properly nested and closed — essentially checking for balance.

Unbalanced parentheses can result in errors in our coding endeavors, much like a misplaced or missing piece in a complex puzzle. Our function will be that of a diligent organizer, confirming that every opened parenthesis finds its rightful closure.

If we consider a simple way to approach this problem, we could initialize a counter variable for each type of bracket (parentheses, braces, and square brackets), increment the counters when we encounter an opening bracket, and decrement it when we get a closing bracket. Although this approach checks whether we have a closing bracket for every opening bracket, it completely misses one critical aspect — the order of brackets. For the brackets to be considered balanced, every closing bracket must correspond to the most recently opened bracket of the same type, which is not checked in this approach.

A stack data structure is an efficient way to solve this problem. The stack follows the LIFO (Last In, First Out) principle, which makes it highly suitable to track the opening and closing brackets' order, as the most recently opened bracket needs to be closed before we move on to the next opening bracket.

We create a dictionary that maps each opening bracket to its corresponding closing bracket and an empty stack. Then, we iterate over each character in the string: If a character is an opening bracket, it gets appended to the stack. If a character is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.

If at any point we meet a closing bracket that doesn't match the top bracket in the stack, we return false.

First, let's introduce brackets mapping and set in C#:

C#
Copy to clipboard
1using System;
2using System.Collections.Generic;
3
4public class Program
5{
6    public static void Main(string[] args)
7    {
8        Console.WriteLine(AreBracketsBalanced("(){}[]"));  // Output: True
9    }
10
11    public static bool AreBracketsBalanced(string inputStr)
12    {
13        Dictionary<char, char> bracketMap = new Dictionary<char, char>
14        {
15            { '(', ')' },
16            { '[', ']' },
17            { '{', '}' }
18        };
19
20        HashSet<char> openPar = new HashSet<char> { '(', '[', '{' };
21        
22        // Implement the solution loop:
23        Stack<char> stack = new Stack<char>();
24
25        foreach (char character in inputStr)
26        {
27            if (openPar.Contains(character))
28            {
29                stack.Push(character);
30            }
31            // Case 1 and 2: If stack is empty or top of stack doesn't match closing bracket
32            else if (stack.Count > 0 && character == bracketMap[stack.Peek()])
33            {
34                stack.Pop();
35            }
36            else
37            {
38                // Case 3: Return false if a closing bracket is found without a matching opening bracket
39                return false;
40            }
41        }
42        
43        // Case 4: When the stack is not empty, it means there are unmatched opening brackets
44        return stack.Count == 0;
45    }
46}

It returns false in three cases:

1. If at any point we find a closing bracket and the stack of opening brackets is empty.
2. If at any point we find a closing bracket and the latest opening bracket doesn't match.
3. If at the end of the process we have any opening brackets left in the stack.

Next, we will flip the script — quite literally — by reversing strings. It may seem straightforward, but it demonstrates the effective use of data structures in computation.

Imagine you're tasked with building a function in which a user can input a string, and you need to display the reversed string as part of the application's features. Or, as a more advanced example, in computer networks, stack buffers are often used to reverse the order of packets that arrive out of order. Understanding how to reverse the order of elements using a Stack is a crucial skill.

Thanks to the stack's Last In, First Out (LIFO) feature, it serves as an excellent tool to reverse elements' order. The strategy here is straightforward: push all the characters to a stack and then pop them out. As a result, we get the reversed string.

A stack inverts addition and removal sequences, much like pressing rewind on a video. Pushing items onto a stack and later popping them off effectively turns the sequence on its head, as if by magic.

Here is how you can build the solution in C#:

C#
Copy to clipboard
1public static string ReverseString(string str)
2{
3    Stack<char> stack = new Stack<char>();
4    foreach (char c in str)
5    {
6        stack.Push(c);
7    }
8
9    System.Text.StringBuilder reversed = new System.Text.StringBuilder();
10    while (stack.Count > 0)
11    {
12        reversed.Append(stack.Pop());
13    }
14    return reversed.ToString();
15}

The stack-based solution's effectiveness is apparent, with each operation's intent communicated. We build a reversed string efficiently and expressively by systematically stacking and then unstacking characters.

Today, you've tackled two classic problems using the stack, demonstrating its practical utility. The stack's LIFO nature has allowed us to ensure the correctness of nested structures and simplify sequences' reversal with straightforward and efficient code.

Well done on completing this lesson! The understanding you've gained is crucial for solving problems where the order of operations is paramount. Now, you're better prepared for real-world scenarios where data needs to be processed in reverse or verified for correctness.

Equipped with a deeper understanding of stack operations in C#, you can confidently approach the exercises ahead. Happy coding!