Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 22

Stack Applications: Parentheses and Expressions

Recommended resources

Hello! Welcome back to your course on Data Structures and Algos.

In our last lesson, we focused on the "how" of stacks and queues, learning to implement them from scratch using arrays and linked lists. Today, we shift our focus to the "why" and "when." You will learn to apply stacks to solve two very common categories of interview problems: parentheses matching and expression evaluation.

These problems are favorites in technical interviews because they test your ability to recognize that a problem's structure—like nesting or operator precedence—maps perfectly to the Last-In, First-Out (LIFO) behavior of a stack. Mastering these patterns is a significant step in your interview preparation.

1. Pattern 1: Validating Nested Structures (Parentheses Matching)

One of the most classic stack problems is "Valid Parentheses." You are given a string containing brackets like (, ), {, }, [, and ], and you must determine if the input string is valid.

A string is valid if:

  1. Open brackets are closed by the same type of bracket.
  2. Open brackets are closed in the correct order.

For example, ()[]{} and ([{}]) are valid, but (] and ([)] are not.

While a simple counter might track if the number of open and close brackets is equal, it fails to check the order of nesting. The core insight here is that the most recently opened bracket must be the first one to be closed. This LIFO requirement is a clear signal that a stack is the ideal data structure for this problem.

The Algorithm

The stack-based approach is elegant and efficient:

  1. Initialize an empty stack.
  2. Iterate through each character of the input string.
  3. If the character is an opening bracket ((, {, [), push it onto the stack.
  4. If the character is a closing bracket (), }, ]):
    • First, check if the stack is empty. If it is, we have a closing bracket with no corresponding opener, so the string is invalid.
    • If the stack is not empty, pop the top element. This element should be the corresponding opening bracket.
    • If the popped bracket does not match the current closing bracket, the string is invalid.
  5. After iterating through the entire string, check if the stack is empty.
    • If it is, every opening bracket was correctly matched and closed, and the string is valid.
    • If it's not empty, there are unclosed opening brackets, making the string invalid.

This process is visualized clearly in the following diagram:

Validating Multiple Parentheses Using a Stack
This diagram shows the state of the stack as it processes the string `({[]})`. Opening brackets are pushed, and closing brackets are matched with the top of the stack, which is then popped. An empty stack at the end signifies a valid string.

To get a complete, in-depth guide to this problem, including a step-by-step walkthrough, complexity analysis, and common pitfalls to watch out for in an interview, please study the following resource.

20. Valid Parentheses - In-Depth Explanation

The AlgoMonster article 'Valid Parentheses - In-Depth Explanation' provides a fantastic, comprehensive breakdown of this classic problem. It covers everything from intuition to implementation and common mistakes.

Please read the following sections: 'Problem Description', 'Intuition', 'Solution Approach', 'Example Walkthrough', and 'Common Pitfalls'. Pay close attention to the pitfall about forgetting to check if the stack is empty before popping.

Test your understanding!

Trace the state of the stack as you process the string "{[()]}". Then, explain why the string "[({)]}" is invalid according to the algorithm.

Show answer

For "{[()]}":

  1. {: Push {. Stack: [{]
  2. [: Push [. Stack: [{, []
  3. (: Push (. Stack: [{, [, (]
  4. ): Stack not empty. Pop (. It matches ). Stack: [{, []
  5. ]: Stack not empty. Pop [. It matches ]. Stack: [{]
  6. }: Stack not empty. Pop {. It matches }. Stack: []
  7. End of string. Stack is empty. Valid.

For "[({)]}":

  1. [: Push [. Stack: [[]
  2. (: Push (. Stack: [[, (]
  3. {: Push {. Stack: [[, (, {]
  4. ): Stack not empty. Pop {. Mismatch! The algorithm expects a } to match the { but found a ). Therefore, the string is invalid. The LIFO order was violated.

2. Pattern 2: Expression Evaluation

Another classic application for stacks is parsing and evaluating mathematical expressions. This is fundamental to how compilers and calculators work. Expressions can come in different formats, but we'll focus on two:

  • Infix Notation: The familiar human-readable format, e.g., 5 + (2 * 3). Operators are in between operands.
  • Postfix Notation (Reverse Polish Notation - RPN): Operators come after their operands, e.g., 5 2 3 * +. This format is much easier for a computer to evaluate using a stack.

Evaluating Reverse Polish Notation (RPN)

The algorithm for evaluating an RPN expression is a textbook stack use case:

  1. Initialize an empty stack.
  2. Iterate through the tokens of the expression (numbers and operators).
  3. If the token is a number, push it onto the stack.
  4. If the token is an operator (+, -, *, /):
    • Pop the top two elements from the stack. These will be the operands. Note the order: the first popped is the right operand, the second is the left.
    • Perform the operation.
    • Push the result back onto the stack.
  5. After processing all tokens, the stack will contain exactly one number: the final result.

The following resource provides a clear explanation of this pattern and its more complex sibling, infix evaluation.

Master Stack Patterns: 7 templates for Coding Interviews

The 'Master Stack Patterns' article from Thita.ai excellently summarizes the expression evaluation pattern. We will focus on its explanation of RPN and its introduction to the challenges of infix evaluation.

Please read the section '1. Expression Evaluation (RPN/Infix)'. Focus on understanding the 'How it works' part for both RPN and Infix, and study the example Python code for evaluate_rpn.

The Challenge of Infix Evaluation

As noted in the resource, evaluating infix expressions is more complex due to operator precedence (* and / are evaluated before + and -) and parentheses. The general approach also uses stacks, but it's more involved:

  • Often, two stacks are used: one for numbers (operands) and one for operators.
  • When an operator is encountered, you check the stack of operators. If the operator at the top of the stack has higher or equal precedence, you pop it, apply it to the top two numbers from the number stack, and push the result. This process continues until the top operator has lower precedence.
  • Parentheses force immediate evaluation of the expression contained within them.

For interview purposes, recognizing that infix evaluation is a stack problem is the most important step. The LeetCode "Basic Calculator" series (I, II, III) are the canonical problems for this pattern.

Test your understanding!

Evaluate the RPN expression ["4", "13", "5", "/", "+"] step-by-step using a stack.

Show answer
  1. "4": Push 4. Stack: [4]
  2. "13": Push 13. Stack: [4, 13]
  3. "5": Push 5. Stack: [4, 13, 5]
  4. /: Pop 5 (right operand) and 13 (left operand). Calculate 13 / 5. In integer division, this is 2. Push 2. Stack: [4, 2]
  5. +: Pop 2 (right operand) and 4 (left operand). Calculate 4 + 2 = 6. Push 6. Stack: [6]
  6. End of expression. The result is the top of the stack: 6.

Conclusion

Today you've moved from theory to practice, applying stacks to solve two high-ROI interview patterns. This transition from knowing a data structure to using it to solve problems is what separates good candidates from great ones.

Key Takeaways:

  • Parentheses Matching: A stack perfectly models the LIFO nature of nested structures. Push on open, pop and check on close. An empty stack at the end means success.
  • Expression Evaluation (RPN): A stack is used to hold operands until an operator is encountered. This elegantly handles the order of operations without needing to worry about precedence.
  • Pattern Recognition: The core skill is identifying a problem's inherent LIFO logic. If you hear words like "nested," "matching," or see problems that require reversing order or deferring calculations, your first thought should be "stack."

In our next lesson, we will explore a more specialized but powerful stack pattern: the monotonic stack. You'll learn how to use it to efficiently solve "next greater/smaller element" problems, another common and clever interview question type.