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:

- Open brackets must be closed by the same type of brackets.
- 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 ☜(ﾟヮﾟ☜)

## Recent Comments