Iterate through objects then parent and add material based on string search in names
Use string.split.

As you are already familiar with programming, and without a test file, will run thru an example. Use pythons String.split to split the name as is into a list using the underscore as a separator.  If there are 4 members in the split etc..

import bpy
context = bpy.context 
scene = context.scene

def parent(name):
    ob = scene.objects.get(name)
    if not ob:
        ob = bpy.data.objects.new(name, None)
        scene.objects.link(ob)
    return ob

def material(name):
    ma = bpy.data.materials.get(name)
    if not ma:
        # add a new material as in link
        pass
    return ma

# iterate thru all obs in scene
for ob in scene.objects[:]:
    split = ob.name.split("_")
    if len(split) != 4:
        continue
    a, b, c, name = split
    ob.parent = parent(c)
    # add materials etc.