Как эта замена регулярного выражения перевернуть строку?

Это четвертая часть в серии образовательных регулярных выражений. Он показывает, как сочетание вложенной ссылки (см. Как это регулярное выражение находит треугольные числа?) Для "подсчета" в утверждениях (см. Как мы можем сопоставить ^n b^n с регулярным выражением Java?) Может быть использовано для обращения строки, Программно сгенерированный шаблон использует абстракции мета-шаблона (см.: Как это регулярное выражение Java обнаруживает палиндромы?). Впервые в серии эти методы используются для замены вместо сопоставления всей строки.

Предоставляются полные рабочие реализации Java и C#. Вдохновляющие цитаты включены.

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

Хотя это все еще не очень хорошая идея, по крайней мере, теперь мы знаем, что это возможно, потому что есть один способ сделать это:

C# ( также на ideone.com) 

using System;
using System.Text.RegularExpressions;

public class TwoDollarReversal {    
public static void Main() {
   string REVERSE = 
      @"(?sx) . grab$2"
         .Replace("grab$2",
            ForEachDotBehind(
               AssertSuffix(@"((.) \1?)")
            )
         );
   Console.WriteLine(
      Regex.Replace(
         @"nietsniE treblA --
         hguone llew ti dnatsrednu t'nod uoy ,ylpmis ti nialpxe t'nac uoy fI",

         REVERSE, "$2"
      )
   );
   // If you can't explain it simply, you don't understand it well enough
   // -- Albert Einstein
}      
// performs an assertion for each dot behind current position
static string ForEachDotBehind(string assertion) {
   return "(?<=(?:.assertion)*)".Replace("assertion", assertion);
}
// asserts that the suffix of the string matches a given pattern
static string AssertSuffix(string pattern) {
   return "(?=.*$(?<=pattern))".Replace("pattern", pattern);
}

}

Java ( также на ideone.com) 

class TwoDollarReversal {

public static void main(String[] args) {
   String REVERSE =
      "(?sx) . grab$2"
         .replace("grab$2",
            forEachDotBehind(
               assertSuffix("((.) \\1?)")
            )
         );

   System.out.println(
      "taerG eht rednaxelA --\nyrt lliw ohw mih ot elbissopmi gnihton si erehT"
         .replaceAll(REVERSE, "$2")
   );
   // There is nothing impossible to him who will try
   // -- Alexander the Great"
}

static String forEachDotBehind(String assertion) {
   return "(?<=^(?:.assertion)*?)".replace("assertion", assertion);
}
static String assertSuffix(String pattern) {
   return "(?<=(?=^.*?pattern$).*)".replace("pattern", pattern);
}

}

Как в версиях C#, так и в Java, похоже, используется один и тот же общий алгоритм, с небольшими изменениями только в абстрактных деталях реализации.

Очевидно, что это не самый лучший, самый простой и эффективный способ перевернуть строку. Тем не менее, в интересах изучения регулярных выражений; как осмыслить шаблоны; как двигатель работает, чтобы соответствовать им; как соединить разные части, чтобы построить то, что мы хотим; как сделать это так, чтобы его можно было читать и поддерживать; и просто ради радости от изучения чего-то нового, можем ли мы объяснить, как это работает?

Приложение: шпаргалка!

