Leveraging Stacks to Solve Common Algorithmic Challenges in TypeScript

Today, we embark on a journey through the functioning of stacks and their practical applications in solving algorithmic problems. Like a pile of plates, stacks allow us to add and remove data in a last-in, first-out manner. This lesson revolves around leveraging stacks to tackle two common algorithmic challenges.

Our first challenge involves ensuring that parentheses, braces, and brackets within a string are correctly matched — crucial for verifying syntax in programming languages and mathematical formulas.

Imagine devising a tool within a code editor that flags syntax errors by checking for mismatched brackets — a much-needed feature for developers to catch common errors early in the coding process.

In a naive approach, one might consider scanning the string and manually checking for matching closing brackets for each opening one. While this might initially seem straightforward, it fails to handle nested structures efficiently, leading to repeated scanning and potential $O(n^2)$ performance in the worst-case scenario.

A stack, however, is ideally suited for this task. It acts as a memory model, helping track the last opened bracket and ensuring its closure before moving on to the prior ones.

Our TypeScript implementation lays out the process in a structured, step-by-step manner:

function areBracketsBalanced(s: string): boolean {
    const stack: string[] = []; // stack tracking brackets
    const brackets: { [key: string]: string } = { '(': ')', '[': ']', '{': '}' };
    
    for (let char of s) {
        if (brackets[char]) { // either add bracket to check...
            stack.push(brackets[char]);
        } else { // ... or check to find a match
            if (stack.length === 0 || stack.pop() !== char) {
                return false;
            }
        }
    }
    
    // empty stack means no hanging brackets
    return stack.length === 0;
}

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

It returns false in three cases:

• If at any point we find a closing bracket and the stack is empty
• If at any point we find a closing bracket and the latest opening bracket doesn't match
• If, at the end of the process, we have any brackets left in the stack