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

Question

Senario

У меня есть объект Ключевое слово -> Он имеет имя и значение (строка)

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

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

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

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

Examlple:

K3= "%K2%"

K2= "%K4%"

K4="%K2%"

Теперь, если я начать заменять там будет бесконечный цикл, как К2 дает K4 и НАОБОРОТ ...

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

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

Answer 1

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

Я хочу, чтобы иметь возможность взять Conte xt Free Grammar и запустить анализатор на нем, который определяет, есть ли любой «бесконечный цикл».

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

В моих примерах, не-терминалы будут в UPPERCASE, а терминалы будут в нижнем регистре. Правила замещения будут записаны как «NONTERMINAL: замещенные символы». Так пример CFG является:

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

Так что, если мы начнем с ПРИГОВОРА, то мы можем сделать замены:

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 

и у нас нет более нетерминалы, поэтому мы сделали.

CFGs может иметь циклы:

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, что должен go forever; если бы не было никакого производства «СРОК: 1», то этот был бы навсегда, не найдя действительной последовательности только терминалов.

Итак, как вы определяете, есть ли любые производств, которые могут работать вечно?

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

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

Во втором примере мы имеем график:

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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 5

Идея заключается в том, чтобы реализовать что-то вроде «государства» машина:

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); 
    } 
}