You're almost there:

    s/(\w+) ?(OR|NOT|AND|$)/\(fieldname \= '$1'\) $2/g;
[download]

should do it. But that's just for this particular example. If you want to be able to process something more complicated, I'd recommend using a parser. For instance, Parse::Recdescent, or a regular expression using (??{ }) constructs.

Abigail