Stack • Classic Algorithm

Valid Parentheses

Given a string containing just the characters '(', ')', ', ', '[' and ']', determine if the input string is structurally valid.

Try Interactive Simulator

The LIFO Requirement

When you open a `[`, you cannot close it until any inner brackets like `{` are completely resolved. The last bracket opened MUST be the first bracket closed. This maps perfectly to a Stack.

The Algorithm

Iterate through the string. If it's an opening bracket, push it. If it's a closing bracket, peek the stack. If it matches the corresponding opening bracket, pop it. Otherwise, the string is invalid.

Edge Cases

1. Closing bracket with an empty stack (e.g., `]`).
2. Reaching the end of the string but the stack isn't empty (e.g., `[`). In both cases, return false.

{

[

(

)

]

}

Stack

Code Tracker

:::

1function isValid(s) {

2 let stack = [];

3 for (let char of s) {

4 if (char === '(' || char === '{' || char === '[') {

5 stack.push(char);

6 } else {

7 if (stack.length === 0) return false;

8 let top = stack.pop();

9 if ((char === ')' && top !== '(') ||

10 (char === '}' && top !== '{') ||

11 (char === ']' && top !== '[')) {

12 return false;

13 }

14 }

15 }

16 return stack.length === 0;

17}