Соответствующие скобки в строке

Ответ 1

Хорошо, вот еще один ответ, немного короче:

Clear[replaceDoubleBrackets];
replaceDoubleBrackets[str_String, openSym_String, closeSym_String] := 
Module[{n = 0},
  Apply[StringJoin, 
   Characters[str] /. {"[" :> {"[", ++n}, 
     "]" :> {"]", n--}} //. {left___, {"[", m_}, {"[", mp1_}, 
      middle___, {"]", mp1_}, {"]", m_}, right___} /; 
       mp1 == m + 1 :> {left, openSym, middle, 
        closeSym, right} /. {br : "[" | "]", _Integer} :> br]]

Пример:

In[100]:= replaceDoubleBrackets["f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]", "(", ")"]

Out[100]= "f[g[h(i(j[2], k(1, m(1, n[2]))))]]"

ИЗМЕНИТЬ

Вы также можете использовать встроенные средства Mathematica, если вы хотите заменить двойные скобки специальными символами, которые вы указали:

Clear[replaceDoubleBracketsAlt];
replaceDoubleBracketsAlt[str_String] :=
  StringJoin @@ Cases[[email protected][str, InputForm, HoldForm],
     _String, Infinity]

In[117]:= replaceDoubleBracketsAlt["f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]"]

Out[117]= f[g[h[[i[[j[2],k[[1,m[[1,n[2]]]]]]]]]]]

Результат не будет отображаться здесь правильно, но это строка Юникода с запрограммированными вами символами.

Ответ 2

