Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'm new to Mathematica, I've been learning by myself, and, being a Java developer for some time, it makes it hard to adapt.

I've tried to solve a Reddit challenge, and I came up with this solution:

str = "[can {and it(it (mix) up)} look silly]"
total = ""
str = StringTake[str, {2, -2}]
inix[strn_] := 
  Min[StringPosition[strn, "["], StringPosition[strn, "{"], 
  StringPosition[strn, "("]];
finix[strn_] := 
  Max[StringPosition[strn, "]"], StringPosition[strn, "}"], 
  StringPosition[strn, ")"]];    
howmany[strn_] := 
  Length[StringPosition[strn, "["]] + 
  Length[StringPosition[strn, "{"]] + 
  Length[StringPosition[strn, "("]];
brackets[x_, y_] := 
  If[x != \[Infinity], (total = 
     StringTake[str, {1, x - 1}] <> " " <> 
     StringTake[str, {y + 1, -1}] <> " " <> total; 
     str = StringTake[str, {x + 1, y - 1}]) , 
     (total = str <> " " <> total; str = "")];

Do[brackets[inix[str], finix[str]], {i, howmany[str] + 1}];
StringSplit[total, Whitespace]
StringJoin[Riffle[%, " "]]

Is there a better solution? From seeing some Mathematica code, this looks to be terribly big code. I would want just some pointers on how to improve.

share|improve this question
6  
Folks, these are all great solutions, but I do think beginning users would benefit from a bit of explanation of how your code works and why you chose to write it that way. –  Verbeia Apr 11 at 10:52
    
When I go to that link you posted, using firefox, I see empty boxes there for the code. Only when I move the mouse over the box, will the code show up there. Same with IE and Chrom. Very strange and confusing web site this reddit is. –  Nasser Apr 11 at 19:18
2  
@Nasser this is spoiler markup, and it exists here on StackExchange as well. The idea is that people might like to try the problem for themselves before they see someone else's solution. –  Oleksandr R. Apr 13 at 4:04

9 Answers 9

up vote 52 down vote accepted

In this response, I will focus upon the programming paradigm change when moving from Java to Mathematica. I will emphasize two differences between the languages. The first concerns the "feel" of writing Mathematica code. The second is about how iteration is expressed.

The "Feel" of Mathematica

Java is a reasonably conventional programming language, designed to conform to the principle of "least surprise" for programmers who are coming to it from other mainstream languages. The boundary between the language proper and the runtime libraries is well-defined. Learning Java is often just a matter of trying to find where a preconceived piece of functionality resides in the standard library.

By contrast, the symbolic nature of Mathematica blurs the line between language and library. From a strict computer science perspective, one could argue that the core language is very tiny indeed. It consists of a few data types, some term-rewriting machinery, and little else. However, it does not feel this way to use it. Instead, I would suggest that learning Mathematica is more akin to learning a natural language. There is endless vocabulary, obscure idioms, weird exceptions, and countless ways to express any given concept. For me, the act of writing Mathematica code sometimes feels more like writing prose (or perhaps even poetry). This is simultaneously Mathematica's greatest strength and its greatest weakness. On the one hand, it is flexible enough to express an algorithm in many differents styles, e.g. procedural, functional, query-based, language-based, etc. On the other hand, the computer sometimes acts like you've just read it a piece of poetry or prose :)

