This is very challenging for generic case since shortcodes can be nested, can be self-closing or enclosing and so on.
If you need to do this on limited and fixed set of specific shortcodes that would be easier. I would unregister their shortcode handlers and register custom handlers that call original ones and add necessary markup around.