Когда я написал свое первое решение, я не заметил, что вы просто хотели заменить [[ на 〚 в строке, а не на выражение. Вы всегда можете использовать HoldForm или Defer как

но я думаю, что вы уже это знали, и вы хотите, чтобы выражение как строка, так же как и вход ([email protected] по вышеописанному не работает)

Поскольку все ответы до сих пор сосредоточены на строковых манипуляциях, я возьму числовой подход вместо борьбы со строками, что для меня более естественно. Символьный код для [ равен 91, а ] равно 93. Таким образом, следующее

дает расположение скобок как вектора 0/1. Я отрицал закрывающие скобки, просто чтобы помочь мыслительному процессу и использовать его позже.

ПРИМЕЧАНИЕ: Я проверял только делимость на 91 и 93, так как я, конечно, не ожидаю, что вы введете любой из следующих символов, но если по какой-то причине вы решите, вы можете легко AND получить результат выше с логическим списком равенства с 91 или 93.

Таким образом, позиции первой пары Part двойных кронштейнов можно найти как

Тот факт, что в mma выражения не начинаются с [ и что более двух [ не может появляться последовательно, поскольку [[[... неявно принимается в приведенном выше вычислении.

Теперь закрывающая пара сложнее реализовать, но просто понять. Идея такова:

• Для каждой ненулевой позиции в closeBracket, скажем i, перейдите в соответствующую позицию в openBracket и найдите первую ненулевую позицию слева от нее (скажем j).
• Установите doubleCloseBrackets[[i-1]]=closeBracket[[i]]+openBracket[[j]]+doubleOpenBrackets[[j]].
• Вы можете видеть, что doubleCloseBrackets является аналогом doubleOpenBrackets и не равен нулю в позиции первой пары Part ]].

Итак, теперь у нас есть набор булевых положений для первой открытой скобки. Нам просто нужно заменить соответствующий элемент в charCode эквивалентом 〚 и аналогичным образом, с булевыми положениями для первой закрывающей скобки, заменим соответствующий элемент в charCode эквивалентом 〛.

Наконец, удалив элемент рядом с теми, которые были изменены, вы можете получить измененную строку с заменой [[]] на 〚 〛

ПРИМЕЧАНИЕ 2:

Многие из моих привычек MATLAB подкрались в вышеприведенный код и не совсем идиоматичны в Mathematica. Однако, я думаю, что логика правильная, и она работает. Я оставлю это для вас, чтобы оптимизировать его (я думаю, вы можете покончить с Do[]) и сделать его модулем, так как мне потребуется намного больше времени, чтобы это сделать.

Код как текст

Clear["Global`*"]
str = "f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]";
charCode = [email protected];
openBracket = [email protected][charCode, [email protected]["["]];
closeBracket = [email protected]
    Divisible[charCode, [email protected]["]"]];
doubleOpenBracket = 
  Append[[email protected][openBracket], 0] openBracket;
posClose = [email protected][Position[closeBracket, [email protected], {1}], 1];

doubleCloseBracket = ConstantArray[0, [email protected]];
openBracketDupe = openBracket + doubleOpenBracket;
Do[
  tmp = [email protected]
    [email protected][openBracketDupe[[1 ;; i]], [email protected], {1}];
  doubleCloseBracket[[i - 1]] = 
   closeBracket[[i]] + openBracketDupe[[tmp]];
  openBracketDupe[[tmp]] = 0;,
  {i, posClose}];

changeOpen = 
  Cases[Range[[email protected]@charCode]  doubleOpenBracket, [email protected]];
changeClosed = 
  Cases[Range[[email protected]@charCode]  doubleCloseBracket, 
   [email protected]];
charCode[[changeOpen]] = ToCharacterCode["\[LeftDoubleBracket]"];
charCode[[changeClosed]] = ToCharacterCode["\[RightDoubleBracket]"];
[email protected]
 Delete[[email protected], 
  List /@ (Riffle[changeOpen, changeClosed] + 1)]

Ответ 3

Вот моя попытка. Вставляемый код ASCII довольно нечитабелен из-за наличия специальных символов, поэтому я сначала предоставляю изображение того, как он выглядит в MMA.

В основном, это так: открывающие скобки всегда однозначно идентифицируются как одиночные или двойные. Проблема заключается в закрывающих скобках. В открываемых скобках всегда есть строка с символами-содержать-без-скобки + [или [[. Невозможно иметь либо [после [[или наоборот без других символов между ними (по крайней мере, не в коде без ошибок).

Итак, мы используем это как крючок и начать искать для некоторых пар совпадающих скобок, а именно те, которые не имеют каких-либо других скобок между ними. Так как мы знаем, типа, либо "[...]" или "[[...]]", мы можем заменить последние из них с символами двойного кронштейна и бывшим один с неиспользованными символами (я использую смайлики). Это делается для того, чтобы они больше не играли роли в следующей итерации процесса сопоставления шаблонов.

Мы повторяем, пока все скобки не обработаны, и, наконец, смайлики снова преобразуются в отдельные скобки.

Вы видите, что объяснение принимает символы нравов, чем код, -).

Ascii:

s = "f @ g[hh[[i[[jj[2], k[[1, m[[1, n[2]]]]]]]]]] // z";

myRep[s_String] :=
 StringReplace[s,
  {
   Longest[y : Except["[" | "]"] ..] ~~ "[" ~~ 
     Longest[x : Except["[" | "]"] ..] ~~ "]" :> 
    y <> "\[HappySmiley]" <> x <> "\[SadSmiley]",
   Longest[y : Except["[" | "]"] ..] ~~ "[" ~~ Whitespace ... ~~ "[" ~~
      Longest[x : Except["[" | "]"] ..] ~~ "]" ~~ Whitespace ... ~~ 
     "]" :> y <> "\[LeftDoubleBracket]" <> x <> "\[RightDoubleBracket]"
   }
  ]

StringReplace[FixedPoint[myRep, s], {"\[HappySmiley]" -> "[","\[SadSmiley]" -> "]"}]

О, а часть Whitespace состоит в том, что в Mathematica двойные скобки не должны быть рядом друг с другом. a[ [1] ] так же легален, как a[[1]].

Ответ 4

Для этого вам нужен стек; там нет способа сделать это правильно, используя регулярные выражения.

Вам нужно распознать [[, а также глубину этих скобок и сопоставить их с ]], который имеет ту же глубину. (Стеки делают это очень красиво. Пока они не переполняются: P)

Без использования какого-либо счетчика это невозможно. Без определенной максимальной глубины невозможно представить это с помощью автоматов конечного состояния, поэтому это невозможно сделать с регулярным выражением.

Примечание: здесь приведен пример строки, которая не будет корректно проанализирована регулярным выражением:

[1+[[2+3]*4]] = 21

Это будет превращено в

[1 + 2 + 3] * 4 = 24

Вот некоторый java-подобный псевдокод:

public String minimizeBrackets(String input){
    Stack s = new Stack();
    boolean prevWasPopped = false;
    for(char c : input){
        if(c=='['){
            s.push(i);
            prevWasPopped = false;
        }
        else if(c==']'){
            //if the previous step was to pop a '[', then we have two in a row, so delete an open/close pair
            if(prevWasPopped){
                input.setChar(i, " ");
                input.setChar(s.pop(), " ");
            }
            else s.pop();
            prevWasPopped = true;
        }
        else prevWasPopped = false;
    }
    input = input.stripSpaces();
    return input;
}

Обратите внимание, что я немного обманул, просто превратив их в пробелы, а затем удалив пробелы... это НЕ будет делать то, что я рекламировал, он уничтожит все пробелы в исходной строке. Вы можете просто занести в журнал все местоположения, а не изменять их в пространстве, а затем скопировать поверх исходной строки без зарегистрированных мест.

Также обратите внимание, что я не проверял состояние стека в конце. Предполагается, что он пуст, поскольку предполагается, что каждый символ [ во входной строке имеет свой уникальный символ ] и наоборот. Если стек выкидывает "вы пытались вскрыть меня, когда я пуст", исключение в любой момент или не пусто в конце прогона, вы знаете, что ваша строка не была правильно сформирована.

Ответ 5

Другие ответы сделали это спорным, я думаю, но здесь больше Mathematica-идиоматическая версия первого решения yoda. Для достаточно длинной строки некоторые части могут быть немного более эффективными, кроме того.

str = "f @ g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]] // z";
charCode = [email protected];
openBracket = [email protected][charCode == 91];
closeBracket = [email protected][charCode == 93];
doubleOpenBracket = openBracket [email protected];
posClose = [email protected][closeBracket, -1, {1}];
doubleCloseBracket = 0*openBracket;
openBracketDupe = openBracket + doubleOpenBracket;
Do[
 tmp = [email protected][[email protected]*[email protected][[1 ;; i]], 0];
 doubleCloseBracket[[i - 1]] = 
  closeBracket[[i]] + openBracketDupe[[tmp]];
 openBracketDupe[[tmp]] = 0, {i, posClose}]
counter = [email protected]@charCode;
changeOpen = DeleteCases[doubleOpenBracket*counter, 0];
changeClosed = DeleteCases[doubleCloseBracket*counter, 0];
charCode[[changeOpen]] = [email protected]["\[LeftDoubleBracket]"];
charCode[[changeClosed]] = 
  [email protected]["\[RightDoubleBracket]"];
[email protected][charCode, List /@ [email protected]{1 + changeOpen, 1 + changeClosed}]

Этот способ установки "tmp" может быть МЕНЬЕ эффективным, но я думаю, что это интересно.

Ответ 6

Edit

tl; dr версия:

Я нахожусь в пути для непреднамеренного решения базовой проблемы, но регулярные выражения не могут считать скобки, поэтому используйте реализацию стека.

Более длинная версия:

Мои уважаемые коллеги правильны, лучший способ подойти к этой проблеме - реализация стека. Регулярные выражения могут изменять [[ и ]] в [ и ] соответственно, если в строке есть такое же число [[, что и число ]], однако, если вся точка упражнение - использовать текст в соответствии с [], тогда регулярное выражение не способ. Регулярные выражения не могут считать скобки, логика вложенности слишком сложна для простого регулярного выражения для учета. Таким образом, в двух словах я считаю, что регулярные выражения могут использоваться для решения основного требования, которое заключалось в том, чтобы сменить соответствие [[]] на соответствие [], однако вы действительно должны использовать стек, потому что это позволяет легче манипулировать результирующей строкой.

И извините, я полностью пропустил тег математики! Я оставлю свой ответ здесь, хотя на всякий случай кто-то взволнован и прыгает с пистолета, как я.

Редактировать конец

Регулярное выражение, использующее неохотные кванторы, должно быть в состоянии постепенно определять, где токены [[ и ]] находятся в строке, и убедитесь, что совпадения выполняются только в том случае, если число [[ равно числу ]].

Требуемое регулярное выражение будет по линии [[{1}?(?!]])*?]]{1}?, которое на простом английском языке:

• [[{1}?, прогрессируйте по одному символу за раз от начала строки до тех пор, пока не встретится один экземпляр [[
• (?!]])*?, если существуют какие-либо символы, которые не соответствуют ]], проедьте их по одному за раз
• ]]{1}? соответствуют закрывающей скобке

Чтобы сменить двойные квадратные скобки в однострочные скобки, определите группы внутри регулярного выражения, добавив скобки вокруг первой и третьей частиц:

([[{1}?)(?!]])*?(]]{1}?)

Это позволяет вам выбрать токены [[ и ]], а затем заменить их на [ или ].

Ответ 7

Я могу предложить тяжелый подход (не слишком элегантный). Ниже представлена ​​моя реализация парсера Mathematica с голой костью (он будет работать только для строк, содержащих Fullform кода, с возможным исключением для двойных скобок - который я буду использовать здесь) на основе довольно общей функциональности синтаксического анализа ширины, Я разработал в основном для реализации HTML-парсера:

ClearAll[listSplit, reconstructIntervals, groupElements, 
groupPositions, processPosList, groupElementsNested];

listSplit[x_List, lengthlist_List, headlist_List] := 
  MapThread[#1 @@ Take[x, #2] &, {headlist, 
    Transpose[{Most[#] + 1, Rest[#]} &[
      FoldList[Plus, 0, lengthlist]]]}];

reconstructIntervals[listlen_Integer, ints_List] := 
  Module[{missed, startint, lastint},
    startint  = If[ints[[1, 1]] == 1, {}, {1, ints[[1, 1]] - 1}];
    lastint = 
       If[ints[[-1, -1]] == listlen, {}, {ints[[-1, -1]] + 1, listlen}];
    missed = 
      Map[If[#[[2, 1]] - #[[1, 2]] > 1, {#[[1, 2]] + 1, #[[2, 1]] - 1}, {}] &, 
      Partition[ints, 2, 1]];
    missed = Join[missed, {lastint}];
    Prepend[Flatten[Transpose[{ints, missed}], 1], startint]];

groupElements[lst_List, poslist_List, headlist_List] /; 
 And[OrderedQ[Flatten[Sort[poslist]]], Length[headlist] == Length[poslist]] := 
  Module[{totalheadlist, allints, llist},
    totalheadlist = 
     Append[Flatten[Transpose[{Array[Sequence &, {Length[headlist]}], headlist}], 1], Sequence];
  allints = reconstructIntervals[Length[lst], poslist];
  llist = Map[If[# === {}, 0, 1 - Subtract @@ #] &, allints];
  listSplit[lst, llist, totalheadlist]];

  (* To work on general heads, we need this *)

groupElements[h_[x__], poslist_List, headlist_List] := 
   h[Sequence @@ groupElements[{x}, poslist, headlist]];

(* If we have a single head *)
groupElements[expr_, poslist_List, head_] := 
    groupElements[expr, poslist, Table[head, {Length[poslist]}]];


groupPositions[plist_List] :=
     Reap[Sow[Last[#], {Most[#]}] & /@ plist, _, List][[2]];


processPosList[{openlist_List, closelist_List}] :=
   Module[{opengroup, closegroup, poslist},
    {opengroup, closegroup} = groupPositions /@ {openlist, closelist} ;
    poslist =  Transpose[Transpose[Sort[#]] & /@ {opengroup, closegroup}];
    If[UnsameQ @@ poslist[[1]],
       Return[(Print["Unmatched lists!", {openlist, closelist}]; {})],
       poslist = Transpose[{poslist[[1, 1]], Transpose /@ Transpose[poslist[[2]]]}]
    ]
];

groupElementsNested[nested_, {openposlist_List, closeposlist_List}, head_] /; Head[head] =!= List := 
 Fold[
  Function[{x, y}, 
    MapAt[groupElements[#, y[[2]], head] &, x, {y[[1]]}]], 
  nested, 
  Sort[processPosList[{openposlist, closeposlist}], 
   Length[#2[[1]]] < Length[#1[[1]]] &]];

ClearAll[parse, parsedToCode, tokenize, Bracket ];

(* "tokenize" our string *)
tokenize[code_String] := 
 Module[{n = 0, tokenrules},
   tokenrules = {"[" :> {"Open", ++n}, "]" :> {"Close", n--}, 
       Whitespace | "" ~~ "," ~~ Whitespace | ""};
   DeleteCases[StringSplit[code, tokenrules], "", Infinity]];

(* parses the "tokenized" string in the breadth-first manner starting 
   with the outermost brackets, using Fold and  groupElementsNested*)

parse[preparsed_] := 
  Module[{maxdepth = Max[Cases[preparsed, _Integer, Infinity]], 
   popenlist, parsed, bracketPositions},
   bracketPositions[expr_, brdepth_Integer] := {Position[expr, {"Open", brdepth}], 
   Position[expr, {"Close", brdepth}]};  
   parsed = Fold[groupElementsNested[#1, bracketPositions[#1, #2], Bracket] &,
               preparsed, Range[maxdepth]];
   parsed =  DeleteCases[parsed, {"Open" | "Close", _}, Infinity];
   parsed = parsed //. h_[x___, y_, Bracket[z___], t___] :> h[x, y[z], t]];

 (* convert our parsed expression into a code that Mathematica can execute *)
 parsedToCode[parsed_] :=
 Module[{myHold},
   SetAttributes[myHold, HoldAll];   
   Hold[Evaluate[
     MapAll[# //. x_String :> ToExpression[x, InputForm, myHold] &, parsed] /.
      HoldPattern[Sequence[x__][y__]] :> x[y]]] //. myHold[x___] :> x

 ];

(обратите внимание на использование MapAll в последней функции). Теперь вот как вы можете его использовать:)

In[27]:= parsed = parse[tokenize["f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]"]]

Out[27]= {"f"["g"["h"[Bracket[
 "i"[Bracket["j"["2"], 
   "k"[Bracket["1", "m"[Bracket["1", "n"["2"]]]]]]]]]]]}

In[28]:= parsed //. a_[Bracket[b__]] :> "Part"[a, b]


Out[28]= {"f"["g"["Part"["h", 
"Part"["i", "j"["2"], 
 "Part"["k", "1", "Part"["m", "1", "n"["2"]]]]]]]}

Теперь вы можете использовать parseToCode:

In[35]:= parsedToCode[parsed//.a_[Bracket[b__]]:>"Part"[a,b]]//FullForm

Out[35]//FullForm= Hold[List[f[g[Part[h,Part[i,j[2],Part[k,1,Part[m,1,n[2]]]]]]]]]

ИЗМЕНИТЬ

Вот дополнение, необходимое для замены только символа:

Clear[stringify, part, parsedToString];
stringify[x_String] := x;
stringify[part[open_, x___, close_]] := 
   part[open, Sequence @@ Riffle[Map[stringify, {x}], ","], close];
stringify[f_String[x___]] := {f, "[",Sequence @@ Riffle[Map[stringify, {x}], ","], "]"};

parsedToString[parsed_] := 
 StringJoin @@ Flatten[Apply[stringify, 
  parsed //. Bracket[x__] :> part["yourOpenChar", x, "yourCloseChar"]] //. 
    part[x__] :> x];

Вот как мы можем его использовать:

In[70]:= parsedToString[parsed]

Out[70]= "f[g[h[yourOpenChari[yourOpenCharj[2],k[yourOpenChar1,m[\
  yourOpenChar1,n[2]yourCloseChar]yourCloseChar]yourCloseChar]\
   yourCloseChar]]]"

Ответ 8

Отредактировано (там была ошибка)

Это слишком наивно?

doubleB[x_String] :=
  StringReplace[
   [email protected]@
     ToExpression["Hold[" <> x <> "]"], 
  {"Hold[" -> "", RegularExpression["\]\)$"] -> "\)"}];

doubleB["f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]"]
[email protected]["f[g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]]]"]

- >

Просто пытаюсь использовать собственный парсер Mma...

Ответ 9

Здесь еще один с сопоставлением с образцом, вероятно похожий на то, что делает Sjoerd C. de Vries, но он работает со структурой вложенного списка, которая создается сначала, процедурно:

FirstStringPosition[s_String, pat_] :=
    Module[{f = StringPosition[s, pat, 1]},
      If[[email protected] > 0, [email protected]@f, Infinity]
    ];
FirstStringPosition[s_String, ""] = Infinity;

$TokenizeNestedBracePairsBraces = {"[" -> "]", "{" -> "}", "(" -> ")"(*,
  "<"\[Rule]">"*)};
(*nest substrings based on parentheses {([*) (* TODO consider something like http://stackoverflow.com/a/5784082/524504, though non procedural potentially slower*)
TokenizeNestedBracePairs[x_String, closeparen_String] :=
    Module[{opString, cpString, op, cp, result = {}, innerResult,
      rest = x},

      While[rest != "",

        op = FirstStringPosition[rest,
          [email protected]$TokenizeNestedBracePairsBraces];
        cp = FirstStringPosition[rest, closeparen];

        Assert[op > 0 && cp > 0];

        Which[
        (*has opening parenthesis*)
          op < cp

          ,(*find next block of [] *)
          result~AppendTo~StringTake[rest, op - 1];
          opString = StringTake[rest, {op}];
          cpString = opString /. $TokenizeNestedBracePairsBraces;
          rest = StringTake[rest, {op + 1, -1}];

          {innerResult, rest} = TokenizeNestedBracePairs[rest, cpString];
          rest = StringDrop[rest, 1];

          result~AppendTo~{opString, innerResult, cpString};

          , cp < Infinity
          ,(*found searched closing parenthesis and no further opening one \
earlier*)
          result~AppendTo~StringTake[rest, cp - 1];
          rest = StringTake[rest, {cp, -1}];
          [email protected]{result, rest}

          , True
          ,(*done*)
          [email protected]{result~Append~rest, ""}
        ]
      ]
    ];
(* TODO might want to get rid of empty strings "", { generated here:
[email protected]"f @ g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]] \
// z"
*)

TokenizeNestedBracePairs[s_String] :=
    [email protected][s, ""]

и с этими определениями тогда

StringJoin @@ 
 Flatten[[email protected]
    "f @ g[h[[i[[j[2], k[[1, m[[1, n[2]]]]]]]]]] // z" //. {"[", {"", \
{"[", Longest[x___], "]"}, ""}, "]"} :> {"\[LeftDoubleBracket]", {x}, 
     "\[RightDoubleBracket]"}]

дает