22
\$\begingroup\$

Given a string containing some parentheses and some other ASCII printable characters, like this: (abc((123))(k)) your task is to remove any sets of parentheses that are redundant.

A set of parentheses is redundant if:

  1. It encloses another set of matching parentheses, like ab((123)), or
  2. It encloses the entire string, like (abc123)

Parentheses are guaranteed to be matched in the input. Also there will never be an empty pair.

Test cases

{
   "(alpha)":              "alpha",
   "(((([))))":            "[",
   " beta(gamma)":         " beta(gamma)",
   "@lpha((lambda))":      "@lpha(lambda)",
   "(phi((theta)pi))":     "phi((theta)pi)",
   "(sigma)(omega)":       "(sigma)(omega)",
   "(sig(ma)(om)e;a)":     "sig(ma)(om)e;a",
   "(((((a)))b))":         "(a)b",
   "((b(((a)))))":         "b(a)",
   "b((a$c)(def))":        "b((a$c)(def))",
   "x(((y)(z)))":          "x((y)(z))",
   "(foo(bar))baz":        "(foo(bar))baz",
   "foo((bar)baz)":        "foo((bar)baz)",
   "(((((a)(b)))c))":      "((a)(b))c",
   "((c(((b)(a)))))":      "c((b)(a))",
   "(((a))b)c":            "((a)b)c",
   "c(b((a)))":            "c(b(a))",
   "((\"))":               "\"",
   "(('))":                "'"
   "XYZ!\"#$%&\'(*)+,-./": "XYZ!\"#$%&\'(*)+,-./",
   ":;<=>?@[\\]^_`{|}~'" : ":;<=>?@[\\]^_`{|}~'",
   "a((foo(bar))baz)z":    "a((foo(bar))baz)z",
   "a(foo((bar)baz))z":    "a(foo((bar)baz))z",
}
\$\endgroup\$
13
  • 2
    \$\begingroup\$ Suggested test case: "x(((y)(z)))": "x((y)(z))" \$\endgroup\$ Aug 1 at 20:30
  • 3
    \$\begingroup\$ @Deadcode I think the part Parenthesis are guaranteed to be matched in the input was intended to cover your issue. \$\endgroup\$
    – pajonk
    Aug 2 at 4:23
  • 2
    \$\begingroup\$ Suggested test cases: (foo(bar))baz, foo((bar)baz) \$\endgroup\$
    – Deadcode
    Aug 2 at 21:07
  • 2
    \$\begingroup\$ @Deadcode I was pretty confidant my test cases included all edge cases. Thanks for proving me very wrong. \$\endgroup\$
    – mousetail
    Aug 3 at 19:28
  • 2
    \$\begingroup\$ @KevinCruijssen Empty pairs of parenthesis are explicitly not allowed \$\endgroup\$
    – mousetail
    Aug 5 at 9:53

16 Answers 16

14
\$\begingroup\$

Regex (Perl / PCRE / Boost / Pythonregex), 45 44 45 44 43 bytes

s/(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)/$3/

Try it online! - Perl v5.28.2 / Attempt This Online! - Perl v5.36+
Try it online! - PCRE1
Try it online! - PCRE2 v10.33
Try it online! - Boost
Try it online! - Python import regex

