Parentheses Validation with a Stack

When I was first learning about stacks and queues, it was fun to see how these abstract data types (ADT) were being implemented all around us. Standing in line to get movie tickets utilizes a queue with its First In First Out structure while I realized my kitchen towel setup is a stack with the Last In First Out (LIFO) method.

ADTs are not necessarily data structures but are more conceptual and relate to the rules governing their user-facing behaviors rather than their core implementations. Often times, stacks and queues are referenced as data structures but it’s important to keep their ADT status in mind.

For this post, I wanted to explore stacks with the valid parentheses problem, as I found this to be a code challenge that helped solidify the usefulness of stacks for me.

Set up your variables

// Given a string containing just the characters '(', ')', '{', '}', '[' and ']', 
// determine if the input string is valid. 
// String is valid when: open brackets must be closed by the same type 
// of brackets & open brackets must be closed in the correct order.

function validParentheses(str) {
  let stack = [];
  let closeLookup = {
    ‘(‘: ‘)’,
    ‘[‘: ‘]’,
    ‘{‘: ‘}’
  }
} 

I’m using an Array to implement a basic stack. Following the LIFO structure, the last element added will be the first element to be removed. I will use .push() to add an opening bracket to the stack, and .pop() to remove the the topmost opening bracket if a closing bracket is matched. You're doing things right if only opening brackets are pushed onto the stack.

The closeLookup object features the opening brackets as keys and its corresponding closing bracket as the value.

Iterate through the string

function validParentheses(str) {
  let stack = [];
  let closeLookup = {
    ‘(‘: ‘)’,
    ‘[‘: ‘]’,
    ‘{‘: ‘}’
  }

  // looping through str
  for (let char of s) {
// If char is a closing bracket that makes a pair with the opening bracket 
// at the top of the stack, then pop off bracket
    if (char === closeLookup[stack[stack.length - 1]]) {
      stack.pop();
// unmatched char will be pushed onto the stack 
    } else {
      stack.push(char);
    }
  }
  return stack.length === 0;
}

console.log(validParentheses('{{()}[]}'); // true
console.log(validParentheses('[]}')); // false

When iterating through the string, we will be checking whether the current character is the corresponding closing bracket of the element at the top of the stack. This is why the closeLookup object is useful, as you can quickly look up what the corresponding close bracket should be be.

To break it down further, if in the stack was the following and the current character is ')':

stack = ['{', '{', '(']

we would check closeLookup[stack[stack.length -1] (which is closeLookup['(']) and see that its value is ')', confirming that the current character and the bracket at the top of the stack is a match and letting us pop off the bracket.

stack = ['{', '{']

Final step

Finally, we can use the === comparison operator to return whether the stack length is equal to zero.