Apply Substitutions

First ask whether applying A to B and B to C should turn A into C, because that determines whether this is a graph problem or a simple lookup. For recursive substitution, make a directed edge from a token to every token needed to expand it. Run depth-first search with three states: unseen, visiting, and resolved. Encountering visiting means a cycle such as A to B to A, so there is no finite expansion unless the specification defines a special rule. Once all dependencies resolve, build and memoize the expansion for the current token; later uses reuse it. If the requested output can grow exponentially, explain that output size itself dominates runtime and use limits or streaming if allowed. Test missing definitions, self references, multiple uses of one symbol, and a cycle. Graph traversal is O(V plus E) before accounting for constructed output, and memoization uses O(V plus E) space.