Creating Linked Lists in Python

Tim Chase python.list at tim.thechases.com
Sat Mar 21 14:38:41 CET 2009


> For example, this means that there can be a start node supposedly.
> Having a value of 0. It is pointing to node 1 with the value of "a"
> and to node 2 with the value of "b". Trying to make something like an
> NFA. Where id be changing regular expressions to NFAs.

John has already pointed out the preconception problems of 
"linked list".

In the past, I've done NFA with a state machine:

   (STATE_A,
    STATE_B,
    STATE_C,
    STATE_D,
    ) = range(4)

   transitions = {
     # values are tuples of (newstate, transition_function)
     STATE_A: [
       (STATE_B, lambda x: x > 5),
       (STATE_C, lambda x: x > 10),
       (STATE_D, lambda x: x > 100),
       ],
     STATE_B: [
       (STATE_A, lambda x: x < 5),
       (STATE_C, lambda x: x > 10),
       ],
     STATE_C: [
       (STATE_B, lambda x: x < 10),
       (STATE_D, lambda x: x > 100),
       ],
     STATE_D: [],
     }

You may have to carry around extra information regarding your 
state, and tweak accordingly.  Instead of tuples of (newstate, 
transition_function), you could just use transition functions 
that return the new state, or None if they're not satisfied.

You then simply maintain your current state, and then test your 
incoming stream of tokens/data against your transition function 
to see if you can transition to the resulting state.  Depending 
on whether you need back-tracking, you'll want to gather all the 
possible results, or otherwise may just settle for the first 
available transition to a new state.

-tkc







More information about the Python-list mailing list