Queues and stacks are fundamental to many algorithms. In this challenge we will be working with std::stack from the STL. For us Audio Programmers, stacks are a core component of procedural audio and game audio related work. With Queues and Stacks, one should be think about.

Does the order of data appearance and processing matter?

C++ is a deep language with a lot to learn. Experimentation, projects and general development practice will catapult you forward. However, sometimes it is important to step back and review some basic computer science and coding challenges. Doing so has helped me think differently about solving problems and appreciate certain aspects of C++ that are easy to forget. This is a part of the reason why I have been practicing extensively on LeetCode.

The Problem

You can find this problem here.

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true 

Example 2:

Input: "()[]{}"
Output: true 

Example 3:

Input: "(]"
Output: false 

Example 4:

Input: "([)]"
Output: false 

Example 5:

Input: "{[]}"
Output: true 

Starter Code:

class Solution {
public:
    bool isValid(string s) {
        
    }
};

Some Initial Thoughts

It is good in coding interviews to ask some clarifying questions. Think of it as a chance to bounce ideas off each other as a conversation. Some clarifying questions may concern specific cases. For instance, is this an input we can expect?

Input: ")("
Output: false 

Let us assume so while coding this question up.

Now let’s take a moment to think about this from first principles.

We are given a std::string and we need to look at each char in the string. Furthermore, the order of processing matters and we do not need to access random characters. Therefore, a std::stack seems like and ideal data structure. Essentially the process will look like this:

  • loop through the string
  • for a opening bracket char… add it to the stack
  • for a closing bracket char… is the char the complementary bracket? If so, pop the item from the stack as we have a complete pair.
  • during the loop… we need to check that the stack is not empty if we are examining a closing character.
  • after the loop… the stack must be empty because all brackets need a complement.

I think we can start coding this as we have a general outline.

A Decent Solution

class Solution {
private:
    bool isComplement(char stackValue, char candidateValue)
    {
        // check for the correct match...
        if(stackValue=='(' && candidateValue==')')
        {
            return true;
        }
        else if(stackValue=='{'&& candidateValue=='}')
        {
            return true;
        }
        else if(stackValue=='[' && candidateValue==']')
        {
            return true;
        }
        else
        {
            // ...not the correct match
            return false;
        }
    }
public:
    bool isValid(string s) {
        // this is a stack that we will use to validate our string
        std::stack<char> validationStack;
        
        // loop through each char element in the input string...
        for(auto element : s)
        {
            // we can only have one of 6 possible characters...
            
            // ...3 possible opening characters
            if((element=='(') || (element=='{') || (element=='['))
            {
                // push this character to the stack
                validationStack.push(element);
            }
            
            // ...3 possible closing characters
            if((element==')') || (element=='}') || (element==']'))
            {
                // do we even have anything on the stack?
                if(validationStack.empty() == true)
                {
                    // not valid strings -->>  "}"  "())"
                    return false;
                }
                
                // is this character the correct complement?
                bool status = isComplement(validationStack.top(), element);
                if(status == true)
                {
                    // ...we found a correct match
                    validationStack.pop();
                }
                else
                {
                    // ...this character does not match the stack character
                    return false;
                }
            }
        }
        // final check...
        // our stack must be empty in order to be valid
        if(validationStack.empty() != true)
        {
            // not valid strings -->>  "{"  "(()"
            return false;
        }
        // things are okay
        return true;
    }
};

Asymptotic Analysis

Let’s take a moment to analyze the space and time complexity of this algorithm.

The time complexity of this algorithm is O(n) as we only loop through the string once and push and pop from the std::stack as we go. Each push and pop operation is a constant time operation. If we were using a std::vector this would not necessarily be the case.

The space complexity of this algorithm is O(n). In the worst case we end up storing the entire input string. Imagine if our input was either of the following:

Input: "({({({("
Input: "[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[["

Conclusion

I hope this short tutorial has helped outline a guiding thought process on using std::stack for use in algorithm design. Stacks and Queues are useful tools when making applications that are easier to forget about. When order matters, always think about stacks and queues as part of your solution. Until next time:

Be good to each other and take it easy…

-Will ☜(゚ヮ゚☜)

Liked it? Take a second to support William Fehlhaber on Patreon!

Shopping cart

Subtotal
Shipping and discount codes are added at checkout.
Checkout

Sign up here to learn about our premium courses and more!

 

Thank you for being a part of The Audio Programmer Community!