C#: Brainfuck brackets finder

Question

So yeah, I'm making Brainfuck interpreter but I also need to create AST from its code. Primitive operations (+ - . , > <) can be used in a node pretty easily. The loop operations, on the other hand, look quite complex. So, what I need is to make links between [ and ] nodes. For that I use a special Node field in ] node.

And now I think that I can create links between them by using brackets positions in a string. But here's a problem - how can I create matching pairs of brackets?

Here's the sample of my code:

    private readonly List<int> rightBracketsIds;
    private readonly List<int> leftBracketsIds;

    private List<Tuple<int, int>> lsTuples;

I get positions of brackets by using special method and place them in a corresponding list. But what should I use for creating pairs of them? Like

++[>+[>++<-]<-]++[>++<-]>.

LBs: 2, 5, 17

RBs: 11, 14, 23

So I need to get Tuples <2,14> <5, 11> <17, 23>.

Well, I can kinda see that right bracket must have position greater than left bracket's: by looking at LB 17 and RB 14 we can say that they are not linked together. But I think there's a way to get it better.

So yeah, any answers will be helpful. Sorry for my bad english.

P.S. I've thought about a Stack, but I don't know how to use it in my problem. P.P.S. I've finally found something useful: How to find the matching pair of braces in a string?

If I'll solve my problem, I'll post the solution here.

Answer 1

Well, I have all kinds of exceptions for input, so I can use just one stack.

class Program
{
    static void Main(string[] args)
    {
        Solver s = new Solver();
        s.Solve("++[>+[>++<-]<-]++[>++<-]>.");
        s.Visualize();
        Console.Read();
    }
}

public class Solver
{
    private readonly List<int> rightBracketsIds;
    private readonly List<int> leftBracketsIds;

    private readonly List<Tuple<int, int>> lsTuples;
    public Solver()
    {
        rightBracketsIds = new List<int>();
        leftBracketsIds = new List<int>();
        lsTuples = new List<Tuple<int, int>>();
    }

    public void Solve(string s)
    {
        Stack<int> st = new Stack<int>();
        for (int i = 0; i < s.Length; i++)
        {
            switch (s[i])
            {
                case '[':
                    st.Push(i);
                    break;
                case ']':
                    int index = st.Any() ? st.Pop() : -1;
                    lsTuples.Add(new Tuple<int, int>(index, i));
                    break;
            }
        }
    }

    public void Visualize()
    {
        foreach (Tuple<int, int> tuple in lsTuples)
        {
            Console.WriteLine(tuple.Item1 + " " + tuple.Item2);
        }
    }
}

Seems good enough for me.