My advice is to learn Mathematica as if you were learning a new natural language. Slowly, patiently. Ability grows with use. Tackle lots of small problems (like this question -- you've come to the right place in Mathematica StackExchange!). Practice expressing the same concept many different ways. Read lots of code. Read random pages from the voluminous documentation -- there are many, many gems hiding in there. Don't try to bite off the whole thing at once.

Iteration

Okay, enough of the warm and fuzzy stuff. Let's talk about code. If I had to pick just one difference between Java and Mathematica to talk about, it would be iteration. Whenever we want to operate on a collection of items in Java, our first thought is to operate upon each item individually within an explicit loop (ignoring Java 8 for the moment). Mathematica takes a different approach. The first choice in Mathematica is to operate upon the collection as a single unit using implicit iteration. For example, the Java loops:

for (int i = 0; i < array.length; ++i) { result[i] = array[i] + 1; }
for (int i = 0; i < array.length; ++i) { result2[i] = someFunction(array[i]); }

would have the following Mathematica equivalents:

result = array + 1;
result2 = Map[someFunction, array];

The iteration is implicit. A big part of the study of Mathematica is about learning these higher-level functions that perform implicit iteration. Explicit iteration still happens in Mathematica, but it is not the first tool to reach for. It is almost always fruitful to seek an operator that will transform a collection in one fell swoop.

You can get a feel for iteration in Mathematica from the Functional Operations tutorial in the documentation, but you'd be hard-pressed to find a better investment of your time than to read Mathematica Programming - an advanced introduction.

One final point before we move on to the specific problem from the question. Mathematica has very few facilities to destructively alter large data structures. Any modification of, say, a list results in a copy of that list being generated. This is the Mathematica way, and one just has to embrace it. It is possible to write (often convoluted) code to minimize memory usage, but the first tool in the toolbox almost always involves lots of data structure copying. A common theme that you will find in the answers here on the Mathematica StackExchange is that the fastest algorithms frequently use the most memory. Don't fight it, unless there is no alternative. Memory is cheap. (ohh, the fading memory of C/C++ in my mind stirs restlessly :)

The Problem, At Last

As you can see from the many responses to this question, there are many ways to approach this problem. I dare say that they hardly scratch the surface of possible solutions. I will add another, but make no claim as to how it stacks up against other answers. This response is more concerned with the process of creating the solution.

Mathematica is first and foremost an exploratory programming environment. Let's explore.

The first thing we know for sure is that we will need to divide the string into pieces. Let's play:

$string = "[can {and it(it (mix) up)} look silly]";

Characters[$string]
(* {[,c,a,n, ,{,a,n,d, ,i,t,(,i,t, ,(,m,i,x,), ,u,p,),}, ,l,o,o,k, ,s,i,l,l,y,]} *)

StringSplit[$string, Characters["{[()]}"]]
(* {can ,and it,it ,mix, up,, look silly} *)

$split = StringSplit[$string, RegularExpression["(?<=[(){}[\\]])|(?=[(){}[\\]])"]]
(* {[,can ,{,and it,(,it ,(,mix,), up,),}, look silly,]} *)

That last one looks promising. Take no notice of the fact that I pulled that regex out of a hat -- this post is long enough! What we need to do is to scan for brackets and drop down a level when we see an opening one and pop back up when we see a closing one:

$changes = Replace[$split, {"["|"{"|"("->-1, "]"|"}"|")"->1, _->0}, {1}]
(* {-1,0,-1,0,-1,0,-1,0,1,0,1,1,0,1} *)

Those represent the level changes, but we are really more interested in the levels themselves. We need to keep a running total of the changes. It so happens that there is an operation for that:

$levels = Accumulate @ $changes
(* {-1,-1,-2,-2,-3,-3,-4,-4,-3,-3,-2,-1,-1,0} *)

Now we have the individual strings and their levels. We need to sort them by level. Here are a couple ways to do that. First, we could pair up each string with its level and then use SortBy:

$pairs = Transpose[{$split, $levels}]
(* {{[,-1},{can ,-1},{{,-2},{and it,-2},{(,-3},{it ,-3},{(,-4},{mix,-4},{),-3},
   { up,-3},{),-2},{},-1},{ look silly,-1},{],0}} *)

$sorted = SortBy[$pairs, {Last}]
(* {{(,-4},{mix,-4},{(,-3},{it ,-3},{),-3},{ up,-3},{{,-2},{and it,-2},{),-2},
   {[,-1},{can ,-1},{},-1},{ look silly,-1},{],0}} *)

Here, the "natural language" behaviour of Mathematica crops up. We need the sort to be stable, that is, elements at the same level must stay in the original order. The way to achieve that is to say SortBy[$pairs, {Last}]instead of SortBy[$pairs, Last]. There is a logical explanation for this (see the documentation), but it is far from obvious. This is an example of something one just picks up by experience and hard knocks.

There is another way to perform this sort that is even less obvious, but is actually a fairly common idiom:

$sorted = $split[[Ordering@$levels]]
(* {(,mix,(,it ,), up,{,and it,),[,can ,}, look silly,]} *)

Ordering does not sort the list, but rather tells you the index of each element as it would appear in a sorted list. This is useful to sort one list based upon the contents of another. It eliminates the need to assemble an intermediate list of pairs first. (Although we are still assembling an intermediate list of indices. Memory. Cheap. Remember?).

The list still contains all of the brackets. We need to remove those:

$result = DeleteCases[$sorted, "{"|"["|"("|")"|"]"|"}"]
(* {mix,it , up,and it,can , look silly} *)

We need to join the strings together:

StringJoin @@ $result
(* mixit  upand itcan  look silly *)

Hmm, we need to something about those spaces. Let's delete the excess:

StringJoin @@ StringTrim @ $result
(* mixitupand itcanlook silly *)

Oops, we need spaces between the strings.

StringJoin @@ Riffle[StringTrim @ $result, " "]
(* mix it up and it can look silly *)

Riffle? Where did that come from? Alas, it is simply vocabulary that must be memorized.

At last, we have the result. Let's pull it all together, keeping our favourites from the variations:

decode[string_] :=
  Module[{split, changes, levels, sorted, result}
  , split = StringSplit[string, RegularExpression["(?<=[(){}[\\]])|(?=[(){}[\\]])"]]
  ; changes = Replace[split, {"["|"{"|"("->-1, "]"|"}"|")"->1, _->0}, {1}]
  ; levels = Accumulate @ changes
  ; sorted = split[[Ordering@levels]]
  ; result = DeleteCases[sorted, "{"|"["|"("|")"|"]"|"}"]
  ; StringJoin @@ Riffle[StringTrim @ result, " "]
  ]

decode["[can {and it(it (mix) up)} look silly]"]
(* mix it up and it can look silly *)

If we are performing a one-off task, there is little need to search for alternative approaches as we have done above. The first approach we find is just fine, provided if gives us our result. But sometimes it takes a while to find an approach that performs well and/or is comprehensible enough to convince ourselves that it is correct. That is where the need to write, rewrite and rewrite again surfaces, just as when writing natural-language prose.

Parting Tip

The widespread mathematical ethic of terseness has taken hold in the Mathematica community. So we are just as likely to see the preceding function expressed without making the intermediate expressions explicit:

decode2[string_] :=
  StringSplit[string, RegularExpression["(?<=[(){}[\\]])|(?=[(){}[\\]])"]] //
  StringJoin @@ Riffle[
    StringTrim @ DeleteCases[
      #[[Ordering @ Accumulate @ Replace[#, {"["|"{"|"("->-1, "]"|"}"|")"->1, _->0}, {1}]]]
    , "{"|"["|"("|")"|"]"|"}"
    ]
  , " "
  ] &

decode2["[can {and it(it (mix) up)} look silly]"]
(* mix it up and it can look silly *)

There it is, fully-grown, armed and armoured as if sprung directly from Zeus' head. Time to post to StackExchange! We might consider such an approach to show little mercy to the reader, who must reverse-engineer what is happening. This is a common problem in expressive high-level languages. Terse expression can sometimes give few cues for understanding.

With experience, it becomes easier to read such expressions. In the meantime (and beyond), a little helper function can help wade through code like this:

P[x___, l_] := (Print[Row[{x, l}, " "]]; l)

This function prints out its arguments, returning the last unchanged. It can be quickly inserted at various places in a pipeline to see what they return. For example:

Module[{level = 0}
, P@StringCases["[can {and it(it (mix) up)} look silly]"
  , { s:Characters["[{("] :> (--level; ##&[])
    , s:Characters["]})"] :> (++level; ##&[])
    , s:Except@Characters["[{()}] "].. :> {s, level}
    }
  ]
] //
P@SortBy[#, {Last}]& //
#[[All, 1]]&

(*
{{can,-1},{and,-2},{it,-2},{it,-3},{mix,-4},{up,-3},{look,-1},{silly,-1}}

{{mix,-4},{it,-3},{up,-3},{and,-2},{it,-2},{can,-1},{look,-1},{silly,-1}}

{mix,it,up,and,it,can,look,silly}
*)

Note the use of P before the StringCases and the Sort, causing their results to be shown. This technique is far more "low tech" than the debuggers in the Front-End and Workbench, but in the notebook interface it is quick and easy and often all that one needs. (And the attentive reader will have noticed that the code block was yet another approach to the problem, using a semi-imperative style. Assuming said attentive reader was not put to sleep half-way through this TL;DR :)

share|improve this answer
    
It took me 15 minutes to read, but it's all good. If this doesn't earn an Accept I don't know what does. +1 –  Mr.Wizard Apr 12 at 18:47
    
I've still got you beat on the "ethic of terseness" however. ;-D –  Mr.Wizard Apr 12 at 18:50
5  
Nice read. I'll buy a copy when it's in paperback ;-). +1 –  rasher Apr 13 at 2:37
3  
@rasher Naaahhh, wait for the movie. We are hoping to get Steven Seagal to play Java, and Christopher Lloyd for Mathematica. I'm not too sure about the love triangle added to the shooting script involving Julia (Amanda Seyfried), but the climactic battle royale ought to make up for it... if we can secure the production funding for the CGI. –  WReach Apr 13 at 3:39
1  
@Mr.Wizard I do indeed love your new method. I rest my case comparing writing Mathematica to writing poetry. –  WReach Apr 13 at 13:51

StringReplace method

After reading other answers I was inspired to write a new method. I place it first because it is almost as concise as the method below yet it is more robust (and safe) because it preserves strings as strings.

str = "[can {and it(it (mix) up)} look silly]";

StringReplace[str, {"["|"{"|"(" -> -1, "]"|"}"|")" -> 1, " " -> 0}] //
  #[[ Ordering @ Accumulate[# /. _String :> 0] ]] ~Cases~ _String ~Row~ " " &
mix it up and it can look silly

This method is certainly not basic, but instead illustrates some interesting functionality in Mathematica.

Additionally this code is several times faster than WReach's decode and decode2 upon which it was based. It appears to be the fastest method posted so far.

Do[str = StringReplace[str, "mix" -> str], {15}];  (* nest the original string *)

StringLength[str]
1146883
StringReplace[str, {"["|"{"|"(" -> -1, "]"|"}"|")" -> 1, " " -> 0}] //
  #[[ Ordering @ Accumulate[# /. _String :> 0] ]] ~Cases~ _String ~Row~ " " & // 
    Timing // First

decode[str]  // Timing // First
decode2[str] // Timing // First
0.483

2.356

2.387

Note: using List @@ # to change the head before Accumulate is a bit faster still, presumably because it eliminates a useless StringExpression evaluation. It however isn't as didactic regarding Mathematica's capabilities.


Native-parser methods

Here is a method using Mathematica's parsing to assist in the process:

str = "[can {and it(it (mix) up)} look silly]";

he = ToHeldExpression @ StringReplace[str, {"["|"(" -> "{", "]"|")" -> "}"}]

Row[Join @@ Array[Cases[he, _Symbol, {99 - #}] &, 99], " "]
Hold[{can {and it {it {mix} up}} look silly}]

mix it up and it can look silly

This has one clear flaw: words such as "can" are converted to Symbols. Since all of the words in the example are lower case this works without error, but to make it robust additional holding would be required, e.g. s_Symbol :> ToString @ Unevaluated[s] or use of heldCases. I also hard-coded a maximum depth of 98 just to make the code a bit cleaner.

With the same start but using ReplaceRepeated to order and condense the expression:

First[he //. Except[Hold][a___, {x__}, b___] :> {x, a, b}] ~Row~ " "
mix it up and it can look silly

An example of how holding may be added:

silly = "Stop that! It's silly!";  (* if this appears in the output I failed *)

he //. Except[Hold][a___, {x__}, b___] :> {x, a, b} /. _[x_] :> HoldForm @ Row[x, " "]
mix it up and it can look silly
share|improve this answer
    
+1 for the patternmeister –  rasher Apr 13 at 2:39
    
@rasher Thank you. I think you might like the new one I just put at the top. :-) –  Mr.Wizard Apr 13 at 9:08
    
I giggled at that. Very cool, and Ordering to the rescue to boot. –  rasher Apr 13 at 9:16
    
The new one is very clever. I don't think I've ever seen non-strings on the rhs of StringReplace rules. Nice... –  Simon Woods Apr 13 at 10:50
    
@Simon In that case please see: (1), (2) –  Mr.Wizard Apr 13 at 16:37
str = "[can {and it(it (mix) up)} look silly]";

i = 10;
StringJoin @@ Last[Replace[Characters@str,
    {"[" | "(" | "{" :> Sow[" ", --i], "]" | ")" | "}" :> Sow["", ++i], c_ :> Sow[c, i]}
    , 1] ~Reap~ Range@10]

(* " mix it  up and it can  look silly" *)

This just scans through the characters one at a time and Sows them with an integer tag. The tag starts with a high value (i=10) and is decremented if an open bracket is encountered, and incremented when a closing bracket is encountered. The Reap collects the results in order, starting with the smallest integer tag (i.e. the most deeply nested characters).

share|improve this answer
    
Nice and clean, but can you get rid of the extra spaces without adding too much? –  Mr.Wizard Apr 11 at 17:47
    
@Mr.Wizard, I decided the use of spaces was inconsistent in the original string so didn't worry about it ;-) –  Simon Woods Apr 11 at 19:37
    
That sounds reasonable. :-) –  Mr.Wizard Apr 11 at 19:38
    
Clever as usual...+1 –  rasher Apr 13 at 2:40

This is a straightforward attempt at a recursive descent parser, favoring readability over brevity.

First, the tokenizer:

tokenize[str_] := DeleteCases[StringCases[str,
   {
    "(" -> open[1],
    "[" -> open[2],
    "{" -> open[3],
    ")" -> close[1],
    "]" -> close[2],
    "}" -> close[3],
    x : (Except[Characters["()[]{}"]] ..) :> token[StringTrim[x]]
    }], token[""]]

And the "parser":

Clear[parse]
parse[{open[i_], rest : ___}, backetStack_: {}] := 
 parse[{rest}, Prepend[backetStack, i]]

parse[{close[i_], rest : ___}, backetStack_: {}] := (
  If[Length[backetStack] == 0, Throw["No matching open bracket"]];
  If[backetStack[[1]] != i, Throw["Closing bracket doesn't match"]];
  parse[{rest}, Rest[backetStack]])

parse[{token[t_], rest : ___}, backetStack_: {}] := 
 Prepend[parse[{rest}, backetStack], 
  tokenDepth[Length[backetStack], t]]

parse[{}, {}] := {}
parse[{}, _] := (Throw["Brackets not closed"]; {})

This returns a flat list of tokens, in the same order as the input string, with the depth attached, so:

parse[tokenize[str]]

returns something like:

{tokenDepth[1, "racket for"], tokenDepth[2, "brackets"], 
 tokenDepth[3, "matching"], tokenDepth[2, "is a"], 
 tokenDepth[1, "computers"]}

All that's left is sorting the tokens by depth, and reuniting them to a string:

StringJoin[
 Riffle[Last /@ Sort[parse[tokenize[str]], #1[[1]] >= #2[[1]] &], 
  " "]]
share|improve this answer

As no one gave a FixedPoint answer, here is one:

preparedStr =
    StringReplace[
                  "((your[drink {remember to}]) ovaltine)",
                  {
                   RegularExpression["[{[(]"] -> "{",
                   RegularExpression["[)\]}]"] -> "}"
                  }]
"{{your{drink {remember to}}} ovaltine}"
lst = {};
FixedPoint[
  StringReplace[#,
                RegularExpression["{([^{}]*)}"] :> (AppendTo[lst, "$1"]; "")
               ] &,
  preparedStr];
lst // Riffle[#, " "] & // StringJoin // StringReplace[#, Whitespace -> " "] &
"remember to drink your ovaltine"

Here the StringReplace[ ] will look for the innermost substring matching the pattern "{...}", where there is no other "{" or "}" inside it, and store it to lst, then replace the matched one with "". FixedPoint will do this iteratively until the result doesn't change any more.

share|improve this answer

Reset the kernel first.

str = "[can {and it(it (mix) up)} look silly]"

new = StringReplace[
        StringReplace[str, {"(" | "[" -> "{", ")" | "]" -> "}"}],
        {(a : WordCharacter ~~ " " | "" ~~ "{") :> a <> ",{",
         (a : WordCharacter ~~ " " ~~ b : WordCharacter) :> a <> "," <> b,
         ("}" ~~ " " | "" ~~ b : WordCharacter) :> "}," <> b

    }] // ToExpression
{can, {and, it, {it, {mix}, up}}, look, silly}
StringJoin@Riffle[
  ToString /@ 
   Flatten[DeleteCases[Level[new, {#}], _List] & /@ 
     Reverse@Range@Depth@new],
  " "]
"mix it up and it can look silly"
share|improve this answer

This will give you an idea to start with I think:

target = "[racket for {brackets (matching) is a} computers]"

Rest@Reap[
  Nest[With[{s = StringPosition[#, {"{", "(", "["}][[-1, 1]], 
      e = StringPosition[#, {"}", ")", "]"}][[1, 1]]},
     Sow[StringTake[#, {s + 1, e - 1}]];
     StringDrop[#, {s, e}]] &, target, 
   Length@StringPosition[target, {"{", "(", "["}]]]

(* {{{matching,brackets  is a,racket for  computers}}} *)

The remaining braces are Mathematica's, use the result list to StringJoin or whatever else you need.

share|improve this answer
str = "[to {quite similar(answer (My) is)} Kuba's answer]";
mid = StringReplace[
    StringReplace[
        "Hold@" <> str, {"[" | "(" -> "{", "]" | ")" -> "}"}] // 
       ToExpression // InputForm // ToString, "*" -> ","] // 
   ToExpression // ReleaseHold
{to, {quite, similar, {answer, {My}, is}}, Derivative[1][Kuba], s, answer}
StringJoin@
 Riffle[ToString /@ 
   Flatten@MapAt[Reverse, 
     Flatten[Reap@
       NestWhile[
        Flatten[Sow@DeleteCases[#, a_List]; Cases[#, a_List], 1] &, 
        new, Depth@# > 2 &], 1], -1], " "]
"My answer is quite similar to Kuba' s answer"
share|improve this answer
 str = "[can {and it(it (mix) up)} look silly]"
 paren = {{"\\(", "\\)"}, {"\\[", "\\]"}, {"{", "}"}};
 allparen = StringJoin@Flatten[paren];
 re = RegularExpression[
    StringTake[
      StringJoin[#[[1]] <> "[^" <> allparen <> "]*" <> #[[2]] <> "|" & /@paren] , 
       {1, -2}]];
 sr := Function[strl,
      Fold[ (Sow[" " <> StringTake[strl, #2 + {1, -1}] <> " "];
          StringReplacePart[#1, "", #2]) &, strl,
            StringPosition[strl, re, Overlaps -> False] ]];
 StringReplace[ StringJoin@First@Last@Reap[
       NestWhile[sr, "(" <> str <> ")", # != "" &] ] ,
       {RegularExpression["^ *"] -> "",
        RegularExpression[" *$"] -> "",
        RegularExpression["  *"] -> " "}]

"mix it up and it can look silly"

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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