Easiest way to calculate how deep a structure is?

Question

Let say I have a AST-structure (a list of lists) like this one :

 [+, [*, a,b],[*,c,d] ]
 [+, [*, a,b],[*,c,[ +, d, e] ] ]

what is the easiest and/or fastest way to calculate how deep the structure is i.e. how many levels it is ?

As a second option you could also work with it as a String, rather than List-of-Lists (LoL). F.e.:

"[+, [*, a,b],[*,c,d] ]"

I could use both.

Traverse the string and keep track of the depth by counting `[` and `]`. — CristiFati, Sep 04 '17 at 19:37
FYI: From experience, I highly recommend using objects over lists/tuples to represent an abstract syntax tree. Using the latter is fragile, and the former offers a much more convenient interface. — Christian Dean, Sep 04 '17 at 19:37
A way would be to represent your structure with a graph and apply graph-based algorithms (e.g. DFS etc...) - but graph theory is a huge topic and your question is very general (e.g. do you want to count cycles, etc...) — coder, Sep 04 '17 at 19:45

score 3 · Answer 1 · answered Sep 04 '17 at 19:44

You can keep the count of the square brackets. You can find a more detailed explanation here. Here is an adaptation of the code:

string = str(tree)

currentDepth = 0
maxDepth = 0
for c in string:
    if c == '[':
        currentDepth += 1
    elif c == ']':
        currentDepth -= 1

    maxDepth = max(maxDepth, currentDepth)

Same caveat, this will break if your data might contain '[' or ']'. In such case, you'll need to define an escape method for those square brackets.

Easiest way to calculate how deep a structure is?

1 Answers1