awelgorithms

Match the nearest opener

Updated

LIFO says a closer binds to the nearest unmatched opener, not the first opener in the string. That is why a stack, not a counter of opens so far, is the structure.

What to focus on

In "([)]" the nearest opener to ')' is '[', not '('. Nearest is the top. Always peek the top. Never scan down for a matching kind.

Worked examples

nearest [

s = "([)]", at ')'
  1. top is [
  2. nearest opener is [
  3. not the earlier (

Result: does not match )

nearest (

s = "(())", last )
  1. top is (
  2. matches

Result: pop

adjacent nearest

s = "()[]", at ']'
  1. top is [
  2. the ( already closed

Result: match [

Try it

Write nearestOpener(s). s is a string of brackets. At each closer, peek the current top. That is the nearest unmatched opener. Do not search under the top. At the first closer of "([)]", the top is '['. At the last ')' of "(())", the top is '('.

s is a non-empty string of brackets. Peek the current top. Do not scan under it.

practise it with Awel find your weak spots: free skill check