You should use a parser to find the head (verb) of the predicate of the sentence.
In case you assume that the original sentence is grammatically correct you can overcome the agreement issue (don't vs. doesn't) by relying on the properties of the original head-verb.
If it's an auxiliary1, replace it with its negative counterpart (was > wasn't, will > won't, have > haven't, etc.). If it's not an auxiliary, add the correct negative form of supportive-do: didn't if the head-verb is in the past form (i.e., walked), don't if it is in the non-3rd-person-singular present form (i.e., think), and doesn't if in the 3rd-person-singular present form (i.e., runs). Immediately following the supportive-do use the base form of the original head-verb (walk, think, run).
A harder issue to solve is what ShaiCohen is discussing in his answer. Notice that you don't always have to replace these items. There are many cases where you shouldn't. For example: I am the one who saw someone at the office > I'm not the one who saw someone at the office.
Have a look at the Contextors API.
1 Be careful of lexical verbs which look like auxiliaries. She has a dog...