> One can, of course, also build an actual table indexed on operation and type as a data structure in just about any language and use it, and in a language like C++ the result may well be quite a bit nicer than using a class hierarchy.

This requires unsafe casting and thus doesn't actually solve the expression problem, which is about how to do this without compromising safety. Your approach is what the solution to the expression problem in Haskell effectively does at runtime though, via type classes and the dictionary-passing translation that they undergo during compilation, but it's all type safe.