# Is there way to remove not all, but only nested brackets?

Say I have a string like this

``````[[["q", "0"], "R"], "L"], ["q", [["1", "["], "]"]], [["q", ["2", "L"]], "R"], ["q", ["3", ["R", "L"]]]
``````

and I want to remove all nested brackets from it

``````["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

I understand how an algorithm could be written that does this by pushing and popping a stack or just incrementing and decrementing a counter, but I'm curious if there is a way to do this just with basic tools like `sed` or `awk`.

• Does the nesting always start at the beginning (as in your example) or do you also have cases like `[ a [ b [ c ]]] - > [a b c]`? Commented Jun 19, 2020 at 15:38
• What if `[[["q", "A"], "]"], "L"]`? May brackets go inside quotes? Commented Jun 19, 2020 at 15:52
• @nohillside good point, those cases can come up aswell. Commented Jun 19, 2020 at 16:08
• @Quasímodo had not thought of that either, ideally quoted brackets should be ignored. Commented Jun 19, 2020 at 16:10
• Could there be escaped quotes: `\"` and/or csv style quoted quotes `""` ?
– user232326
Commented Jun 21, 2020 at 21:31

`bracket.awk`:

``````BEGIN{quote=1}
{
for(i=1;i<=length;i++){
ch=substr(\$0,i,1)
pr=1
if(ch=="\""){quote=!quote}
else if(ch=="[" && quote){brk++;pr=brk<2}
else if(ch=="]" && quote){brk--;pr=brk<1}
if(pr){printf "%s",ch}
}
print ""
}
``````
``````\$ awk -f bracket.awk file
["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

The idea behind it:

Initialize `quote=1`. Read the file char-wise. Whenever a quote is found, invert `quote` variable (if `1`, it becomes `0`, and vice-versa).

Then, brackets are only counted if `quote` is set to 1 and excess brackets are not printed, according to `brk` counter.

The `print ""` statement is just to add a newline, as the `printf` above does not do it.

## With `perl`:

``````perl -pe '
s{([^]["]+|"[^"]*")|\[(?0)*\]}
{\$1 // "[". (\$& =~ s/("[^"]*"|[^]["]+)|./\$1/gr) . "]"}ge'
``````

That makes use of `perl`'s recursive regexp.

The outer `s{regex}{replacement-code}ge` tokenises the input into either:

• any sequence of characters other than `[`, `]` or `"`
• a quoted string
• a `[...]` group (using recursion in the regexp to find the matching `]`)

Then, we replace that token with itself if it's in the first two categories (`\$1`), and if not the token with the non-quoted `[`, `]` removed using the same tokenising technique in the inner substitution.

To handle escaped quotes and backslashes within quotes (like `"foo\"bar\\"`), replace `[^"]` with `(?:[^\\"]|\\.)`.

## With `sed`

If your `sed` supports the `-E` or `-r` options to work with extended regexps instead of basic ones, you could do it with a loop, replacing the innermost `[...]`s first:

``````LC_ALL=C sed -E '
:1
s/^(("[^"]*"|[^"])*\[("[^"]*"|[^]"])*)\[(("[^"]*"|[^]["])*)\]/\1\4/
t1'
``````

(using `LC_ALL=C` to speed it up and make it equivalent to the `perl` one which also ignores the user's locale when it comes to interpreting bytes as characters).

POSIXly, it should still be doable with something like:

``````LC_ALL=C sed '
:1
s/^\(\(\("[^"]*"\)*[^"]*\)*\[\(\("[^"]*"\)*[^]"]*\)*\)\[\(\(\("[^"]*"\)*[^]["]*\)*\)\]/\1\6/
t1'
``````

Here using `\(\(a\)*\(b\)*\)*` in place of `(a|b)*` as basic regexps don't have an alternation operator (the BREs of some `sed` implementations have `\|` for that, but that's not POSIX/portable).

