How to solve the Valid Parentheses Problem in JavaScript

###
What is the **Parentheses Problem**?

Your *function* is passed a *string* of brackets. If each open bracket in the string has a corresponding closing bracket and they're in the correct order, then this is considered a balanced string of brackets.

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

```
"[]" // Valid
"}{" // Invalid
"{({[]})}" // Valid
"{({[]}))" // Invalid
```

## Our Approach

We're going to be using a **Stack** to solve this problem. JavaScript doesn't have Stacks by default but a simple **Array** gives us enough of the original Stack functionality to make this work. This array will follow a **LIFO** (Last In First Out) behavior.

## Pseudo-code

Let's try to solve this example using plain old English

'[{()}]'

- Iterate over the entire
*string*once - For every
**open**bracket we*push*it to the stack - For every
**closed**bracket we get the last open from the stack - If both the closing and opening brackets match we
*pop* - If they don't, we end the loop and return false

## Time to Code

```
const stack = []
const brackets = {'(':')', '[':']','{':'}'}
```

We created our first data structures. An array to act as our stack and an **Object** to map our brackets.

```
for (let i = 0; i < str.length; i++) {
const currentBracket = str[i];
if (brackets[currentBracket]) {
stack.push(currentBracket)
...
```

Here we create a basic *for-loop* to iterate over our entire string. For every bracket we find we *push* it to the top of the stack **only** if is an **open** bracket.

```
const lastOpenBracket = stack[stack.length - 1];
if (brackets[lastOpenBracket] != currentBracket) {
return false;
}
stack.pop();
...
```

If the current bracket is not **open** then it must be a **closed** bracket. We grab the last **open** bracket from our *stack* and compare them. If the pair doesn't match, we return false. If they do, we **pop** the stack and continue.

Here's the entire code;

```
function isValid(str) {
const stack = []
const brackets = {'(':')', '[':']','{':'}'}
for (let i = 0; i < str.length; i++) {
const currentBracket = str[i];
if (brackets[currentBracket]) {
stack.push(currentBracket)
} else {
const lastOpenBracket = stack[stack.length - 1];
if (brackets[lastOpenBracket] != currentBracket) {
return false;
}
stack.pop();
}
}
return stack.length === 0;
}
```

## Congratulations !

We just solved the Valid Parentheses Problem. This question was a very common interview question back in the old days but its still relevant today and we can learn a lot from it. Hope you enjoyed this read, happy coding !

## Discussion (0)