algorithm for sorting functional expressions

[Christian Stapfer]

<chrisguest at gmail.com> wrote in message 
news:1165215032.749560.171530 at 16g2000cwy.googlegroups.com...
>I am trying to write some code that will take a list of functional
> expressions, and order them so that those with primitive terms appear
> at the beginning of the list and those that are defined by other terms
> appear last.
>
> eg:
> getSortedEquations(['b = w + z','a = z - y','w = 2*z + v','z = e +
> f','y = p + l']) =
> ['w = 2*z + v', 'z = e + f', 'y = p + l', 'b = w + z', 'a = z - y']
>
> It is easy enough to tokenise each of the equations and produce a list
> like:
> ['b', ['w','z']], ['a': ['z','y']], ['w':'z','v'] , ['z', ['e','f']],
> ['y',['p','l']]
>
> But I'd like to find an algorithm that can handle the sorting problem.
>
> So I suspect that this is a common problem for those familiar with
> partially ordered sets or directed graphs.

Right.

> I'm wondering if anyone else
> is familiar with this problem and knows an efficient algorithm that
> will solve it. It would be good if any such algorithm would be able to
> check for circular definitions in the input.

Read http://en.wikipedia.org/wiki/Topological_sorting
or just search for "topological sorting" on the net.

Regards,
Christian