• The result from `[\"[ ]\"]` should be `[\" \"]` (yes changing `[^"]` as needed) but it isn't.
– user232326
Commented Jun 21, 2020 at 22:03
• @Isaac, The OP doesn't mention anything about backslashes. Their input looks like json in which case you could imagine a backslash-escaped `"` could be found inside `"..."` which is why I mention it, but not `\"` outside quoted strings which would make it invalid json. Commented Jun 22, 2020 at 5:56
• So, you are assuming it must be valid json (never mentioned anywhere else). But you also mention: To handle escaped quotes, which it does only partially.
– user232326
Commented Jun 22, 2020 at 6:02
• @Isaac, I said to hande escaped quotes and backslashes within quotes. I'm working within the stated requirements, hinting at a potential extra requirement the OP might have. Having to deal with `\"` outside quotes might be another requirement the OP might have, but that sounds to me very unlikely. Commented Jun 22, 2020 at 7:07

I only posted this alternative because you said:

I understand how an algorithm could be written that does this by pushing and popping a stack or just incrementing and decrementing a counter

In reality I'd just use a counter.

``````\$ cat tst.awk
{
\$0 = encode(\$0)
sep = ""
while ( match(\$0,/\[[^][]+]/) ) {
if ( prevRstart && (RSTART > prevRstart) ) {
printf "%s%s", sep, decode(prevStr)
sep = ", "
}
prevStr = substr(\$0,RSTART,RLENGTH)
prevRstart = RSTART
\$0 = substr(\$0,1,RSTART-1) "<" substr(\$0,RSTART+1,RLENGTH-2) ">" substr(\$0,RSTART+RLENGTH)
}
printf "%s%s\n", sep, decode(prevStr)
}

function encode(str) {
gsub(/@/,"@A",str)
gsub(/[{]/,"@B",str)
gsub(/}/,"@C",str)
gsub(/</,"@D",str)
gsub(/>/,"@E",str)
gsub(/"\["/,"{",str)
gsub(/"]"/,"}",str)
return str
}

function decode(str) {
gsub(/[<>]/,"",str)
gsub(/}/,"\"]\"",str)
gsub(/[{]/,"\"[\"",str)
gsub(/@E/,">",str)
gsub(/@D/,"<",str)
gsub(/@C/,"}",str)
gsub(/@B/,"{",str)
gsub(/@A/,"@",str)
return str
}
``````

.

