algorithm for sorting functional expressions

chrisguest at gmail.com chrisguest at gmail.com
Mon Dec 4 01:50:32 EST 2006


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. 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.




More information about the Python-list mailing list