19
\$\begingroup\$

Picolisp has a feature called "super parentheses":

Brackets ('[' and ']') can be used as super parentheses. A closing bracket will match [all parentheses to and including] the innermost opening bracket, or [if there are no unmatched opening brackets] all currently open parentheses. src

Taking a string containing only the characters []() (and newline if your language requires it), remove all closing brackets [] and replace them with the corresponding parentheses. A [ is replaced with a (, but your program will not have to handle a [ or ( without a matching ] or ). Output may contain trailing newlines.

] matches as many open parens as possible until it hits a [ at which point it has to stop --DJMcMayhem

Examples

((((] -> (((())))
(([()(()])) -> (((()(()))))
) or ( or ] or [) or ([(]  -> invalid, do not need to handle
(] -> ()
((](] -> (())()
[] -> ()
[(] -> (())
[[()(]] -> ((()()))
((][(] -> (())(())
(([((](] -> ((((()))()))

This is , shortest code per language wins.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ sandboxed \$\endgroup\$
    – Wezl
    Jun 7 at 16:11
  • 1
    \$\begingroup\$ Maybe a test case where multiple ]s expand to multiple )s? \$\endgroup\$
    – Adám
    Jun 7 at 16:20
  • \$\begingroup\$ Are we guaranteed that the input will be balanced? E.g. no (([((]? \$\endgroup\$
    – Adám
    Jun 7 at 16:22
  • 1
    \$\begingroup\$ The explanation from the reference seems misleading: "A closing bracket will match the innermost opening bracket, or all currently open parentheses" whereas for, say, [(] -> (()), the closing bracket matches an opening bracket AND opening parentheses. \$\endgroup\$
    – xnor
    Jun 7 at 22:04
  • 1
    \$\begingroup\$ Historical note: The first language to support superparentheses was Interlisp; see p. 18 of Gabriel and Steele's "Evolution of Lisp". \$\endgroup\$
    – texdr.aft
    Jun 9 at 22:14

11 Answers 11

9
\$\begingroup\$

Charcoal, 26 bytes

FS≡ι)⊟υ]W∧υ⊟υκ«(F⁼ι[⊞υω⊞υ)

Try it online! Link is to verbose version of code. Explanation:

FS≡ι

Switch over each character of the input.

)⊟υ

If it's a ) then pop and print the top of the stack (which should always be a ) at this point).

]W∧υ⊟υκ

If it's a ] then pop and print the top of the stack until it becomes empty or an empty string was popped.

«(F⁼ι[⊞υω⊞υ)

Otherwise, print a (, push an empty string to the stack if it was a [, and push a ) to the stack.

\$\endgroup\$
9
\$\begingroup\$

Python 3,  117  115 bytes

-2 thanks to ovs (use mod 8 in place of mod 6 allowing the bitwise-OR in place of exponentiation; remove a space from 5!=x or with x!=5or.)

My golf of hyper-neutrino's Python 3 answer.

k=[0]
o=""
for c in input():x=ord(c)%8;o+="() ( )"[x]*(x<5or k.pop());k=[0]+k+[1]*(x==3);k[-1]+=x<3and-x|1
print(o)

Try it online!

Remaps '(', ')', '[', ']' to the integers 0, 1, 3, 5 (x) with x=ord(c)%8 then uses this for the decision making process to save quotes.

Inlines all the decision-making to avoid newlines, tabs and if-elif-else syntax.

Gets the character to output for the current input character by using x to index into "() ( )".

When the current character is one of "()" we need to add or subtract one, respectively, from the last entry in the counts list, k. To do so we check if the character is one of "()" we use x<3 (False, the value for '[' and ']' is equivalent to 0) and logical-AND that with -x bitwise-OR with 1 (-x|1) translating the 0 of ( to 1 and the 1 if ) to -1. Thus we can add x<3and-x|1.

\$\endgroup\$
3
  • \$\begingroup\$ x!=3or ... saves a byte \$\endgroup\$
    – ovs
    Jun 7 at 18:28
  • \$\begingroup\$ And another -1 with %8 instead of %6: tio.run/##LY/hisIwDID/… \$\endgroup\$
    – ovs
    Jun 7 at 18:50
  • 1
    \$\begingroup\$ Thanks @ovs, I changed x<2 to x<3 just to add a little more love :) \$\endgroup\$ Jun 8 at 0:43
8
\$\begingroup\$

PicoLisp, 211 bytes

(de f(x k)[or k(set'k(0][set'a(car x][set'b(cdr x](if x(cond[(="("a)(prin a)(f b(cons(+(car k)1)(cdr k][(=")"a)(prin a)(f b(cons(-(car k)1)(cdr k][(="["a)(prin"(")(f b(cons 1 k](1[prin(need(car k)")"](f b(cdr k]

Try it online!

-1 byte thanks to Wzl

First time using picolisp, so it's probably very badly golfed.

\$\endgroup\$
4
  • \$\begingroup\$ s/'(0/(0/ picolisp has a special case for lists starting with integers \$\endgroup\$
    – Wezl
    Jun 7 at 17:57
  • \$\begingroup\$ Shouldn't you use super-parens for some bytes less? \$\endgroup\$
    – pajonk
    Jun 7 at 18:01
  • \$\begingroup\$ @pajonk am I not already? where have i missed the chance to use them? \$\endgroup\$
    – hyper-neutrino
    Jun 7 at 18:02
  • \$\begingroup\$ Sorry, I think I've seen some earlier edit with definitely too many closing parentheses. \$\endgroup\$
    – pajonk
    Jun 7 at 18:04
5
\$\begingroup\$

Python 3, 139 bytes

o=""
k=[0]
for c in input():
	if"["<c:o+=")"*k.pop();k=[0]+k
	elif"Z"<c:k+=[1];o+="("
	elif")">c:k[-1]+=1;o+=c
	else:k[-1]-=1;o+=c
print(o)

Try it online!

-4 bytes thanks to caird coinheringaahing
bugfix thanks to Jonathan Allan

trivial attempt, will try to golf it down more later

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 158 bytes \$\endgroup\$ Jun 7 at 16:06
  • \$\begingroup\$ I think you need to reset k to [0] sometimes TIO \$\endgroup\$ Jun 7 at 16:33
  • \$\begingroup\$ ...if so ;k=[0]+k would also work for a couple of bytes less. \$\endgroup\$ Jun 7 at 16:39
  • \$\begingroup\$ @JonathanAllan Ah, thanks for catching that \$\endgroup\$
    – hyper-neutrino
    Jun 7 at 16:45
5
\$\begingroup\$

JavaScript (ES6),  96  94 bytes

Expects an array of characters. Returns a string.

a=>a.map(c=>c>{}?')'.repeat(b.pop()):b.push(-~(c>')'?c='(':b.pop()-2*(c>'(')))&&c,b=[]).join``

Try it online!

Commented

a =>                // a[] = input
a.map(c =>          // for each character c in a[]:
  c > {} ?          //   if c is ']':
    ')'             //     use ')'
    .repeat(        //     and repeat it as many times as
      b.pop()       //     recorded in the last slot,
    )               //     which is removed from b[]
  :                 //   else:
    b.push(         //     push in b[]:
      -~(           //
        c > ')' ?   //       if c is '[':
          c = '('   //         update c to '(' and push 1 (a new slot)
        :           //       else
          b.pop()   //         update the last slot (it may be undefined):
          - 2 *     //           increment it if c is '('
          (c > '(') //           decrement it if c is ')'
      )             //
    )               //     end of push()
    && c,           //     yield c
  b = []            //   start with b[] = empty array
).join``            // end of map(); join everything
\$\endgroup\$
3
  • \$\begingroup\$ can you explain what c>{} does? \$\endgroup\$
    – user100752
    Jun 7 at 18:49
  • 2
    \$\begingroup\$ @EliteDaMyth {} is implicitly coerced to the string [object Object]. So a character greater than this string must be a ]. \$\endgroup\$
    – Arnauld
    Jun 7 at 19:05
  • 1
    \$\begingroup\$ That's quite smart! thanks for the explanation \$\endgroup\$
    – user100752
    Jun 7 at 19:09
4
\$\begingroup\$

Retina 0.8.2, 49 bytes

+`(^|\[)(((\()|(?<-4>\)))*)]
$.1$*($2$#4$*)$.1$*)

Try it online! Link includes test cases. Explanation:

+`

Repeat until no more replacements can be made.

(^|\[)(((\()|(?<-4>\)))*)]

Starting at the beginning of the string or at a [, start counting (s, but subtract 1 for every ), until a ] is reached.

$.1$*($2$#4$*)$.1$*)

Append )s according to the count of remaining (s, and if we started at a [ then wrap the whole thing in )s (because the count of (s doesn't include the initial [).

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 96 bytes

f=s=>s>(s=s.replace(/.([()]*)]/,(_,m)=>'('+m+')'.repeat(3+m.length-2*m.split`)`.length)))?f(s):s

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pip, 46 bytes

L#aaR:`((\[|^)[()]*)]`{b.')X#b-2*(')Nb)R'['(}a

Try it online!

Algorithm:

  • Find the first pair of square brackets with only parentheses between them (the opening bracket is optional if we're at the beginning of the string) using regex.
  • Call the regex match minus the final bracket b. Replace the match (including the bracket) with:
    • b,
    • concatenated to a number of ) equal to the length of b minus two times the number of closing parens in b,
    • with [ replaced with (
  • Do that as many times as there are characters in the input (overkill, but gets the job done).
  • Print the result.

Different algorithm, also 46 bytes:

Fca{l|:^0cLT0?@l+:v**A OccQ'[?lPU1&O'(O')XPOl}

Try it online!

Treating the list l as a stack, loop over each character in the input:

  • If the stack is empty, put a 0 on it.
  • If the character is a parenthesis, output it and increment/decrement the top of stack.
  • If the character is an open square bracket, push a 1 to the stack and output an open parenthesis.
  • If the character is a close bracket, pop the stack and output that many close parentheses.
\$\endgroup\$
3
\$\begingroup\$

Red, 131 119 bytes

-12 bytes thanks to @9214

func[a][do{s:[""""]}parse a[any["("(insert s/1")")|")"(take s/1)|
change"[""("(insert s copy")")| change"]"(take s)]]a]

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can squeeze it down to 120 by using insert, s/1, and take instead of append, last s and take/last. \$\endgroup\$
    – 9214
    Jun 8 at 12:47
  • 1
    \$\begingroup\$ -1 more byte with do{s:[""""]} trick. \$\endgroup\$
    – 9214
    Jun 8 at 13:02
  • \$\begingroup\$ @9214 Thank you! That makes sense, why I didn't see it? :) \$\endgroup\$ Jun 8 at 13:14
2
\$\begingroup\$

Ruby 3.0.1, 123 93 92 bytes

Expects an array of characters and returns an array of characters

->x{*a=0
x.map{|c|c<?*?a[-1]+=(c<?)?1:-1):c<?]?(a<<0;c=?():c=?)*a.pop+(a[0]??):c*(*a=0));c}}

Old explanation:

-> x {
  a=[0] # this is the "stack"
  x.map do |c| # for each character `c` in input
    case c
    when ?( # ? creates a one-character string. Shorter than '('
      a[-1] += 1 # increment the top of the stack
    when ?)
      a[-1] -= 1 # decrement the top of the stack
    when ?[
      a << 0 # push a new element, 0, onto the stack
      c = ?( # 'output' an open paren in place of this character
    when ?]
      c = ?) * a.pop + # remove the last element of the array, and print that many closing parens.
      # however, we need to print another closing paren iff the stack isn't empty after we popped it.
        ( a[0] ? # ternary. a[0] is nil(falsy) if the array is empty, but 0 is truthy
          ?) : # if the array isn't empty, add another close parent
          # if the array is empty, we need to add nothing, but also add a 0 onto the array. 
          # `a<<0` is shorter, but evaluates to the array `a`.
          # `a[0]=0` evaluates to 0. 
          # any string * 0 is the empty string, so we use `c` since it's shorter than `""`
          c*(a[0]=0)
        )
    end
    c #last value evaluated is implicitly returned
  }
}
\$\endgroup\$
1
\$\begingroup\$

Vyxal ṠJs, 32 bytes

0⅛ƛk(nc[k)k-ĿI¼+⅛|\[=[1⅛\(|\)¼⌊*

Try it Online! (Try all testcases!)

0⅛ƛk(nc[k)k-ĿI¼+⅛|\[=[1⅛\(|\)¼⌊*   
 
0⅛                    Set the global array to [0]
  ƛ                     For each char n in input:
       [         |        If...
   k(nc                   n is in "()":
            Ŀ               Transliterate...
        k)                  n's index in ")("...
          k-                into [-1, 1]
             I              Cast to integer
              ¼+⅛           Add to top of global stack

|                         Otherwise...
    [    |                If...
 \[=                      n is '[':
     1⅛                     Push 1 to the global array
       \(                   Push "(" for output
         |                Otherwise:
              *             Repeat...
          \)                the string ")"...
            ¼⌊              pop(global_array) times
  • - treat [] as the string `[]`, not an empty array
  • Js - output properly
\$\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.