Это краткое описание основных конструкций регулярных выражений:

  • (?sx) это встроенные модификаторы флага. s включает режим "однострочный", позволяющий точке соответствовать любому символу (включая символы новой строки). x включает режим свободного пробела, где неэкранированные пробелы игнорируются (и # можно использовать для комментариев).
  • ^ а также $ являются якорями начала и конца строки.
  • ? как спецификатор повторения обозначает необязательный (то есть ноль или один из). В качестве квантификатора повторения, например, в .*? это означает, что * (то есть ноль или более) повторение неохотно / не жадный.
  • (…) используются для группировки. (?:…) это группа без захвата. Группа захвата сохраняет строку, которой она соответствует; это позволяет назад / вперед / вложенные ссылки (например, \1), замена замены (например, $2), так далее.
  • (?=…) позитивный взгляд; он смотрит вправо, чтобы утверждать, что есть совпадение данного образца. (?<=…) это позитивный взгляд сзади; это смотрит налево.

Языковые ссылки / дополнительные ресурсы

Источник

2 ответа

обзор

На высоком уровне шаблон соответствует любому одному символу ., но дополнительно выполняет grab$2 действие, которое захватывает "сопряжение" обращения символа, который был сопоставлен с группой 2. Этот захват выполняется путем создания суффикса входной строки, длина которой соответствует длине префикса до текущей позиции. Мы делаем это, применяя assertSuffix на шаблоне, который увеличивает суффикс на один символ, повторяя это один раз forEachDotBehind, Группа 1 фиксирует этот суффикс. Первый символ этого суффикса, захваченный в группе 2, является "обратным" "сопряжением" для сопоставляемого символа.

Таким образом, замена каждого совпавшего символа его "сопряжением" имеет эффект обращения строки.

Как это работает: более простой пример

Чтобы лучше понять, как работает шаблон регулярных выражений, давайте сначала применим его к более простому вводу. Кроме того, для нашего шаблона замены мы просто "выбросим" все захваченные строки, чтобы лучше понять, что происходит. Вот версия Java:

System.out.println(
    "123456789"
        .replaceAll(REVERSE, "[$0; $1; $2]\n")
);

Вышеуказанные отпечатки ( как видно на ideone.com):

[1; 9; 9]
[2; 89; 8]
[3; 789; 7]
[4; 6789; 6]
[5; 56789; 5]
[6; 456789; 4]
[7; 3456789; 3]
[8; 23456789; 2]
[9; 123456789; 1]

Так, например, [3; 789; 7] означает, что точка соответствует 3 (захвачено в группе 0), соответствующий суффикс 789 (группа 1), чей первый символ 7 (группа 2). Обратите внимание, что 7 является 3"помощник".

                   current position after
                      the dot matched 3
                              ↓        ________
                      1  2 [3] 4  5  6 (7) 8  9
                      \______/         \______/
                       3 dots        corresponding
                       behind      suffix of length 3

Обратите внимание, что "помощник" персонажа может быть справа или слева. Персонаж может даже быть его собственным "помощником".

Как построен суффикс: вложенная ссылка

Шаблон, отвечающий за сопоставление и построение растущего суффикса, выглядит следующим образом:

    ((.) \1?)
    |\_/    |
    | 2     |       "suffix := (.) + suffix
    |_______|                    or just (.) if there's no suffix"
        1

Обратите внимание, что в определении группы 1 есть ссылка на себя (с \1), хотя это необязательно (с ?). Необязательная часть предоставляет "базовый случай", способ сопоставления группы без ссылки на себя. Это необходимо, потому что попытка сопоставить ссылку на группу всегда терпит неудачу, когда группа еще ничего не захватила.

Как только группа 1 захватывает что-то, дополнительная часть никогда не выполняется в нашей установке, так как суффикс, который мы только что захватили в прошлый раз, все еще будет там на этот раз, и мы всегда можем добавить другой символ к началу этого суффикса с помощью (.), Этот предваряющий персонаж попадает в группу 2.

Таким образом, этот шаблон пытается увеличить суффикс на одну точку. Повторяя это один раз forEachDotBehind следовательно, приведет к суффиксу, длина которого точно равна длине префикса до нашей текущей позиции.

Как assertSuffix а также forEachDotBehind работа: мета-паттерн абстракции

Обратите внимание, что до сих пор мы рассматривали assertSuffix а также forEachDotBehind как черные ящики. Фактически, оставить это обсуждение насовсем - это преднамеренный акт: имена и краткая документация предполагают, ЧТО они делают, и этой информации было достаточно, чтобы мы могли написать и прочитать наш REVERSE шаблон!

При ближайшем рассмотрении мы увидим, что реализации этих абстракций в Java и C# немного отличаются. Это связано с различиями между двумя двигателями регулярных выражений.

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

  • AssertSuffix(pattern) := (?=.*$(?<=pattern))То есть мы используем lookahead, чтобы пройти весь путь до конца строки, а затем используем вложенный lookbehind, чтобы сопоставить шаблон с суффиксом.
  • ForEachDotBehind(assertion) := (?<=(?:.assertion)*)т.е. мы просто совпадаем .* в виде сзади, помечая утверждение вместе с точкой внутри не захватывающей группы.

Поскольку Java официально не поддерживает просмотр задних частей бесконечной длины (но он все равно работает при определенных обстоятельствах), его аналог немного более неловкий:

  • assertSuffix(pattern) := (?<=(?=^.*?pattern$).*), т.е. мы используем lookbehind, чтобы пройти весь путь до начала строки, затем используем вложенный lookahead для сопоставления всей строки, добавляя шаблон суффикса с помощью .*? неохотно подбирать какой-то неуместный префикс.
  • forEachDotBehind(assertion) := (?<=^(?:.assertion)*?)т.е. мы используем закрепленный вид сзади с неохотным повторением, т.е. ^.*? (а также пометить утверждение вместе с точкой внутри не захватывающей группы).

Следует отметить, что, хотя реализация этих мета-шаблонов на C# не работает в Java, реализация Java работает в C# ( см. На ideone.com). Таким образом, в действительности нет необходимости иметь разные реализации для C# и Java, но реализация C# сознательно использовала преимущества более мощной поддержки.NET regex engine для поддержки более естественного выражения шаблонов.

Таким образом, мы показали преимущества использования абстракций мета-паттернов:

  • Мы можем независимо разрабатывать, исследовать, тестировать, оптимизировать и т. Д. Эти реализации мета-шаблонов, возможно, используя преимущества специфических для ароматов функций для дополнительной производительности и / или читабельности.
  • После того, как эти строительные блоки разработаны и хорошо протестированы, мы можем просто использовать их как части более крупного шаблона, что позволяет нам выражать идеи на более высоких уровнях для более удобочитаемых, более удобных в обслуживании и более портативных решений.
  • Мета-шаблоны способствуют повторному использованию, а программная генерация означает, что дублирования меньше

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

Смотрите также

Заключительные мысли

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

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

Менее ощутимо, возможно, статья также показывает решимость, необходимую для решения проблемы, которая на первый взгляд может показаться трудной (или даже "невозможной"). Возможно, это также показывает ясность мысли, которая приходит с более глубоким пониманием предмета, результатом многочисленных исследований и тяжелой работы.

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

Источник

использование регулярного выражения для реверсирования не так сложно, как некоторые думают - просто сделайте это по степени двойки, с несколькими циклами, которые по сути являются перефразированием типичного трюка с реверсированием битов, применяемого к произвольным строкам, поэтому необходимое количество циклов цикла - это просто целое число log-base-2 длины строки вместо одного символа за раз:

       LANG="en_US.UTF-8" echo '1234567890123\nABCDefghi\n코요태이하픽에' | 

       LANG="en_US.UTF-8" gawk -e '

   # gawk profile, created Sun Dec  4 17:22:55 2022

   # Functions, listed alphabetically

 5  function _____(__,___,_,____,______)
    {
 5      if ((___=(_=_<_)<+___ ? +___ : length(__))<=(++_+_)) {

            return substr((__)__,___,___*=_<=___)
        }

16      do { ++____ } while ((_+=_)<___)

 5      if (___<_) { # 5

 5        ______ = (___-(_=(_^!_+_^!_)^—____))<=_^!_ \
                   ?       substr(__,___) \
                   : _____(substr(__,_+!!_),___-_)

 5            __ = substr(__,!!_,___=_)
         }
 5       ___ = "."
11       while (____--) {

11            sub("$", "\3", __)
             gsub("(^|" (___)  (")")___, "\3&\5&", __)
             gsub("\5|(^|" (___) ")\3("(___)"|$)", "",__)

11            ___=(___)___
         }
 5       return (______)__
      }

      BEGIN {
 1       OFS = "\f\r\t"
      }

 3    ($++NF = _____($!_))^_'

       1  1234567890123
    3210987654321

 2  ABCDefghi
    ihgfeDCBA

 3  코요태이하픽에
    에픽하이태요코
Источник
Другие вопросы по тегам