Creating Linked Lists in Python

grocery_stocker cdalten at gmail.com
Sat Mar 21 16:47:01 CET 2009


On Mar 21, 6:38 am, Tim Chase <python.l... at tim.thechases.com> wrote:
> > 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.
>

And if you don't mind me asking. How do you invoke lambda from
transitions?



More information about the Python-list mailing list