Like Token Replace, but a token's replacement may itself contain more tokens. Keep
expanding until no replaceable tokens remain. Assume the rules contain no cycles. A token
with no rule is left as the literal {name}.
tokenTransform(template, rules)
Input format: template | rules, rules as space-separated name=value entries.
"{greeting}", rules greeting={hi}{name} hi=hello name=sam // → "hellosam"
"{a}", rules a={b} b=done // → "done"
This extends token-replace with one twist: a token's replacement can itself contain more tokens, needing expansion, potentially several layers deep. The scanning mechanics — find {, locate }, extract the name — stay the same. What changes is what happens once you have a token's replacement: instead of dropping it into the output as-is, treat it as itself a template that might need further expansion.
"A value that may itself contain tokens needing the same expansion" is the giveaway: expanding a template is defined in terms of expanding another template. When the scan finds a known token, recursively call the same expansion function on its replacement value, using the same rules, and append that result instead of the raw value. Nested tokens get looked up and expanded too, and their replacements' tokens, and so on, until nothing's left to expand.
Unrestricted recursion could loop forever if token A referenced B and B referenced A back. The problem guarantees no cycles, which makes recursing safe without extra cycle-detection: no rule refers back to itself, so each expansion strictly progresses toward rules with no further references.
A token with no rule stays the literal {name} — nothing to recursively expand into, so this base case is unchanged from the simpler version.
A single non-recursive pass would substitute a token's raw value once and stop — any {something} inside it would be left unresolved. The recursive call is what turns "replace once" into "expand fully."
Work is proportional to the fully expanded output's size, since every character comes from one pass of copying or one token lookup-and-recurse — no cycles guarantees this is finite. O(output length) time and space.
def token_transform(template, rules):
out = []
i = 0
while i < len(template):
if template[i] == "{":
end = template.find("}", i)
if end != -1:
name = template[i + 1:end]
if name in rules:
out.append(token_transform(rules[name], rules))
else:
out.append(template[i:end + 1])
i = end + 1
continue
out.append(template[i])
i += 1
return "".join(out)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.