As of mypy 0.990, mypy finally supports recursive type annotations, using the natural syntax:

from typing import Union, Dict, List

JSONVal = Union[None, bool, str, float, int, List['JSONVal'], Dict[str, 'JSONVal']]

d: JSONVal = {'a': ['b']}

mypy output:

Success: no issues found in 1 source file

Before 0.990, this would produce an error reporting a lack of recursive type support:

$ mypy asdf.py
asdf.py:3: error: Recursive types not fully supported yet, nested types replaced with "Any"

On such versions, Dict[str, Any] would be the way to go.

You can also use mutually recursive type aliases now, so you can do things like

from typing import Union, Dict, List

JSONVal = Union[None, bool, str, float, int, 'JSONArray', 'JSONObject']
JSONArray = List[JSONVal]
JSONObject = Dict[str, JSONVal]

d: JSONObject = {'a': ['b']}

Use recursion, and use type() or isinstance() to decide what to do.

def handle(x):
    if isinstance(x, dict):
        # do dict stuff
        for key, val in x.items():
            handle(val)
    elif isinstance(x, list):
        # do list stuff
        for val in x:
            handle(val)
    elif isinstance(x, str):
        # do string stuff
        print(x)
    elif isinstance(x, (int, float)):
        # maybe integer, float, etc
        print(x)
    else:
        print("None???")

d = json.loads(json_string)

handle(d)

Above recursive implementation will handle your use case of array in array, dict in array, etc

The JSON might contain a list of objects, which needs to be searched:

Python 2.7 version:

def item_generator(json_input, lookup_key):
    if isinstance(json_input, dict):
        for k, v in json_input.iteritems():
            if k == lookup_key:
                yield v
            else:
                for child_val in item_generator(v, lookup_key):
                    yield child_val
    elif isinstance(json_input, list):
        for item in json_input:
            for item_val in item_generator(item, lookup_key):
                yield item_val

Python 3.x version:

def item_generator(json_input, lookup_key):
    if isinstance(json_input, dict):
        for k, v in json_input.items():
            if k == lookup_key:
                yield v
            else:
                yield from item_generator(v, lookup_key)
    elif isinstance(json_input, list):
        for item in json_input:
            yield from item_generator(item, lookup_key)

I'm interpreting this question as "my injson data structure contains a series of objects that represent the components of an expression. How can I evaluate this expression and return the final result?"

The grammar of your expression language looks pretty simple: each component is either a simple value, such as "yang", or a dictionary that represents a function call. So your recursive evaluator only needs to handle those two cases. Most of the real work will be in translating your custom operators into something that Python understands.

Example implementation:

import operator

def check_type(obj, type_name):
    #we can't just directly use `isinstance` for type checks, because `isinstance("foo", "string")` doesn't understand what the second argument is supposed to represent.
    #so we need an extra layer here to convert type-looking strings into actual types.
    types_by_name = {"string": str, "int": int, "bool": bool} #add more types as desired
    return isinstance(obj, types_by_name[type_name])

operators_by_name = {
    "gte": operator.ge,
    "startswith": str.startswith,
    "type": check_type,
    #add more named functions as desired
}

def eval_json(obj):
    if isinstance(obj, dict) and "$op" in obj:
        op = operators_by_name[obj["$op"]]
        args = [eval_json(arg) for arg in obj["$params"]]
        return op(*args)
    else:
        return obj

injson = {
    "params": [
        {
            "$op": "startswith",
            "$params": ["yang", "y"]
        },
        {
            "$op": "type",
            "$params": ["yang", "string"]
        }
    ]
}
print(eval_json(injson))

Result:

True

This is the desired result, since "yang".startswith("y") >= isinstance("yang", str) also evaluates to True.

with recursion you can do something like this:

result = []

def finditem(obj, key):
    if key in obj: result.append({"timestamp": obj[key], "text": obj['textsList'][0]['text']})
    for k, v in obj.items():
        if isinstance(v,dict):
            item = finditem(v, key)
            if item is not None:
                result.append({"timestamp": item,"text":v['textsList'][0]['text']})
        elif isinstance(v,list):
            for i in v:
                item = finditem(i, key)
                if item is not None:
                    result.append({"timestamp": item,"text": i['textsList'][0]['text']})

finditem(data, 'timestamp')
print (result)

result:

[{'timestamp': 1234567890, 'text': 'some text here 0'}, {'timestamp': 12345678901234, 'text': 'some other text 1'}, {'timestamp': 12345678901234, 'text': 'some other text 2'}]

EDIT:

result = []
def finditem(obj, key):
    if key in obj and obj[key]=='Recursive': result.append({"timestamp": obj["data"]["timestamp"],"text": obj["data"]['textsList'][0]['text']})
    for k, v in obj.items():
        if isinstance(v,dict):
            item = finditem(v, key)
            if item == 'Recursive':
                d = v['timestamp']
                result.append({"timestamp": d,"text": v['textsList'][0]['text']})
        elif isinstance(v,list):
            for list_item in v:
                item = finditem(list_item, key)
                if item == 'Recursive':
                    d = list_item['timestamp']
                    result.append({"timestamp": d,"text": list_item['textsList'][0]['text']})

finditem(data,'type')
print (result)

result:

[{'timestamp': 12345678901234, 'text': 'some other text 1'}, {'timestamp': 12345678901234, 'text': 'some other text 2'}]

You can use recursion with itertools.count:

import itertools
class Heading:
   def __init__(self, text):
     self._text = text
     self._subheadings = []
   def add_subheading(self, sub):
     self._subheadings.append(sub)
   @classmethod
   def to_dict(cls, _obj):
     c = itertools.count(1)
     def _to_dict(d):
        return {f'h{next(c)}_heading':d._text, 'children':list(map(_to_dict, d._subheadings))}
     return _to_dict(_obj)

Now:

import json
h, c1, c2 = Heading('test_header1'), Heading('test_sub_header1'), Heading('test_sub_header2')
c1.add_subheading(c2)
h.add_subheading(c1)
print(json.dumps(Heading.to_dict(h), indent=4))

Output:

{
    "h1_heading": "test_header1",
    "children": [
    {
        "h2_heading": "test_sub_header1",
        "children": [
            {
                "h3_heading": "test_sub_header2",
                "children": []
            }
        ]
      }
   ]  
}

This is a simplified example, however, the recursive procedure can be easily updated to support custom key names, etc.