Learn With Champak • Data Structures and Algorithms

Stacks in Python: From Palindromes to Bracketed Expressions

Learn the Last In, First Out idea by building a stack class and applying it to palindromes, balanced parentheses, and nested-expression extraction. Every example below opens in a runnable Python editor.

1. The Stack Abstract Data Type

A stack follows Last In, First Out (LIFO). The most recently inserted item is the first one removed—like the top plate in a pile.

push(item)
Add an item to the top.
pop()
Remove and return the top item.
peek()
Read the top item without removing it.
OperationPython list operationTypical time
Pushappend(item)O(1) amortized
Poppop()O(1)
Peekitems[-1]O(1)
Is empty?len(items) == 0O(1)
Checkpoint: If you push A, B, and C in that order, three pops return C, B, and A.

2. Palindrome by Reversing with a Stack

Push every character, then pop until the stack is empty. Popping reverses the word. Compare the reversed text with the original.

Runnable Example 1: madamStack reversal
Open editor in a new tab
Try it: Replace madam with level, python, and racecar. Predict the output before running.

3. Palindrome by Direct Character Comparison

This version still pushes the word onto a stack, but compares each character from the beginning of the word with characters popped from the end. It stops immediately on the first mismatch.

Runnable Example 2: early mismatchBreak early
Open editor in a new tab

The algorithm takes O(n) time and O(n) additional stack space.

4. A Two-Pointer Alternative

A palindrome can also be checked without a stack. One pointer starts at the left, another at the right, and both move toward the centre. This method uses O(1) additional space.

Runnable Example 3: phrase palindromeTwo pointers
Open editor in a new tab
Important: The supplied phrase is already lowercase and contains spaces symmetrically. For general sentences, first remove non-alphanumeric characters and normalize the case.

5. Checking Balanced Parentheses

When an opening parenthesis appears, push it. When a closing parenthesis appears, the stack must contain a matching opening parenthesis. At the end, the stack must be empty.

Runnable Example 4: validate and reveal nested expressionsParentheses
Open editor in a new tab

Why store positions instead of brackets?

Saving the index of each opening parenthesis lets us slice the original string when its closing parenthesis is found. Because the most recent opening parenthesis closes first, a stack is the natural structure.

6. Return All Bracketed Expressions

The next version turns the extraction logic into a reusable function. Each discovered substring is appended to a list, and the function returns an immutable tuple.

Runnable Example 5: return a tupleReusable function
Open editor in a new tab
Runnable Example 6: final practice copyRecap editor

The sixth link supplied with this lesson repeats the completed program. Use this copy for experimentation without changing the previous checkpoint.

Open editor in a new tab

Expected order

For (a+c*(d*t)*c), inner pairs close before outer pairs. Therefore the inner expression is discovered first, followed by the complete expression.

Practice and Assessment

  1. Add a size() method to the stack.
  2. Change the palindrome program so it ignores spaces and letter case.
  3. Extend the bracket validator to support (), [], and {}.
  4. Test an invalid expression such as (a+b)).
  5. Modify the extractor to return the start index, end index, and text of every bracketed expression.
Concept check: Why is a queue unsuitable for bracket matching?

A queue removes the oldest opening bracket first. Nested expressions require the newest unmatched opening bracket to close first, which is exactly the LIFO behaviour of a stack.

Complexity check

Each main algorithm scans the input once, so its time complexity is O(n). Stack-based versions may store up to n items, producing O(n) additional space in the worst case.