CODEWITHSUNDEEP
c#algorithmreplace
Ankesh
Ankesh

Reputation: 4885

Recursive string replacement in C#

Senario

I have an object Keyword -> It has a name and a Value (string)

A keyword cannot contain itsSelf... but can contain other keywords example

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

where K2,K3,K4 are keywords.....

Just Relpacing them with their values works but here a catch that i am facing

Examlple :

K3= "%K2%"

K2= "%K4%"

K4="%K2%"

Now if i start replacing there will a infinite loop as K2 gives K4 and Vice Versa...

I wish to avoid such problem

But it is required that i allow the uesr to nest other keyword... how could i check "While adding if the DeadLock Occur" i will display invalid... Should i use a HashTable or what... Some Code Direction would be nice...

Upvotes: 4

Views: 2353

Answers (5)

Eric Lippert
Eric Lippert

Reputation: 660138

From your comment:

I want to be able to take a Context Free Grammar and run an analyzer on it that determines if there is any "infinite cycle".

That is easily done. First off, let's clearly define a "context free grammar". A CFG is a substitution system which has "terminal" and "non-terminal" symbols. Terminals are things which are "done"; non-terminals are replaced with a sequence of terminal and non-terminal symbols.

In my examples, non-terminals will be in UPPERCASE and terminals will be in lowercase. Substitution rules will be written as "NONTERMINAL : substituted symbols". So an example of a CFG is:

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

So if we start with SENTENCE then we can make substitutions:

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

and we have no more non-terminals, so we're done.

CFGs can have cycles:

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

And now we do productions:

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

This one can eventually stop but it can go forever also. Of course you can define CFGs that must go forever; if there had been no production "TERM : 1" then this one would go forever without finding a valid sequence of only terminals.

So how do you determine if there are any productions that can run forever?

What you do is make a directed graph data structure. Make all the non-terminals into nodes in the graph. Then add an edge for every production rule that has a non-terminal on the right-hand side. So for our first example, we'd have the graph:

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

In the second example we'd have the graph:

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

If the graph contains a cycle that is reachable from the start symbol then the grammar contains productions which can be expanded forever. If it does not, then it cannot.

So now all you have to do is build a cycle detector, and that's an easy problem in graph analysis. If there are no cycles, or if the only cycles are not reachable from the start symbol, then the grammar is good.

Upvotes: 19

paxdiablo
paxdiablo

Reputation: 881563

For a start, I wouldn't actually do this recursively. There's a perfectly good iterative solution that won't blow out your stack:

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

That's the basic construct. No chance of blowing out stack space with infinite looping substitutions. However, it still has the same problem as the recursive solution in that it will loop infinitely where:

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

or even the simpler:

kw1="%kw1%"

The best way to stop that is to simply provide an arbitrary limit on the number of substitutions allowed (and preferably make it configurable in case there's a real need for a large number).

You can make this a arbitrarily large number since there's no risk of stack blowout, and the changes needed to the code above are as simple as:

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

Upvotes: 2

chopikadze
chopikadze

Reputation: 4239

The idea is to implement something like "state" machine:

  1. Look for first occurrence of any key string
  2. Make replacement there
  3. Look for first occurence of any key string, starting from previous occurence (from step 2)
  4. Make replacement there
  5. etc.
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);
    }
}

Upvotes: 0

Argalatyr
Argalatyr

Reputation: 4659

Enforce unique keywords. They could be nested but not equal.

Since it would be hard to have deeply nested strings, you could enforce a limit on recursion levels.

Upvotes: 0

Matthias
Matthias

Reputation: 16209

Each time you're going to replace a keyword, add it to a collection. If, at some point, that collection contains the keyword more than one time, it is recursive. Then you can throw an exception or just skip it.

Upvotes: 0

Related Questions