How do you expand nested placeholders in strings?

Given a map of string templates, each key is an identifier such as NAME. A template value is a string that may contain placeholders of the form %KEY%. A placeholder should be replaced with the fully expanded text of the template identified by KEY. Expansion follows references transitively: if a template contains another placeholder, expand that referenced template first. When a placeholder references a key that is not present in the map, leave the placeholder %KEY% unchanged…