Parse it back-to-front
Take off the zip, if it exists plus any spaces and comma
then the state, if it exists, and any space/comma before it
then look at the next comma-separated section.
If it exists, take it and remove parenthetical text as the city.
What's left is the address...
This seems to meet your requirements.

You can also vet the state by word, abbrev, or start-of-word.
You can vet the city from a larger list, as well as lookup city by
zip, given the right list.