Initially, you might think that to be a relatively simple challenge - but spend a few minutes reading the United States Postal Service Pub 28 (Postal Addressing Standards) - and you'll appreciate some of the nuances of the problem. In particular, see the examples beginning on page-9 to get a quick idea of the variations that would need to be handled. At 208 pages - that's quite a bit of information.
A few quick Google searches turned-up a few interesting links that were relevant to my search for a possible solution:
Canada specific information