Рекурсивная замена строк в C #

Question

Senario

У меня есть объект Keyword -> У него есть имя и значение (строка)

Ключевое слово не может содержать itsSelf ..., но может содержать другие ключевые слова, пример

K1 = "%K2% %K3% %K4%"

где K2, K3, K4 - ключевые слова .....

Просто переназначение их с их значениями работает, но здесь уловка, с которой я сталкиваюсь

Пример:

K3= "%K2%"

K2= "%K4%"

K4="%K2%"

Теперь, если я начну замену, будет бесконечный цикл, поскольку K2 дает K4 и наоборот ...

Я хочу избежать такой проблемы

Но требуется, чтобы я разрешил uesr вкладывать другое ключевое слово ... как я могу проверить "При добавлении, если DeadLock Occur" появится, будет отображаться неверно ... Должен ли я использовать HashTable или что ... Some Code Direction would be nice...

Answer 1

Из вашего комментария:

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

Это легко сделать. Прежде всего, давайте четко определим «контекстно-свободную грамматику». CFG - это система замещения, которая имеет «терминальные» и «нетерминальные» символы. Терминалы - это то, что «сделано»; нетерминалы заменяются последовательностью терминальных и нетерминальных символов.

В моих примерах нетерминалы будут в верхнем регистре, а терминалы будут в нижнем регистре. Правила замещения будут записаны как «НЕТЕРМИНАЛ: замещенные символы». Итак, пример CFG:

SENTENCE : SUBJECT VERB OBJECT
SUBJECT  : ARTICLE NOUN
ARTICLE  : a
ARTICLE  : the
NOUN     : can
NOUN     : man
VERB     : saw
VERB     : kicked
OBJECT   : ARTICLE NOUN

Итак, если мы начнем с SENTENCE, мы можем сделать замены:

SENTENCE
SUBJECT VERB OBJECT
ARTICLE NOUN VERB OBJECT
the NOUN VERB OBJECT
the man VERB OBJECT
the man kicked OBJECT
the man kicked ARTICLE NOUN
the man kicked the NOUN
the man kicked the can

и у нас больше нет нетерминалов, так что мы закончили.

CFG могут иметь циклы:

EQUATION : TERM = TERM
TERM     : 1
TERM     : ADDITION
ADDITION : TERM + TERM

А сейчас мы делаем постановки:

EQUATION
TERM = TERM
1 = TERM
1 = ADDITION
1 = TERM + TERM
1 = 1 + TERM
1 = 1 + 1

Этот может в конце концов остановиться, но может продолжаться и вечно. Конечно, вы можете определить CFG, которые должны идти вечно; если бы не было производственного «СРОКА: 1», то этот работал бы вечно, не найдя правильную последовательность только терминалов.

Так как же определить, есть ли какие-либо постановки, которые могут работать вечно?

То, что вы делаете, это создаете ориентированный граф структуру данных. Сделайте все нетерминалы в узлах на графике. Затем добавьте ребро для каждого производственного правила, для которого справа нет нетерминала. Итак, для нашего первого примера у нас будет график:

SENTENCE ----->  SUBJECT
  |   |          |     |
  |   |          |     |
  v   |          |     |
 VERB |          |     |   
      v          v     |
     OBJECT--->ARTICLE |
         \             v  
          ---------->NOUN

Во втором примере у нас будет график:

EQUATION --> TERM ---> ADDITION
                 <-----/

Если график содержит цикл , достижимый из начального символа , то грамматика содержит произведения, которые можно расширять навсегда. Если это не так, то не может.

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

Answer 2

Для начала я бы не стал делать это рекурсивно.Существует совершенно хорошее итеративное решение, которое не разрушит ваш стек:

def morph (string):
    while string has a substitution pattern in it:
        find first keyword in string
        replace it with value
    endwhile
    return string

Это базовая конструкция.Нет шансов выбросить пространство стека с бесконечными циклическими заменами.Тем не менее, он по-прежнему имеет ту же проблему, что и рекурсивное решение в том, что он будет зацикливаться бесконечно, где:

kw1="%kw2%"
kw2="%kw1%"

или даже проще:

kw1="%kw1%"

.Лучший способ остановить в том, что - это просто установить произвольное ограничение на количество разрешенных замен (и предпочтительно сделать его настраиваемым в случае реальной необходимости большого числа).

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

def morph (string):
    sublimit = getConfig ("subLimit")
    while string has a substitution pattern in it:
        sublimit = sublimit - 1
        if sublimit < 0:
            return some sort of error
        find first keyword in string
        replace it with value
    endwhile
    return string

Answer 3

Идея состоит в том, чтобы реализовать нечто вроде "конечного автомата":

1. Ищите первое вхождение любой ключ
2. Сделай замену там
3. Поиск первого вхождения любой строки ключа, начиная с предыдущего вхождения (с шага 2)
4. Сделай замену там
5. и т.д.

---

using System;

class Program
{
    static void Main(string[] args)
    {
        var s = "%K2% %K3% %K4%";
        var replaces = new[]
                           {
                               new[] {"%K3%", "%K2%"},
                               new[] {"%K2%", "%K4%"},
                               new[] {"%K4%", "%K2%"},
                           };

        bool wasReplaces;
        var curPos = 0;
        do
        {
            wasReplaces = false;

            string[] curReplacement = null;
            var minIndex = int.MaxValue;

            foreach (var replacement in replaces)
            {
                var index = s.IndexOf(replacement[0], curPos);
                if ((index < minIndex) && (index != -1))
                {
                    minIndex = index;
                    curReplacement = replacement;
                }
            }

            if (curReplacement != null)
            {
                s = s.Substring(0, minIndex) + curReplacement[1] + s.Substring(minIndex + curReplacement[0].Length);
                curPos = minIndex + curReplacement[0].Length + 1;
                wasReplaces = true;
            }

        } while (wasReplaces && (curPos < s.Length));

        // Should be "%K4% %K2% %K2%
        Console.WriteLine(s);
    }
}

Answer 4

Применение уникальных ключевых слов.Они могут быть вложенными, но не равными.

Поскольку было бы сложно иметь глубоко вложенные строки, вы можете установить ограничение на уровни рекурсии.

Answer 5

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