This is a single regex substitution to be repeatedly applied until it has nothing to match. However in Boost, it is applied until there is no change (since its substitution interface apparently doesn't allow detecting whether any replacements were done).

This golf down from the 45 byte version is similar to Neil's .NET regex, in that it is flanked with (?<=\(|^) and (?=\)|$) (or equivalent). When initially writing a PCRE regex answer to this challenge, the thought occurred to me to do this, but I dismissed the idea, assuming that empty capture groups would need to be used to XNOR the flanking conditions (i.e. force them to only match if they agree on ^ and $ or \( and \)), by doing (?<=\(()|^)...(?=(?(1)\)|$)) or at least (?<=\(()|^)...(?=\1\)|$).

Then later on, after Neil posted his answer, I tried porting that approach to mine anyway. I found it to indeed return some incorrect results unless forced to agree using an empty capture group, but at that point I'd already gone with the (as it turned out incorrect) golf of [^)] in my regex. As it turns out, with [^()], the flanking approach is fully robust in recursive versions of the regex, without requiring any additional XNORing logic or atomic grouping.

s/                 # Begin substitution - match the following:
(\(|^)             # Assert either we're at the start of the string, or there
                   # is a (redundant) left-adjacent opening parenthesis.
\K                 # Keep everything matched up to this point out of the match.
                   # This is a more efficient way of doing the same thing as
                   # lookbehind in many situations.
(                  # Define recursive subroutine (?2)
    \(             # Match an opening parenthesis
    (              # At the outermost level, $3 = the following capture, i.e.
                   # with the parentheses matched outside it discarded.
        (
            (?2)   # Call (?2) recursively
        |          # or
            [^()]  # Match any character other than a parenthesis.
                   # It's not safe to reduce this to "[^)]" because if,
                   # after popping out to the top level and exiting this
                   # loop, the "\)" fails to match because there's more
                   # inside the top-level parentheses pair matched in this
                   # regex, it will backtrack and can incorrectly match an
                   # opening parenthesis here.
        )*         # Iterate the above as many times as possible, min 0
    )
    \)             # Match a closing parenthesis
)
(?=\)|$)           # Assert that either we're at the end of the string, or
                   # there is a redundant right-adjacent closing parenthesis.
/                  # Substitution - replace with the following:
$3
/                  # End substitution - no flags used

I also intend to write a single-use s/...//g substitution that will erase all the parentheses in one go, but that will be significantly more complicated and less efficient (as it will need to emulate variable-length lookbehind to erase the closing parentheses). As such, it would be demonstrable in regex101, which can only apply a substitution once. (I've done this for .NET, but intend to for PCRE2 as well.)

Regex (PCRE / Ruby), 48 49 45 44 bytes

s/(\(|^)\K(\(((\g<2>|[^()])*)\))(?=\)|$)/\3/

Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Ruby

As of 45 bytes and smaller, this is an absolutely straight port of the regex above. Previously, it needed to work around the difference in Ruby subroutine capture group behavior.

\$\large\textit{Functions}\$

Ruby, 75 76 74 72 71 66 62 bytes

-5 bytes thanks to Steffan
-4 bytes thanks to Dingus

->s{0while s[/(\(|^)\K(\(((\g<2>|[^()])*)\))(?=\)|$)/]&&=$3;s}

Try it online!

Julia v1.6.1+, 84 85 84 83 bytes

Attempt This Online! (now the same as below)

Julia v0.7+, 86 87 84 83 bytes

f(s,p=0)=s==p ? s : f(replace(s,r"(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)"=>s"\3"),s)

Try it online!

Julia's implementation of PCRE substitution appears to be deficient, not actually using pcre2_substitute() (the giveaway is that $1 $2 etc. capture group syntax is not supported). This is a shame, because PCRE2 has some advanced conditional replacement features (enabled by PCRE2_SUBSTITUTE_EXTENDED in its C interface). The explanation, though, is that it was originally integrated with PCRE1, which has no built-in substitution API – so presumably when they switched to PCRE2, they kept the substitution code they'd already written for use with PCRE1.

R v4.1.0+, 90 91 89 88 bytes

f=\(s,p=0)if(p==s)s else f(sub(r'{(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)}','\\3',s,,1),s)

Attempt This Online!

R is apparently also not using PCRE2's built-in substitution engine, otherwise $2 would work as the replacement argument.

Python (with regex), 123 108 107 106 107 106 105 bytes

-15 bytes thanks to Steffan

import regex
f=lambda s,p=0:s==p and s or f(regex.sub('(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)',r'\3',s),s)

Try it online!

For golf reasons, this continues substituting until the string is unchanged, not until there are no matches (with this regex either of those two methods will work).

Alternative 105 bytes, using essentially the same technique as suggested by VisualMelon:

import regex
def f(s):
 for i in s:s=regex.sub('(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)',r'\3',s)
 return s

Try it online!

Python 3.8+ (with regex), 100 101 100 99 bytes

lambda s:[s:=regex.sub('(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)',r'\3',s)for i in s][-1]
import regex

Can't Try it online! - Confirmed to work on my machine, but regex is not installed on TIO or ATO.

Uses essentially the same technique as suggested by VisualMelon.

PHP, 108 109 108 107 106 104 bytes

-1 bytes (→ 106) thanks to Steffan with the added bonus of now being an anonymous function
-2 bytes (→ 104) with no "Undefined variable" warning

function($s){while($p!=$s=preg_replace('/(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)/','$3',$p=$s));return$s;}

Try it online!

\$\large\textit{Full programs}\$

Perl -p, 52 51 50 51 50 49 bytes

-1 byte thanks to dingledooper and Sisyphus

1while s;(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$);$3

Attempt This Online!

PHP -F, 103 104 103 102 100 98 bytes

-2 bytes (→ 100) thanks to Steffan
-2 bytes (→ 98) with the added bonus of getting rid of the "Undefined variable" warning

<?for($s=$argn;$p!=$s=preg_replace('/(\(|^)\K(\((((?2)|[^()])*)\))(?=\)|$)/','$3',$p=$s););echo$s;

Try it online!

\$\endgroup\$
9
  • 1
    \$\begingroup\$ -1 byte based on this comment \$\endgroup\$ Aug 1 at 22:30
  • \$\begingroup\$ Noooo i wanted to solve this in regex :( \$\endgroup\$
    – Seggan
    Aug 1 at 23:37
  • \$\begingroup\$ @Seggan You still can, can't you? If you can beat this regex in the same flavor, or use a different flavor, or more than one regex, or combination of regex and non-regex code. Did you want to do it as one pure regex like I did? \$\endgroup\$
    – Deadcode
    Aug 1 at 23:39
  • \$\begingroup\$ @Deadcode I know I can. I was planning for the output to be the concatenation of the matches and was got pretty far along. \$\endgroup\$
    – Seggan
    Aug 1 at 23:41
  • 1
    \$\begingroup\$ Your Python snippet can be 106 bytes: Try it online! \$\endgroup\$
    – Steffan
    Aug 2 at 0:18
7
\$\begingroup\$

sed 4.2.2, 98 bytes

:a
s/(\(([^()]*)\))/\1/
ta
s/\(.\)(\([^()]*\))\(.\)/\1\t\2\n\3/
ta
s/^(\([^()]*\))$/\1/
y/\t\n/()/

Try it online!

-a handful of bytes thanks to Jiří for reminding me to use y.

+4 bytes thanks to Deadcode for noting that any printable ascii could be in the input string

how

:a
s/(\(([^()]*)\))/\1/  # remove a layer of any double parens
                      # not enclosing parens
ta                    # loop back to a if we changed anything
s/\(.\)(\([^()]*\))\(.\)/\1\t\2\n\3/
                      # convert (no-parens) to \tno-parens\n
                      # but only if they occur in the middle.
ta                    # loop back to a if we changed anything
s/^(\([^()]*\))$/\1/  # Remove global parens if they
                      # don't enclose any parens
y/<>/()/              # convert all our \t\n back to ()
\$\endgroup\$
9
  • \$\begingroup\$ Doesn't work for x(((y)(z))) \$\endgroup\$ Aug 1 at 20:29
  • \$\begingroup\$ You can replace last line with transliteration to save few bytes y/<>/()/. \$\endgroup\$
    – Jiří
    Aug 1 at 20:30
  • 2
    \$\begingroup\$ Sorry to bring this up at such a late time, but if the input can contain quotes, it can contain <> too... is there any way to sanitize the input so <> will be preserved? \$\endgroup\$
    – Deadcode
    Aug 5 at 9:34
  • 1
    \$\begingroup\$ @mousetail It should be corrected now. I switched the temporary delimiters from <> to tab, newline. Please lmk if that's legal. \$\endgroup\$
    – Jonah
    Aug 5 at 13:35
  • 1
    \$\begingroup\$ @Jonah I consider those fine \$\endgroup\$
    – mousetail
    Aug 5 at 13:37
5
\$\begingroup\$

Jelly,  33 30 29  27 bytes

Ø(jẹⱮØ(Œ!ż€¥/ṢƑ€ÞṪ_Ø-fƊF’œP

A full program that accepts a string and prints the result.

Try it online!

How?

Partitions the input string at its redundant parentheses and prints the characters that remain.

The redundant parentheses are found by first finding the indices of all pairs of matching parentheses in a copy of the input string that has been wrapped in parentheses, and then filtering these to those which are bounded by any other (i.e. rule 1, but removing the inner pair).

For that, the list of indices of all pairs of matching parentheses are effectively found by pairing each closing index with the opening index that is closest to its left that has not been consumed by any previous closing index. This is actually achieved by constructing all lists of pairs of opening and closing indices and finding the one that (a) has no reversed pairs and (b) has the maximal list of opening indices when ordered by their respective closing indices.

Ø(jẹⱮØ(Œ!ż€¥/ṢƑ€ÞṪ_Ø-fƊF’œP - Link: list of characters, S
Ø(                          - "()"
  j                         - join with S -> parenthesised S
     Ø(                     - "()"
    Ɱ                       - map with:
   ẹ                        -   all indices -> [open_indices, close_indices]
            /               - reduce this pair of lists by:
           ¥                -   last two links as a dyad - f(open_indices, close_indices):
       Œ!                   -     all permutations of open_indices
         ż€                 -     zip each with close_indixes
                Þ           - sort by:
               €            -  for each pair:
              Ƒ             -    is invariant under?:
             Ṣ              -      sort
                 Ṫ          - tail -> X = list of open indices that pair ascending close indices
                      Ɗ     - last three links as a monad - f(X)
                   Ø-       -   [-1,1]
                  _         -   subtract [-1,1] from each index-pair
                     f      -   X filter keep those
                                    -> redundant parentheses index pairs
                       F    - flatten
                        ’   - decrement (from indices in parenthesised S to indices in S)
                         œP - partition S at those indices, discarding borders
                            - implicit, smashing print
\$\endgroup\$
5
\$\begingroup\$

Retina, 53 52 51 55 bytes

-2 bytes by assuming balanced parentheses in the input
+4 bytes to fix a bug

.+
($&)
+`\((\((?>(\(()|[^)]|(?<-3>.))*)\))\)
$1
^.|.$

Try it online!

Step 1:

.+
($&)

Surround the string with parentheses (in addition to whatever parentheses it may already have). An alternative way to do this for the same number of bytes would have been:

^
(
$
)

Step 2:

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

Remove redundant parentheses, assuming that all parentheses are balanced in the input string.

+                    # Loop substitution until its result is equal to the input
`                    # Delimiter between Retina flags and regex
\(                   # Opening parenthesis (redundant one)
(                    # $1 = the following:
    \(               # Opening parenthesis
    (?>              # Atomic group – once the following finishes matching, lock
                     # in the match and prevent backtracking into it.
        (
            \(       # Match an opening parenthesis
            ()       # Push a capture onto the \3 stack
        |       # or
            [^)]     # Match any character other than a closing parenthesis.
        |       # or
            (?<-3>.) # By process of elimination, this character must be a
                     # closing parenthesis, but only allow removing it if it
                     # corresponds to popping a capture from the \3 stack.
        )*           # Iterate the above as many times as possible, minimum zero.
    )
    \)               # Closing parenthesis
)
\)                   # Closing parenthesis (redundant one)
                     # (newline) - delimiter between regex and substitution
$1                   # Replace with $1

Step 3:

^.|.$

Remove the pair of parentheses that surround the entire string, which are guaranteed to still be there.

PowerShell, 112 101 95 99 bytes

-6 bytes thanks to VisualMelon

[char[]]($p="($args)")|%{$p=$p-replace'\((\((?>(\(()|[^)]|(?<-3>.))*)\))\)','$1'};$p-replace'^.|.$'

Try it online!

Uses the same regex and algorithm as my Retina answer, so I figured it'd make sense to group into the same post.

Ungolfed:

$p = "($args)"
$c = [char[]]$p  # $c = $p converted to an array of characters
$c | ForEach {   # Iterate the following the same number of times as $c's length
    $p = $p -replace'\((\((?>(\(()|[^)]|(?<-3>.))*)\))\)', '$1'
}
$p -replace '^.|.$', ''

PowerShell, 94 bytes

Using Neil's regex, with a -1 byte golf from me:

[char[]]($p="$args")|%{$p=$p-replace'(^|\()\(((?>((\()|[^)]|(?<-4>.))*))\)(?=\)|$)','$1$2'};$p

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ If you're happy to use a default alias (%) you can knock a few bytes off the pwsh: ($p="($args)")-split''|%{$p=$p-replace'\((\(((\()|[^)]|(?<-3>.))*\))\)','$1'};$p-replace'^.|.$' \$\endgroup\$ Aug 2 at 7:38
4
\$\begingroup\$

Python3, 275 bytes:

lambda x:P(f(x)[1])
P=lambda x,l=0:[]==x*0and'('*l+''.join(P(i,1)for i in x)+l*')'or x
def f(s):
 r,*t=0,''
 while s:
  h,*R=s
  if'('==h:s,T=f(R);t+=T,''
  elif')'==h:r=1;break
  else:t[-1]+=h;s=R
 return s[r:],(lambda x:len(x)<2and[]==x[0]*0and x[0]or x)([*filter(None,t)])

Try it online!

\$\endgroup\$
11
  • 1
    \$\begingroup\$ 306byte \$\endgroup\$
    – okie
    Aug 2 at 0:02
  • \$\begingroup\$ 305 \$\endgroup\$ Aug 2 at 0:04
  • 1
    \$\begingroup\$ 276 \$\endgroup\$
    – Steffan
    Aug 2 at 0:16
  • 1
    \$\begingroup\$ 275 synthesizing all that \$\endgroup\$ Aug 2 at 0:17
  • 1
    \$\begingroup\$ I've decided to post this as my own answer... but thanks for inspiring it with your answer! \$\endgroup\$
    – Deadcode
    Aug 4 at 22:22
4
\$\begingroup\$

Regex (.NET), 200 bytes

s/(?<=()^\(*|)(?=\(((\()|[^)]|(?<-3>.))*(?=\)+$()|)(\).*)).(?=\1\4|\(((\()|[^)]|(?<-7>.))*\)\5$)|\)(?=\)*$()|)(?<=(.*\()(?<=^\(+()|)((\))|[^(]|(?<-12>.))*.)(?<=\8\10|^\9\(((\))|[^(]|(?<-14>.))*\).)//g

Try it on regex101!

This is a single regex substitution, to be applied once. It's one and done, erasing all the required parentheses in a single pass. This is the only kind of substitution that can be easily used on regex101; ones requiring multiple passes need to have their output manually fed back as input each time.

    (?<=
        ()             # \1 = set if to the left is a continuous stack of
                       #      opening parentheses
        ^\(*
    |
    )
    (?=
        \(             # Match an opening parenthesis.
        (
            (\()       # Push an opening parenthesis onto the \3 stack.
        |         # or
            [^)]       # Match any character other than a closing parenthesis.
        |         # or
            (?<-3>.)   # Match what must, by process of elimination (with the
                       # assumption that the input is balanced) be a closing
                       # parenthesis, while popping a capture off the \3 stack.
        )*
        (?=
            \)+$
            ()         # \4 = set if to the right is a continuous stack of
                       #      closing parentheses
        |
        )
        (\).*)         # \5 = mark spot by capturing everything to the right
    )
    .
    (?=
        # Assert \1 and \4 are both set
        \1\4
    |          # or
        # Assert that the next deeper set of parentheses is adjacent on both
        # sides to the pair we just processed.
        
        # First, match balanced parentheses the same way we did above, but one
        # level deeper, starting by asserting that the next opening parenthesis
        # is immediately adjacent.
        \(
        (
            (\()
        |
            [^)]
        |
            (?<-7>.)
        )*
        \)
        
        # Assert that this brings us exactly to the spot we marked with \5.
        \5$
    )
|
    # Do the same thing as above, but exactly in reverse. Note that lookbehinds
    # are tokenwise evaluated from right to left (bottom to top in this view
    # here). That means alternatives are still evaluated left to right within a
    # group, but the matching of groups/characters/backreferences is done from
    # right to left.
    \)
    (?=
        \)*$
        ()             # \8
    |
    )
    (?<=
        (.*\()         # \9
        (?<=
            ^\(+
            ()         # \10
        |
        )
        (
            (\))       # \12
        |
            [^(]
        |
            (?<-12>.)
        )*
        .
    )
    (?<=
        \8\10
    |
        ^\9
        \(
        (
            (\))       # \14
        |
            [^(]
        |
            (?<-14>.)
        )*
        \)
        .
    )
\$\endgroup\$
2
  • \$\begingroup\$ I take it this is only currently possible in .NET as it's the only engine with both variable-length lookbehind and some sort of balanced parenthesis detection? \$\endgroup\$
    – Neil
    Aug 6 at 8:24
  • \$\begingroup\$ @Neil No, it's possible in PCRE too, just harder – using recursion and fixed-width lookbehind to emulate variable-length lookbehind. I've got close but not quite to full validity. The length of that regex is similar to that of this .NET version, but I expect I can get it to be smaller, what with having subroutine calls. \$\endgroup\$
    – Deadcode
    Aug 6 at 8:28
4
\$\begingroup\$

Jelly, 31 29 bytes

Ø(j
ẆṚẹⱮØ(>/SƊÐḟÇ€¹œṣÇ}jʋƒÇḊṖ

Try it online!

If Jelly had a builtin for "is a balanced string", this would have been much shorter. A "replace substring" builtin could also have helped, as would better chaining rules for dyads. (My recommendation for dyad chains is to start with the left argument, then mostly use the monad chaining rules with the right argument, keeping the special case for but discarding the other dyad chaining rules. That would have saved two bytes in this program, compared to Jelly's current chaining rules, and would also be much more intuitive.) Larger-scale problems like this one can be good at exposing some of Jelly's shortcomings.

Thanks to @Unrelated String for pointing out that I'd missed a builtin – using rather than implementing it manually saved two bytes.

Explanation

Helper function 1Ŀ

The helper function encloses a string in parentheses, and is called using the shortcut Ç (which calls the other function, when only one function is available, thus there's no need to state its name explicitly).

Ø(j
Ø(     ["(", ")"]
  j    join this list by {the function argument}

Main program

Outputs a string with redundant parentheses removed.

ẆṚẹⱮØ(>/SƊÐḟÇ€¹œṣÇ}jʋƒÇḊṖ

  ẹⱮØ(>/S                      check if a string is unbalanced
   Ɱ                           for each of
    Ø(                           ["(", ")"]
  ẹ                            find the indexes at which it occurs
       /                       compare these two lists with each other
      >                          by greater than of corresponding elements
        S                      sum (i.e. true if there are any nonzeros)
         Ɗ                     parse the entire check as a single group

Ẇ                              find each substring of {the input}
 Ṛ                               ordered from longest to shortest
          Ðḟ                   keep only those that are not
  ẹⱮØ(>/SƊ                       unbalanced
            Ç€                 call `1Ŀ` on each of them
                     ƒ         iterating over this list, using an accumulator
                      Ç          initialised to `1Ŀ` of {the input}
                    ʋ            do all of the following, parsed as a group:
               œṣ                  split {the accumulator} on
                 Ç                   `1Ŀ`
                  }                    of the current list element
                   j               and join on {the current list element}
                                 {to produce the new accumulator}
              ¹                (fix for parser ambiguity)
                       ḊṖ      delete the first and last elements

There's an interesting subtlety in the check for unbalanced strings. The main idea is to check the indexes of the opening parentheses and of the close parentheses, and try to find an n for which the nth opening parenthesis appears after the nth closing parenthesis (thus, we're comparing the two lists with an element-wise > that compares corresponding elements of the two lists). However, if the number of opening parentheses differs from the number of closing parentheses, the element-wise > will be trying to compare two lists of different lengths. In this case, it ends up just outputting the extra elements literally (so, e.g., comparing [4,3,2]>[1,2,3,4] outputs [true, true, false, 4]). This doesn't make much sense mathematically, but means that (because Jelly uses 1-indexing) the result will contain a truthy element if the two lists are different lengths, so the string will be seen as unbalanced (which is correct – if the number of opening and closing parentheses differ, it can't be balanced). It took me a while to find a check for string balance that could handle both the equal-parenthesis-count and unequal-parenthesis-count cases without needing a separate check, but I'm happy with this one.

Once we have a list of all the balanced strings (say x), the algorithm is to replace ((x)) with (x). As long as this is done in order from longest to shortest, all the internal redundant parentheses will be removed.

To remove redundant parentheses around the string as a whole, the idea is to enclose the string in parentheses to start with, and remove them at the end, so that the same redundant parenthesis removal algorithm works to remove both internal and external redundant parentheses. This fits in rather nicely with the Ă construction, allowing the loop to start with a parenthesis-enclosed input without requiring any extra plumbing (if attempting to use the input directly rather than a function of it, it might well require spending another byte on parser ambiguity fixes).

\$\endgroup\$
2
  • \$\begingroup\$ 29 with =þØ(T€ -> ẹⱮØ( \$\endgroup\$ Aug 3 at 22:30
  • 1
    \$\begingroup\$ @UnrelatedString I'd specifically checked for that atom, because I'd remembered it existing, but concluded it wasn't there. Yet, it's there after all. How strange. \$\endgroup\$
    – ais523
    Aug 4 at 11:31
4
\$\begingroup\$

Retina 0.8.2, 53 52 bytes

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

Try it online! Link includes test cases. Explanation: Works by removing all inner sets of balanced parentheses that are contained by parentheses or match the whole string. Uses the assumption that all parentheses are balanced meaning that the input can't be something like (@))((@). Edit: Saved 1 byte thanks to @Deadcode pointing out that I didn't need to use lookarounds.

\$\endgroup\$
8
  • \$\begingroup\$ I didn't go with this approach because I thought the beginning and end conditions would have to be XNORed, and that would no longer be good golf. That turns out to be correct: your solution deals incorrectly with (foo(bar))baz. I'm not sure why it doesn't do the same with foo((bar)baz). \$\endgroup\$
    – Deadcode
    Aug 2 at 21:06
  • \$\begingroup\$ XNOR fix: 57 b. It's also possible 53 b works. \$\endgroup\$
    – Deadcode
    Aug 2 at 21:15
  • \$\begingroup\$ @Deadcode I think I fixed it at a cost of 4 bytes. \$\endgroup\$
    – Neil
    Aug 2 at 22:28
  • \$\begingroup\$ -1 byte. Also, my 51 byte version had the same bug as your 49 byte version, so yours is actually the winner. \$\endgroup\$
    – Deadcode
    Aug 6 at 21:39
  • \$\begingroup\$ @Deadcode Nice byte save, but is there a reason some of your answers are still using those lookarounds? (I removed both of them from my answer for consistency; of course the byte count is the same for the lookahead.) \$\endgroup\$
    – Neil
    Aug 6 at 23:15
3
\$\begingroup\$

JavaScript (Node.js), 112 bytes

a=>a.map((c,i)=>c=='('?a[a.push(!i|a[i-1]==c?[c]:c)-1]:c==')'&&(a[p=a.pop(),i+1]||c)==c?(p[0]='')+p&&c:c).join``

Try it online!

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

05AB1E, 50 47 46 bytes

®1‚„()ISkkƶ0KvyDdi‚ˆ]¯.Æʒ`αP}€¨¯ʒ®Ig‚Q}«˜Ä<õsǝ

Try it online or verify all test cases.

Original (completely different) 50 bytes approach:

ŒʒÁÁ4ôć„()©º{RQiJ®Ã®õ:õQ]vyD¦¨:}Ð'(Å?i¦¨‚¤®Ã®õ:õQè

Try it online or verify all test cases.

Both can most likely be golfed quite a bit more, but these kind of challenges aren't really 05AB1E's (nor my..) strong suit, especially with all these edge-cases.

Explanation 1:

Step 1: Get a list of all index-pairs for the balanced parenthesis:

®1,           # Push pair [-1,1]
   „()        # Push string "()"
      I       # Push the input-string
       Sk     # Get the index 0-based index of each character in string "()", 
              # or -1 if it's neither
         k    # Use that to index into the [-1,1] (basically replacing -1s with 0s and
              # vice-versa, without changing the 1s)
          ƶ   # Multiply each value by its 1-based index
           0K # Remove all 0s
v             # Loop over each index:
 y            #  Push the current index to the stack
  Ddi         #  Duplicate it, and if it's a positive index:
     ‚        #   Pair it with the top negative index of the stack
      ˆ       #   Pop and add this pair to the global array
]             # Close the if-statement and loop
 ¯            # Push the global array

Try just step 1 online.

Step 2a: Keep all the pairs which has a neighboring pair available:

.Æ             # Get all unique pairs of this list of index-pairs
  ʒ            # Filter it by:
   `           #  Pop and push both pairs separated to the stack
    α          #  Get the absolute difference at the same positions
     P         #  Product to check if both differences are 1
  }€           # After the filter: map over each pair of pairs:
    ¨          #  Remove the last one

Try steps 1 and 2a online.

Step 2b: If the input is surrounded by a pair of parenthesis, add its index-pair as well:

¯              # Push the global array of pairs again
 ʒ             # Filter it by:
     ‚         #  Pair
  ®            #  -1
   Ig          #  with the length of the input-string
      Q        #  And check if the current pair is equal to this
 }«            # After the filter: merge the two lists of step 2a and 2b together

Try steps 1 and 2 online.

Step 3: Remove all characters at those indices, and output the result:

˜              # Flatten the list of index-pairs
 Ä             # Get their absolute values, to make the negative indices positive
  <            # Subtract 1, to make the 1-based indices 0-based
   õ           # Push an empty string ""
    s          # Swap so the list of indices as at the top
     ǝ         # Insert the empty string at those indices in the (implicit)
               # input-string, basically removing them
               # (after which the result is output implicitly)

Explanation 2:

Step 1: Get all substrings of the input, and filter it to only keep those with double leading/trailing parenthesis-pairs:

Π                 # Get all substrings of the (implicit) input-string
 ʒ                 # Filter it by:
  ÁÁ               #  Rotate the substring twice to the right
    4ô             #  Split the string into parts of size 4
      ć            #  Extract the first item
       „()         #  Push string "()"
          ©        #  Store it in variable `®` (without popping)
           º       #  Mirror it to "()()"
            {      #  Sort it to "(())"
             R     #  Reverse it to "))(("
              Qi   #  If the extracted head is equal to this:
  J                #   Join the remainder-list together
   ®Ã              #   Only keep all "()"
     ®õ:õQ         #   Check if these parenthesis are well-balanced:
     ®õ:           #    Keep replacing all "()" with "" until it is no longer possible
        õQ         #    Check if the result is ""
 ]                 # Close both the if-statement and filter

Try just step 1 online.

Step 2: Replace all these filtered substrings with it's leading/trailing parenthesis removed in the input-string:

v                  # Loop over each of these filtered substrings:
 y                 #  Push the current substring
  D                #  Duplicate it
   ¦¨              #  Remove the first and last characters (the "(" and ")")
     :             #  Replace it in the (implicit) input-string
}                  # Close the loop

Try steps 1 and 2 online.

Step 3: Remove a potential leading/trailing parenthesis-pair, if everything else in the string is still well-balanced without it, and output the result:

Ð                  # Triplicate the current string
 '(Å?i            '# Pop one copy, and if it starts with a "(":
      ¦¨           #  Remove the first and last character from another copy
        ‚          #  Pair it with the string
         ¤         #  Push the string with first/last characters removed (without
                   #  popping the pair)
          ®Ã®õ:õQ  #  Same as in step 1 to check if its parenthesis are well-balanced,
                   #  resulting in 1 or 0 for truthy/falsey respectively
                 è #  Use that to index into the pair
                   # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Python 3.8, 215 204 195 214 205 bytes

-11 bytes thanks to Unrelated String
-9 bytes thanks to att
+19 +10 bytes to properly handle input containing single quotes and/or backslashes

lambda x:P(Q(eval(repr('"\''+x)[3:].translate({40:"',['",41:"'],'"}))))[1:-1]
P=lambda x:[]==x*0and'(%s)'%''.join(map(P,x))or x
Q=lambda x:(x:=[Q(y)if[]==y*0else y for y in x if y])==[[*x[0]]]and Q(*x)or x

Try it online!

This was inspired by Ajax1234's 275 byte answer, which had already had 48 bytes knocked off it (starting at 323 bytes) by okie, Unrelated String, and Steffan.

The P() lambda here is based directly on its P(). The rest is completely refactored to be functional rather than imperative, but follows a similar approach:

  1. Convert the string into a ragged list.
  2. Do the parentheses removal on the ragged list.
  3. Convert it back into a string. This will be surrounded by outermost parentheses whether or not the original was.
  4. Remove the outermost pair of parentheses.

In more detail:

repr('"\''+x)[3:] - backslash-escape single quotes and backslashes, and surround with single quotes (forces repr to use single quotes even if they're in the input, by putting a double quote in it)

.translate({40:"',['",41:"'],'"}) - replace ( with ',[' and ) with '],'

At this point, e.g. "(sig(ma)(om)ega)" will have become "'',['sig',['ma'],'',['om'],'ega'],''". When we then eval() it as Python code, it becomes a ragged list that is a tuple on the topmost level, containing lots of empty strings, '', mixed in with the strings/lists we want.

The job of Q() is to recursively remove the empty strings (which results in the original string converted to a ragged list), and unnest lists whose only element is another list.

[]==y*0 is true iff y is a list – golfed down from type(y)==list.

x:=[Q(y)if[]==y*0else y for y in x if y] recursively applies Q() to x's list elements, and removes its empty string elements.

x==[[*x[0]]] is true iff x is a list whose only element is another list – golfed down from type(x)==list and len(x)<2.

Q(*x) recursively applies Q() to the result of dropping one pair of surrounding brackets from x (unnesting it by one level).

'(((((a)(b)))c))' will have become [[['a'], ['b']], 'c'].
' beta(gamma)' will have become [' beta', ['gamma']].
'(alpha)' will have become ['alpha'].
'epsilon' will have become ['e', 'p', 's', 'i', 'l', 'o', 'n'].

P() then converts the resulting ragged list back into a string, surrounding lists' contents with parentheses and joining the strings. [1:-1] removes the outermost pair of parentheses, which will be there even if the original input didn't have them.

\$\endgroup\$
7
  • 2
    \$\begingroup\$ 195 with Q=lambda x:(x:=[Q(y)if[]==y*0else y for y in x if y])==[[*x[0]]]and Q(*x)or x \$\endgroup\$
    – att
    Aug 5 at 0:42
  • \$\begingroup\$ @att Ooh, nice one, thanks! \$\endgroup\$
    – Deadcode
    Aug 5 at 1:12
  • 2
    \$\begingroup\$ I added some test cases that contain single quotes. Not sure if this would work for those, but they are ASCII printable so they are valid in the input. \$\endgroup\$
    – mousetail
    Aug 5 at 6:38
  • 1
    \$\begingroup\$ @mousetail Oops! Didn't even think of that. I think it works with them now? \$\endgroup\$
    – Deadcode
    Aug 5 at 8:23
  • 1
    \$\begingroup\$ Looks good now, impressive answer \$\endgroup\$
    – mousetail
    Aug 5 at 8:24
3
\$\begingroup\$

Python,194 193 183 177 174 173 165 bytes

  • -1 byte since one string didn't need to be raw
  • -10 byes by using a recursive function to re-assemble the output rather than regex
  • -6 bytes thanks to @deadcode by using map() instead of a comprehension
  • -3 bytes by copying string comparison logic from dead code's answer
  • -8 bytes thanks to @deadcode and @steffan

Since it's a slightly different approach than the other python answers I think this deserved it's own answer. Probably further golfable.

lambda x:u(eval(s('\)\(','),(',s('(?<![^(]),','',s('[^()]+',lambda i:f",{i[0]!r},",x)))))[1:-1]
u=lambda g:g if''==g*0else"(%s)"%"".join(map(u,g))
import re;s=re.sub

Attempt This Online!

Explanation

  1. Extract all sequences that don't contain parenthesis and surround them by quotes and commas.
a = re.sub('[^()]+',lambda i:f",{i[0]!r},",x)
  1. Remove commas at the start of the string and right after opening parenthesis
b = re.sub('(?<![^(]),','',a)
  1. Eval the string then repr it again, this part actualy does the parenthesis removing
c = eval(b)
  1. Basically a custom repr function that ignores strings
u=lambda g:g if g*0==''else"(%s)"%"".join(map(u,g))
d=u(c)
  1. Remove the first and last character
f=e[1:-1]
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Nice answer. I wonder if you could golf it another 4 bytes ;-) it is currently beaten by a 189 byte port of Jonah's sed answer. (Though that requires Python 3.8 and yours doesn't.) \$\endgroup\$
    – Deadcode
    Aug 5 at 10:13
  • 1
    \$\begingroup\$ @Deadcode Challange accepted \$\endgroup\$
    – mousetail
    Aug 5 at 10:43
  • 1
    \$\begingroup\$ Oooh, very impressive. And: 177 bytes using the same golf that Unrelated String gave me. \$\endgroup\$
    – Deadcode
    Aug 5 at 10:54
  • 1
    \$\begingroup\$ import re;s=re.sub instead of from re import*;s=sub for -3. \$\endgroup\$
    – Steffan
    Aug 5 at 23:54
  • 1
    \$\begingroup\$ r'^,|(\(),' doesn't need the r \$\endgroup\$
    – Steffan
    Aug 5 at 23:54
3
\$\begingroup\$

Jelly, 32 30 28 27 bytes

=þØ(_/µJṁ"Äo¹ṁɗ\ḟ"JċⱮ`HnAɓx

Try it online!

Removes every pair of parentheses which is the only thing contained by either an outer pair or the entire string.

=þØ(                           Table equality with "()"
    _/                         and subtract the close parens from the open parens.
          Ä                    Cumulative sum, to get depths,
      µJṁ"                     repeat each index by its depth,
               \               and scan by:
           o                   overlay the element on the accumulator
            ¹ ɗ                then
             ṁ                 trim the accumulator to the element's length.
                ḟ"J            For each result, filter out its index.

=þØ(_/µJṁ"Äo¹ṁɗ\ḟ"J            This results in a list of lists where each list
                               uniquely represents the deepest pair of parentheses 
                               containing the corresponding element.

                   ċⱮ`         Count how many times each list appears.
                      H        Is each count halved
                       n       not equal to
=þØ(_/µ                 A      if the corresponding element is a paren?
                         ɓx    Replicate the input by that result.
\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 206 bytes

s=>eval(`[${s[[].__proto__.toString=function(){return this[1]?this.map(e=>Array.isArray(e)?`(${e})`:e).join``:this[0]+''},r='replace'](/[^()]+/g,m=>JSON.stringify(m)+',')[r](/\(/g,'[')[r](/\)/g,'],')}]`)+''

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 190 Bytes

def f(s,r="",o="("):
 while o in s:a,b=s.split(o,1);i=[b.count(o,0,i+1)-b.count(")",0,i+1) for i in range(len(b))].index(-1);s=b[i+1:];r=r+a+o+f(b[:i])+")" if r+a+s else f(b[:i])
 return r+s

No regex library!

This works by going through each open paren, finding the matching close paren, and recursing on the contents. If, at any recursion level, the parens identified enclose the whole string being considered, they are redundant and discarded (as they either enclose the whole string or enclose a substring that is immediately surrounded by another pair of parens).

Un-golfed Version:

def f(unparsed_string):
    ret = ""
    while "(" in unparsed_string:
        # Split on first open paren
        first, rest = unparsed_string.split("(", 1)
        # Find index of matching close paren; it's the first index in `rest`
        # where the number of close parens is one more than the
        # number of open parens.
        # This will error if the parens are unmatched
        close_paren_index = [
            rest[:i+1].count("(") - rest[:i+1].count(")")
            for i in range(len(rest))
        ].index(-1)
        unparsed_string = rest[close_paren_index+1:]
        if (ret + first) or unparsed_string:
            # Recurse on the contents of the identified parens
            ret += first + "(" + f(rest[:close_paren_index]) + ")"
        else:
            # If the identified parens are the beginning and end of
            # the string, they are redundant; return just the recursed payload
            ret = f(rest[:close_paren_index])
    return ret + unparsed_string
\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, nice answer! \$\endgroup\$ Aug 8 at 21:33
1
\$\begingroup\$

Rust, 408 396 bytes

I made this problem way to hard for myself

let f=|b:&[u8]|->Vec<u8>{let v=(0..).zip(b).scan(vec![],|a,(b,c)|Some(match c{40=>{a.push(b);None}41=>{Some((a.pop()?,b))}_=>None})).flatten().collect::<Vec<_>>();for k in &v{if k.0==0&&k.1==b.len()-1{return b[1..b.len()-1].to_vec();}for l in &v{if l.0==k.0+1&&l.1==k.1-1{return [&b[..k.0],&b[l.0..k.1],&b[k.1+1..]].concat();}}}return b.to_vec();};let g=|mut b:Vec<u8>|{while f(&b)!=b{b=f(&b)}b};

Attempt This Online!

Expanded version:

    // Single iteration
    let f = |b: &[u8]| -> Vec<u8> {
        // Find all pairs of parenthesis and store them in v
        let v = (0..)
            .zip(b)
            .scan(vec![], |a, (b, c)| {
                Some(match c {
                    40 => {
                        a.push(b);
                        None
                    }
                    41 => Some((a.pop()?, b)),
                    _ => None,
                })
            })
            .flatten()
            .collect::<Vec<_>>();
        // For ever pair
        for k in &v {
            // If it's the first and last, return everything except the first and last character
            if k.0 == 0 && k.1 == b.len() - 1 {
                return b[1..b.len() - 1].to_vec();
            }
            for l in &v {
                //else if a second pair touches it
                if l.0 == k.0 + 1 && l.1 == k.1 - 1 {
                    // combine 3 sections to crate the whole string again without 2 parenthesis
                    return [&b[..k.0], &b[l.0..k.1], &b[k.1 + 1..]].concat();
                }
            }
        }
        return b.to_vec();
    };
    let g = |mut b: Vec<u8>| {
        //while f(x) does something
        while f(&b) != b {
            b = f(&b)
        }
        b
    };
\$\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.