Mex - 2 years ago 220
Brainfuck Question

# C#: Brainfuck brackets finder

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 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.

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.

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();
}
}

public class Solver
{

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;
break;
}
}
}

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

Seems good enough for me.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download