Dev Skills
Go·Go for coding rounds

Valid parentheses with a slice as a stack

Go has no stack type, because a slice already is one. Push with append, pop by re-slicing.

Topic 27 of 98 · 5 min to read · 55 min to build
After this topic you can
  • Write a bracket checker that uses a slice as a stack.
  • Fix the out-of-range panic when a closer arrives on an empty stack.
  • Explain why counting brackets alone is not enough.

The problem

Given a string of brackets ()[]{}, decide whether every opener is closed by the right closer, in the right order. Other characters are ignored.

Brute force first

Keep deleting "()", "[]" and "{}" from the string with strings.ReplaceAll until nothing changes. If the string ends up empty, it was valid.

Each pass is O(n) and you may need n/2 passes: O(n²) time, O(n) space for the new strings.

The approach

Push each opener. On a closer, the top of the stack must be its matching opener; pop it. At the end the stack must be empty. O(n) time, O(n) space.

parens.go
package main
import "fmt"
// valid reports whether every bracket is closed in the right order.
// A slice is the stack: append to push, re-slice to pop.
func valid(s string) bool {
	pairs := map[rune]rune{')': '(', ']': '[', '}': '{'}
	stack := []rune{}
	for _, r := range s { // range over a string yields runes, not bytes
		switch r {
		case '(', '[', '{':
			stack = append(stack, r)
		case ')', ']', '}':
			if len(stack) == 0 || stack[len(stack)-1] != pairs[r] {
				return false
			}
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0 // leftovers mean something never closed
}
func main() {
	for _, s := range []string{"()[]{}", "([{}])", "(]", "((", "", "a(b)c"} {
		fmt.Printf("%-8q %v\n", s, valid(s))
	}
}

Dry run

s = "{[]()}" with the stack solution:

charactionstack after
{opener, push{
[opener, push{[
]top is [, matches, pop{
(opener, push{(
)top is (, matches, pop{
}top is {, matches, pop(empty)
endstack emptyvalid: true

Go-specific gotchas

  • Check `len(stack) == 0` before peeking. stack[len(stack)-1] on an empty slice is an index-out-of-range panic, and a closer with nothing open is the classic edge case.
  • `range` over a string yields runes at byte offsets. Indexing s[i] gives a byte. Mixing the two is the commonest type error in string problems.
  • Popping does not free memory. stack[:len(stack)-1] keeps the backing array. Fine here; for a stack of pointers that lives a long time, set the popped slot to nil first so the GC can collect it.
  • A `switch` with several values per `case` reads better than a chain of if r == ... || r == ....
The short version
  • Slice as stack: append to push, s[:len(s)-1] to pop, s[len(s)-1] to peek.
  • Guard the empty stack before every peek.
  • Leftover openers at the end mean invalid.
Remember: Any "matching pairs, most recent first" problem is a stack.
Build this before moving on
Solve "evaluate reverse Polish notation" (["2","1","+","3","*"] → 9) with a []int stack and strconv.Atoi.
Coding challenge · checked by tests
Write valid(s string) bool that reports whether every (, [ and { is closed by the right bracket in the right order. Ignore other characters. Example: "{[]()}" → true, "([)]" → false.

Tab indents. Press Esc, then Tab, to leave the editor.

Then try these in your own editor
  1. 1The main task: Solve "evaluate reverse Polish notation" (["2","1","+","3","*"] → 9) with a []int stack and strconv.Atoi.
  2. 2Call valid(")") with the len(stack) == 0 guard removed. What happens?
  3. 3Return the length of the longest valid parentheses substring, using a stack of indices.
  4. 4Dry run "([)]". At which character does it fail, and why?
  5. 5Find the minimum number of brackets to add to make a string of ( and ) valid ("())(" needs 2).
Official documentation
Check yourselfTake the Go for coding rounds test