Algorithm for storing templates and places

Question

First a quick definition :)

• Template . A string that may contain placeholders (example: "hello [name]")
• Placeholder . A substring in square brackets of a substring (example: "name" to "hello" [name] :).
• Property map - a valid object with strings as values

I need to write code that replaces placeholders (along with brackets) with the corresponding values ​​in the property map.

Example: for the following properties:

{ "name":"world", "my":"beautiful", "a":"[b]", "b":"c", "c":"my" } 

Expected results:

• "hello name" → "hello name"

• "hello [name]" → "hello world"

• "[b]" → "c"

• "[a]" → "c" (because [a] → [b] → [c])

• "[[b]]" → "my" (because [[b]] ​​-> [c] → my)

• "hello [my] [name]" → "hello beautiful world"

Answer 1

 var map = { "name":"world", "my":"beautiful", "a":"[b]", "b":"c", "c":"my" }; var str = "hello [my] [name] [[b]]"; do { var strBeforeReplace = str; for (var k in map) { if (!map.hasOwnProperty(k)) continue; var needle = "[" + k + "]"; str = str.replace(needle, map[k]); } var strChanged = str !== strBeforeReplace; } while (strChanged); document.write(str); //hello beautiful world my 

Answer 2

The answer from @chris is excellent, I just want to propose an alternative solution using regular expressions that work the other way around, i.e. they don’t look for the appearance of “placeholder versions” of all elements in the map properties, but repeatedly looking at the occurrences of the placeholder itself and substituting it with the corresponding value from the property map. This has two advantages:

• If the property map grows very large, this solution should have better performance (still for comparison).
• Placeholder and substitution work can be easily changed by adjusting the regular expression and the substitution function (this may not be a problem).

The disadvantage is, of course, that the code is a bit more complicated (partly due to the fact that JavaScript does not have a nice way of substituting regular expression matches using custom functions, so what is substituteRegExp ):

 function substituteRegExp(string, regexp, f) { // substitute all matches of regexp in string with the value // returned by f given a match and the corresponding group values var found; var lastIndex = 0; var result = ""; while (found = regexp.exec(string)) { var subst = f.apply(this, found); result += string.slice(lastIndex, found.index) + subst; lastIndex = found.index + found[0].length; } result += string.slice(lastIndex); return result; } function templateReplace(string, values) { // repeatedly substitute [key] placeholders in string by values[key] var placeholder = /\[([a-zA-Z0-9]+)\]/g; while (true) { var newString = substituteRegExp(string, placeholder, function(match, key) { return values[key]; }); if (newString == string) break; string = newString; } return string; } alert(templateReplace("hello [[b]] [my] [name]", { "name":"world", "my":"beautiful", "a":"[b]", "b":"c", "c":"my" })); // -> "hello my beautiful world" 

Update . I slightly adjusted the comparison of the two solutions (jsFiddle at http://jsfiddle.net/n8Fyv/1/ , I also used Firebug). Although the @chris solution is faster for small lines (no regular expression analysis, etc.), this solution is much better for large lines (of the order of thousands of characters). I did not compare for different sizes of the property map, but I expected even big differences there.

Theoretically, this solution has runtime O (kn), where k is the nesting depth of the placeholders and n is the string length (provided that the dictionary / hash search requires constant time), while the @chris solution is O (knm), where m - the number of elements on the property map. Of course, all this applies only to large entrances.

Answer 3

If you are familiar with the .NET String.Format , you should take a look at this JavaScript implementation . It also supports number formatting, like String.Format .

Here is an example of how to use it:

 var result = String.Format("Hello {my} {name}", map); 

However, recursive templates will require some modification.