Stacks: Solving Problems with C#

Introduction to the Lesson

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#.

Problem 1: Validating Parentheses

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.

Problem 1: Actualization

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.

Problem 1: Naive Approach

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.

Problem 1: Efficient 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.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 1: Solution Building

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

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        Console.WriteLine(AreBracketsBalanced("(){}[]"));  // Output: True
    }

    public static bool AreBracketsBalanced(string inputStr)
    {
        Dictionary<char, char> bracketMap = new Dictionary<char, char>
        {
            { '(', ')' },
            { '[', ']' },
            { '{', '}' }
        };

        HashSet<char> openPar = new HashSet<char> { '(', '[', '{' };
        
        // Implement the solution loop:
        Stack<char> stack = new Stack<char>();

        foreach (char character in inputStr)
        {
            if (openPar.Contains(character))
            {
                stack.Push(character);
            }
            // Case 1 and 2: If stack is empty or top of stack doesn't match closing bracket
            else if (stack.Count > 0 && character == bracketMap[stack.Peek()])
            {
                stack.Pop();
            }
            else
            {
                // Case 3: Return false if a closing bracket is found without a matching opening bracket
                return false;
            }
        }
        
        // Case 4: When the stack is not empty, it means there are unmatched opening brackets
        return stack.Count == 0;
    }
}

using System;
using System.Collections.Generic;

public class Program
{
    public static void Main(string[] args)
    {
        Console.WriteLine(AreBracketsBalanced("(){}[]"));  // Output: True
    }

    public static bool AreBracketsBalanced(string inputStr)
    {
        Dictionary<char, char> bracketMap = new Dictionary<char, char>
        {
            { '(', ')' },
            { '[', ']' },
            { '{', '}' }
        };

        HashSet<char> openPar = new HashSet<char> { '(', '[', '{' };
        
        // Implement the solution loop:
        Stack<char> stack = new Stack<char>();

        foreach (char character in inputStr)
        {
            if (openPar.Contains(character))
            {
                stack.Push(character);
            }
            // Case 1 and 2: If stack is empty or top of stack doesn't match closing bracket
            else if (stack.Count > 0 && character == bracketMap[stack.Peek()])
            {
                stack.Pop();
            }
            else
            {
                // Case 3: Return false if a closing bracket is found without a matching opening bracket
                return false;
            }
        }
        
        // Case 4: When the stack is not empty, it means there are unmatched opening brackets
        return stack.Count == 0;
    }
}

It returns false in three cases:

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

Introduction to the Lesson

Problem 1: Validating Parentheses

Problem 1: Actualization

Problem 1: Naive Approach

Problem 1: Efficient Approach

Join the 1M+ learners on CodeSignal

Problem 1: Algorithm

Problem 1: Solution Building

Problem 2: Reverse a String using a Stack

Problem 2: Actualization

Problem 2: Approach Explanation

Problem 2: Solution Building

Lesson Summary