Looping through a string finding nested brackets So I've been trying to check through a string, looping for, [ (start) and ] (end).

In this, I also have to check for nested brackets.

My expected output, given input [depth1[depth2]] is as follows:


depth2
depth1[depth2]


To achieve this, I wrote this little snippet of code, which uses a Dictionary&lt;int, int&gt; to store the initial bracket's position at a given depth. If it finds another opening bracket, the depth will increase (and the position will be recorded). It will look for the next ending bracket (with respect to any other opening brackets), and get the initial position of the bracket for that depth. (Thus we get both the beginning and ending of that nested string)

    var depthItems = new Dictionary&lt;int, int&gt;();
    int depth = 0;

    string input = "[depth1[depth2]]";

    for (int i = 0; i &lt; input.Length; i++) {
        if (input[i] == '[') {
            depth++;
            depthItems.Add(depth, i);
        } else if (input[i] == ']') {
            int item = depthItems[depth];
            depthItems.Remove(depth);
            depth--;
            Console.Write($"Found item at ({item}, {i}) -&gt; ");
            Console.WriteLine(input.Substring(item + 1, i - item - 1));
        }
    }


I'm not sure how viable this would be when looking up against large strings with lots of nested brackets - I think it's a start, at least.

I will note that I was first surprised that higher "depths" were returned first, but then realised that in order for the lower ones to complete, the higher ones should have been returned first. Not a bad thing, but curious to note.

So how could this be improved, especially in terms of memory (i.e. large strings)?
I'm not sure how viable this would be when looking up against large strings with lots of nested brackets [...]


"how viable" is a very vague question.
Two common performance metrics are CPU load and memory load,
perhaps that's what you were trying to get at.
It's good to clarify what exactly you want to know.

In terms of CPU, how will this program behave as the input grows?  


The algorithm does a single pass over all characters of the input.
When the input doubles, the number of operations doubles, roughly.


=> In other words, it's linear.

Can it be any better than linear?


=> No, because we cannot know the positions of the brackets without looking through each character once.



In terms of memory, how will this program behave as the input grows?


Aside from the memory used by the input string,
what consumes memory in this program?


=> The dictionary storing the starting positions of brackets.

How do brackets on the same nesting level impact the memory consumption?
That is, in a string like [][][][]?


=> Since the storage for a [ is removed when the corresponding ] is found, brackets at the same nesting level use a single entry in the dictionary.

How do deeply nested brackets impact the memory consumption?


=> The dictionary has as many entries as the deepest nesting level. As closing brackets are found, entries get deleted. The maximum memory consumed by the dictionary throughout the program is proportional to the maximum depth of nesting encountered.




  So how could this be improved, especially in terms of memory (i.e. large strings)?


The current performance of the program is on the expected order of complexity, so it's fine.
However, a dictionary is not the most natural choice for this purpose,
and its actually overkill.
A simpler data structure, a stack, would have been enough to solve this.
Instead of storing (depth, index) pairs in a dictionary,
you could store just index in a stack:


When you see a [, push the index onto the stack.
When you see a ], pop the last pushed index from the stack.


The result will be equivalent, the depth variable becomes unnecessary.