``````\$ awk -f tst.awk file
["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

See https://stackoverflow.com/a/35708616/1745001 for some background on what those sub()s (in that question it was sed) are doing to encode/decode those meaningful characters and strings as needed to be able to isolate the `[...]` strings.

So - what it's doing is finding `[...]` strings from the inside out, in other words given `[ [ foo ] ]` the `match("[ [ foo ] ]",/[[^][]/)` matches `[ foo ]` then we change the `[` to `<` and the `]` to `>` so that next time round the loop the `match("[ < foo > ]",/[[^][]/)` matches the whole string. Then we just have to remove the `<` and `>` before printing `[ foo ]`. It knows it's found an outermost `[...]` when the next time round the loop the matching string starts at a position beyond the previous starting position (i.e. is not inside the previous matching string) and at that time it prints whatever the previous matching string was.

I've been wondering if it's possible to write recursive lambdas in Python, so here you go:

``````echo '[[["q", "0"], "R"], "L"], ["q", [["1", "["], "]"]], [["q", ["2", "L"]], "R"], ["q", ["3", ["R", "L"]]]' | python -c 'import sys, ast; print([(lambda f: f(f))(lambda f, i=top_level_list: [e for a in i for e in (f(f,a) if isinstance(a, (tuple, list)) else (a,))]) for top_level_list in ast.literal_eval(sys.stdin.read())])'
``````

[['q', '0', 'R', 'L'], ['q', '1', '[', ']'], ['q', '2', 'L', 'R'], ['q', '3', 'R', 'L']]

[Replace the `echo` with your stdout.] Un-one-linered, the Python looks like:

``````my_list = [[["q", "0"], "R"], "L"], ["q", [["1", "["], "]"]], [["q", ["2", "L"]], "R"], ["q", ["3", ["R", "L"]]]
[(lambda f: f(f))(lambda f, i=top_level_list: [e for a in i
for e in (f(f,a)
if isinstance(a, (tuple, list)) else (a,))
])
for top_level_list in my_list]
``````

The list flattening code is recursive if an element is a tuple/list, otherwise it produces the value. The recursive lambda code allows the lambda to call itself without being named. The rest of the code just handles reading `mylist` from stdin.

Warning: if you ever put this in production expect a talking-to.

It could be done with sed:

``````sed -E ':a;s/(\[[^][]*)\[([^][]*)\]([^][]*\])/\1\2\3/;ta'
``````

The idea is to match a `[ ]` pair, inside it, match the pair to remove `[ ]` which, in turn, contains no `[` or `]`. To avoid matching one `[` or one `]` we need to use `[^][]*`. Which repeats in several places:

• `(\[[^][]*)` Match (and capture) one `[` followed by several non `[` or `]`.
• `\[` followed by one `[`
• `([^][]*)` followed by match and capture several non `[` or `]`.
• `\]` followed by one `]`
• `([^][]*\])` followed by several non `[` or `]` that end in a `]`.

Then replace the whole capture by `\1\2\3` which remove the internal `[]` pair.

Surround everything above with a label `:a` and a loop if a change was done `ta` and the replacement is repeated until no more internal `[]` pairs are found (and replaced).

• Will it account for quoted brackets? You need to make the regex more elaborate to match them. Commented Jun 20, 2020 at 4:28
• @RakeshSharma No, it won't account for "quoted brackets". I may look into that in a future version.
– user232326
Commented Jun 21, 2020 at 0:46

This `gawk` is inelegant to say the least, it will break if you even look at it too long, so you don't need to tell me........ just have a quiet and self-satisfied chuckle that you can do better.

But as it more or less works (on Wednesdays and Fridays during months with a `J` in them) and consumed 20 minutes of my life I am posting it anyway

Schroedinger's `awk` (Thx @edmorton)

``````awk -F"\\\], \\\[" '
{printf "[";
for (i=1; i<=NF; i++) {
cs=split(\$i,c,",");
for (j=1; j<=cs; j++){
sub("^ *\\[+","",c[j]); sub("\\]+\$","",c[j]);
t=(j==cs)?"]"((i<(NF-1))?", [":""):",";
printf c[j] t
}}print ""}' file

["q", "0", "R", "L"], ["q","1", "[", "]"], ["q","2", "L", "R"], ["q","3","R", "L"]
``````

Walkthrough

Split the fields `-F` on `], [` which needs to be escaped to hell and back in order to get your final element groups in the fields.

Then `split` on `,` to get the elements and consume any leading `^[` or trailing `]\$` from each element, then re-aggregate the `split` with `,` as a separator and finally re-aggregate the fields using a conditional combination of `]` and `, [`.

Heisenberg's `sed`

If you pipe to `sed` it's slightly tidier

``````awk 'BEGIN{FS="\\], \\["}{for (i=1; i<=NF; i++) print \$i}' file |
sed -E "s/(^| |,)\[+(\")/\1\2/g ;s/\]+(,|\$)/\1/g" |
awk 'BEGIN{RS=""; FS="\n";OFS="], ["}{\$1=\$1; print "["\$0"]"}'

["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

Does the same job as the first version, the first `awk` splits out the fields as before, `sed` loses the excess `[` and `]` and the final `awk` recomposes the elements by redefining `RS`, `FS` and `OFS`

• Love the description `it will break if you even look at it too long` :-). There should be a name for that - Hiesenberg programming maybe? Commented Jun 20, 2020 at 0:36
• @EdMorton Schroedingers `awk`? just put it in the box and you never know if it's broken or not until you look inside?. Commented Jun 20, 2020 at 6:51

Using recursive regex in perl we can do the required flattening of the variable.

Recursively grab the 3 types of chunks, quoted part, unquoted part but does not start another nesting, and third the nested bracket which is non quoted.

After grabbing the chunk, remove the bracket signs from the odd portions of the chunk. The odd portion is the one to the left of a double quote.

``````perl -lpe '
my \$re;
\$re = qr{\[(?:
(?>"[^"]*") |
(?>[^]"[]+) |
(??{ \$re })
)*]}x;
s/\$re/
local \$_ = \$&;
"[" .
s{([^"]*")([^"]*")|([^"]+\$)}{
\$1 =~ tr:[]::dr
. \$2 .
\$3 =~ tr:[]::dr
}xger
. "]"
/xge;
'
``````

output:

``````["q", "0", "[", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````
• Try with `[ \"[ ]\" ]`. Should it remove the internal `[]` ?
– user232326
Commented Jun 21, 2020 at 22:08

The following is another way to flatten the brackets this time using non recursive regex.

``````echo "....." |\
perl -lne '
my \$re = qr{\[ (?{ local \$a = 1 })
(?:(?(?{ ! \$a })(?!))
(?:
\[(?{ local \$a=\$a+1 }) |
\](?{ local \$a=\$a-1 }) |
(?>"[^"]*") |
(?>[^]"[]+)
)
)+
(?(?{ \$a })(?!))
}x;
print s/(\$re)/"[" .
\$1 =~ s{([^"]*(?:"|\$))}{
\$|-- ? \$1 : \$1 =~ tr:][::dr;
}regx
. "]"/regx;
'
``````

(This answer is more of an experiment to see just what it would look like to "apply the right tool for the job"—in this case, clojure. Indeed, I came to write this answer precisely because the solution in clojure occurred to me within about 10 seconds of reading the question, coupled with the fact about `(read)` I'll mention below. The rest—the true "problem" in this answer—was a 90 minute attempt to fight lisp's interactive roots. This struggle is not unknown to me; SML, particularly the New Jersey implementation, suffers from the same disadvantage.)

A lisp is the obvious choice for processing data-structures like lists. In fact, in clojure, this problem is solved by `(flatten my-list)` or `(map flatten list-of-lists)`!

But we are not done if we want to keep the input and output exactly to what is defined in the question. Here, clojure struggles under its own weight: it was built for use interactively (like so many lisps) or for use like a java program (run a main method). Neither truly facilitates the unix filter tradition of read from standard in/write to standard out. So, we will solve this challenge in several different ways, all of them more or less useful/outrageous.

We will rely on the following interesting facts:

1. Commas are whitespace in clojure, so the input given is actually a valid set of clojure vectors.
2. `(read)` reads a single object from standard in; not a line, as in many other languages, but a single clojure form (such as an s-expression or a vector).

## Metaprogramming with `cat`

Having already observed that the original input is valid clojure, we bypass reading it as input from clojure by injecting directly into a clojure program (and leave `sed` to do some rather dull formatting):

``````#! /usr/bin/env bash

clojure -e '(->> ['"\$(cat)"'] (map flatten) (map vec) (apply prn))' \
| sed -e 's/ /, /g'
``````

Running this produces

``````\$ ./nested-clj-cat <unix.in
["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

The trickery in this solution is a mix of proper quoting, a properly useful `cat`, and a subtle-but-necessary continuous coercion to vectors.

## Using `clojure` as the interpreter

Wouldn't that inner clojure script be a lot more maintainable if we could move it to a file containing code rather a quoted string? (I say this quite seriously, despite the tradition in most shell scripts of invoking `awk`/`sed`/`python`/`perl` inline with strings!)

But now we have to deal with reading standard in; unfortunately, `(read)` only reads one object at a time, while the input given is a series of objects. We could massage the data by adding a `[` to the beginning and a `]` to the end:

``````sed -e 's/^/[/' -e 's/\$/]/'
``````

But then the caller has to remember this, or the original program has to be adjusted.

So we'll build a function `read-all` that reads all the objects in a stream and returns that sequence. Then we'll apply our technique from before:

``````#! /usr/bin/env clojure

(require '[clojure.java.shell :as shell])

[stream]
(loop [acc []]
(if (= red :eof)
acc
(recur (conj acc red))))))

(map flatten)
(map vec)
(apply prn))
``````

This has another downside: we still need `sed` on the end to get the exact data! Otherwise:

``````\$ ./nested-clj-read <unix.in
["q" "0" "R" "L"] ["q" "1" "[" "]"] ["q" "2" "L" "R"] ["q" "3" "R" "L"]
``````

which is just not quite right. Perhaps we can fix this in clojure?

## Topsy-turvy: shell in clojure

It turns out that one of the following is true:

• I'm very bad at formatting strings in clojure with simple techniques (`str`, `format`), or
• Clojure is pretty horrible for formatting complex data-structures as strings

I suspect the latter only because clojure makes it very easy to pass data-structures between programs as data-structures (`prn`/`read` and the EDN format are evidence). I didn't mess with the common-lisp formatter `cl-format` that I know is capable of doing this, because I figured that might as well be too many lisps in the same jumble of languages :)

If anyone can solve this more elegantly, I would be glad to discuss it.

Ultimately, I resorted to embedding the `sed` calls inside of clojure—this does avoid the need for the caller to remember to invoke it, at the cost of adding yet more complexity to the code. In order to keep things nice and readable, I introduce the pipe macro:

``````(defmacro |
[cmd in]
`(:out (shell/sh ~@cmd :in ~in)))
``````

It needs to be a macro because `apply` won't work with non-lists after the lists and I really want `in` to be the last parameter (so that it fits with `->>`). Alas, because of `sh`'s implementation using futures, we need a call to `(shutdown-agents)` to eliminate waiting for minutes after the script is done for it to terminate.

So the final script is

``````#! /usr/bin/env clojure

(require '[clojure.java.shell :as shell])

[stream]
(loop [acc []]
(if (= red :eof)
acc
(recur (conj acc red))))))

(defmacro |
[cmd in]
`(:out (shell/sh ~@cmd :in ~in)))

(map flatten)
(map vec)
(apply prn-str)
(| ["sed" "-e" "s/ /, /g"])
print)

; needed because of shell/sh's use of futures
(shutdown-agents)
``````

And the results:

``````\$ ./nested-clj-read-with-sed <unix.in
["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````

Perfect.

## Lessons learned

Other languages have humongous benefits when it comes to proper recursive data manipulation. They don't always make acting like a unix-filter easy, however, and trying to cram them into that world often results in increased complexity. Even the short `cat` solution should give a reviewer pause—not because it's difficult to understand, but because it's just obscure enough to require some thought.

Still, perhaps it's worth considering other languages when manipulating certain forms of data: while all the other sed/perl/awk solutions I browsed here had no trouble reading in and writing out data, they had to do quite a bit of work to manipulate it. In some cases, I would call that level of work unmaintainable for the difficulty required to penetrate the commands (and I use these tools daily myself)! This is not to argue that my clojure solutions are any less impenetrable, but rather that we have two sides of a coin that really wants to be a torus: give me both, give me the ease of I/O filters know and the ease of data processing inherent to lisps/ML.

Aside: I wonder if `jq` could solve this after we wrap the input in `{}`?

We can solve this problem by means of functional programming paradigm once we realize that the input string is a valid list of lists (@LoLs).

So we store the string in a text file and "do" invoke it inside the perl code. What it does is bring to life a valid Perl data structure for free for us.

Now we simply employ a recursive map command to break down the list into their individual elements. And then decorate them in quotes and comma separate them.

``````#! /bin/env bash
echo '@::LoLs = ([[["q", "0"], "R"], "L"], ["q", [["1", "["], "]"]], [["q", ["2", "L"]], "R"], ["q", ["3", ["R", "L"]]])' > code.pl

perl -wMstrict   -le '
local \$" = ", "; #list separator
use constant A => q[ARRAY];
do "./code.pl";
print join q[, ], map { qq([\$_]) }
map {
\$_[0] ||= sub {
"@{[map {
+ref eq A ? \$_[0]->(\$_[0],@\$_) : qq(\"\$_\");
} splice @_,1]}"; #end inner map
};  #end sub
\$_[0]->(\$_[0],\$_);
} @::LoLs; # end outer map
'
``````

Result:

``````["q", "0", "R", "L"], ["q", "1", "[", "]"], ["q", "2", "L", "R"], ["q", "3", "R", "L"]
``````