13
\$\begingroup\$

Inspired by @AviFS.

Given a string containing brackets, e.g.

[xyz]]abc[[def]hij[

You can parse through it with a stack of brackets. When you find an open bracket, push a value to the stack, when you find a close bracket, pop from the stack. If you make these values indices, you know where you need to remove brackets.

If you try to pop from an empty stack, the close bracket is unmatched, and the brackets left on the stack at the end are unmatched.

For example, the above would be:

[                   # PUSH index 1 - [1]
 xyz]               # POP - []
     ]              # POP from empty stack, unmatched
      abc[          # PUSH index 4 - [4]
          [         # PUSH index 5 - [4, 5]
           def]     # POP - [4]
               hij[ # PUSH index 7 - [4, 7]

After doing this, the 3rd bracket is unmatched as it pops from an empty stack, and the 4th and 7th brackets are unmatched as they were left on the stack.

Here's another way of viewing the matching:

     ]abc[
[   ]     [   ]hij[
 xyz       def    

Your challenge is to remove those unmatched brackets, leaving matched ones alone. For the above:

[   ]abc[   ]hij
 xyz     def

You may use any pair of brackets out of (), [], {}, and <>, and the input will only contain those and lowercase letters.

Testcases

[abc -> abc
[[] -> []
a[x[y]z[e]k[ -> ax[y]z[e]k
]ab[cdef]]gh[ij[klm]no]] -> ab[cdef]gh[ij[klm]no]
\$\endgroup\$
6
  • \$\begingroup\$ the bracket at index 2 that would be clearer as: the bracket at stack index 2. Likewise: the brackets at stack indices 3 and 6 \$\endgroup\$
    – Noodle9
    Mar 27 at 10:07
  • \$\begingroup\$ @Noodle9 They're not stack indices though. \$\endgroup\$
    – emanresu A
    Mar 28 at 3:23
  • \$\begingroup\$ Well I'm very confused now. Though they were string indices at first but that didn't make any sense. Then it looked like they corresponded to the stack you showed. \$\endgroup\$
    – Noodle9
    Mar 28 at 8:45
  • \$\begingroup\$ @Noodle9 Sort of the first. They're indices in the string without the alphabetic characters. \$\endgroup\$
    – emanresu A
    Mar 28 at 10:43
  • \$\begingroup\$ Maybe then simply say the first, second, or \$n^{\text{th}}\$ bracket? \$\endgroup\$
    – Noodle9
    Mar 28 at 10:49

9 Answers 9

6
\$\begingroup\$

JavaScript (Node.js), 94 91 89 78 bytes

f=s=>s==(t=s.replace(/<(\w*)>/,"0$11"))?s.replace(/[^a-z]/g,x=>['<>'[x]]):f(t)

Try it online!

-2 thanks to ophact

-11 thanks to Arnauld: When returning an array in the replace callback function, undefined values will be deleted. Eg, 'abcde'.replace(/b/,x=>['<>'[x]]) returns acde

Am curious to see how this can be improved...

We use <> for our bracket characters.

Approach:

  • Replace valid instances of <...> with 0...1 until it stops changing.
  • Remove remaining <> characters.
  • Map 01 back to <>.
    • This part could probably be golfed better. It amounts to finding a JS golf for tr. Currently we use the match (0 or 1) to index into <>, which is shorter than doing two replaces.
\$\endgroup\$
5
  • 1
    \$\begingroup\$ Since f is recursive, you must add the f= at the beginning. \$\endgroup\$
    – ophact
    Mar 27 at 12:21
  • \$\begingroup\$ Ah right, thanks. \$\endgroup\$
    – Jonah
    Mar 27 at 15:11
  • 1
    \$\begingroup\$ Use \d instead of 0|1 within the regex, and remove the + from +x (you can index with strings) \$\endgroup\$
    – ophact
    Mar 27 at 15:27
  • 1
    \$\begingroup\$ 78 bytes \$\endgroup\$
    – Arnauld
    Mar 28 at 14:20
  • \$\begingroup\$ @Arnauld Me right now \$\endgroup\$
    – Jonah
    Mar 28 at 14:24
5
\$\begingroup\$

Ruby -p, 37 29 28 bytes

$_=$_.scan(/<\g<0>*>|\w/)*''

Try it online!

Uses <> as brackets. Scans for, and prints:

  • paired brackets and anything between them,
  • letters outside brackets.

\g<0> embeds the regex within itself, allowing us to match nested bracket pairs recursively.

\$\endgroup\$
2
  • \$\begingroup\$ Nice answer. I never knew about g<0.. \$\endgroup\$
    – Jonah
    Mar 27 at 6:14
  • \$\begingroup\$ @Jonah Subexpression calls like this can be quite powerful. \$\endgroup\$
    – Dingus
    Mar 27 at 6:36
3
\$\begingroup\$

Retina 1, 35 bytes

|""L`<((<)|(?<-2>>)|\w)*(?(2)^)>|\w

Try it online! Link includes test cases. Uses <> as brackets. Explanation: |""L` indicates that Retina should list the matches without a separator, the matches being any paired bracket string or letter.

\$\endgroup\$
1
  • \$\begingroup\$ Note that the Retina 0.8.2 answers also work in Retina 1 and some of them are now shorter than this answer. \$\endgroup\$
    – Neil
    Mar 27 at 9:04
3
\$\begingroup\$

Jelly, 26 bytes

¬Ø[iⱮT,ƝịJƑ¥ƇƊFƲ¦ÐLe€Ø[oḟ1

A monadic Link that accepts a list of characters and yields a list of characters.

Try it online!

How?

Finds any "[...]" where the middle has no '[' or ']' and replaces the '[' and ']' with zeros. Repeats that until no change happens. Checks each value in the result for existence in "[]", giving a list of zeros and ones where the ones identify any '[' or ']' to remove. Logical ORs these with the input characters, to give a list of ones and characters, and then removes the ones.

¬Ø[iⱮT,ƝịJƑ¥ƇƊFƲ¦ÐLe€Ø[oḟ1 - Link: list of characters
                 ÐL        - loop while distinct applying:
                ¦          -   sparse application...
¬                          -   ...of: logical NOT (i.e. replace with a zero)
               Ʋ           -   ...to indices: last 4 links as a monad - f(Current):
 Ø[                        -     "[]"
    Ɱ                      -     map across c in Current with:
   i                       -      first 1-indexed index of c in "[]" or 0
                                     e.g. "]ab[c]d[" -> [2,0,0,1,0,2,0,1]
             Ɗ             -     last 3 links as a monad - f(X=that):
     T                     -       truthy indices       [1,4,6,8]
       Ɲ                   -       for neighbours:
      ,                    -         pair               [[1,4],[4,6],[6,8]]
            Ƈ              -       keep those for which:
           ¥               -         last 2 links as a dyad - f(Neighbours, X)
        ị                  -           Neighbours index into X (vectorises)
          Ƒ                -           is invariant under?:
         J                 -             range of length
                                       (i.e. =[1,2]? hence outer indices of "[...]"
                                        with no '[' or ']' in the middle)
              F            -     flatten -> indices of some valid []s
                     Ø[    - "[]"
                    €      - for each value in the loop result:
                   e       -   exists in "[]"?
                       o   - logical OR with the input (vectorises)
                         1 - one
                        ḟ  - filter - discard ones
\$\endgroup\$
2
\$\begingroup\$

Retina 0.8.2, 65 28 bytes

+T`<>`{}`<[^<>]*>
T`{}<>`<>_

Try it online! Link includes test cases. Uses <> as brackets. Explanation: Port of @Jonah's JavaScript answer.

+`

Repeat until no more transliterations can be made.

T`<>`{}`<[^<>]*>

Transliterate <> to {} if it's a matched pair that doesn't contain inner <>s (but it can include inner {} that were previously matched and transliterated).

T`{}<>`<>_

Transliterate {} back to <> but delete any remaining <> first.

A Replace stage can also be used for the first step for the same byte count:

+`<([^<>]*)>
{$1}
T`{}<>`<>_

Try it online! Link includes test cases.

Previous 65-byte answer deleted mismatched <>s directly:

(?<!<(?(2)$)((>)|(?<-2><)|\w)*)>|<(?!((<)|(?<-4>>)|\w)*(?(4)^)>)

Try it online! Link includes test cases. Uses <> as brackets. Explanation: Uses lookarounds and .NET balancing groups to directly match and delete unpaired brackets. Note that the lookbehind matches from right-to-left so the three parts are in the opposite order to the lookahead.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 37 bytes

FS¿⁼<ι⊞υω«F⁼>ι≔⎇υ⪫<>⊟υωι¿υ⊞υ⁺⊟υιι»⪫υω

Try it online! Link is to verbose version of code. Uses <> as brackets only because that's what I used for my Retina answers. Explanation:

FS

Start by tokenising the input string into characters and loop over them.

¿⁼<ι⊞υω«

If the next token is a <, then push an empty string to the stack, representing the characters waiting to be wrapped in <>s. Otherwise:

F⁼>ι≔⎇υ⪫<>⊟υωι

If the next token is a > then if the stack is empty then set the token to the empty string otherwise pop the balanced string from the stack and wrap it in <>s.

¿υ⊞υ⁺⊟υιι

If the stack is (now) empty then print the current balanced string otherwise append it to the top balanced string of the stack.

»⪫υω

Print any balanced string parts which were waiting to be wrapped in <>s but their closing >s were missing.

\$\endgroup\$
1
\$\begingroup\$

Python3, 136 bytes:

import re
f=lambda x:x.translate(str.maketrans({'{':'[','}':']','[':'',']':''}))if x==(x:=re.sub('\[([\w\{\}]+)*\]','{\\1}',x))else f(x)

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

R, 89 86 bytes

f=\(x,`[`=gsub)"if"(x!=(x="<([^<>]*)>"["L\\1R",x]),f(x),chartr("LR","<>","<|>"["",x]))

Attempt This Online!

Port of @Jonah's JS answer.

Uses <> as brackets and LR as intermediate replacement (to lower confusion with [] in already two other contexts).

Slightly longer, but a probably more interesting attempt with the use of Reduce:

R, 91 bytes

\(x,`[`=gsub)chartr("LR","<>","<|>"["",Reduce(\(a,b)"<([^<>]*)>"["L\\1R",a],1:nchar(x),x)])

Attempt This Online!

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 94 bytes

s->strjoin(g(g(s,"[","]"),"]","["))
g(s,l,r,i=0)=[c|c<-Vecrev(s),c==r&&i++||c!=l||i-->=0||i=0]

Attempt This Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.