C#：Brainfuck 括号查找器

Question

是的，我正在制作 Brainfuck 解释器，但我还需要从其代码创建 AST。可以很容易地在节点中使用原始操作（+ - . , > <）。另一方面，循环操作看起来相当复杂。所以，我需要的是在 [ 和 ] 节点之间建立链接。为此，我在 ] 节点中使用了一个特殊的节点字段。

现在我认为我可以通过在字符串中使用括号位置来创建它们之间的链接。但这里有一个问题 - 如何创建匹配的括号对？

这是我的代码示例：

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

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

我用特殊的方法得到了括号的位置，并把它们放在了相应的列表中。但是我应该用什么来创建它们对呢？喜欢

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

磅数：2、5、17

RB：11、14、23

所以我需要获取元组 <2,14> <5, 11> <17, 23>。

好吧，我可以看出右括号的位置必须大于左括号的位置：通过查看 LB 17 和 RB 14 我们可以说它们没有链接在一起。但我认为有办法让它变得更好。

是的，任何答案都会有所帮助。抱歉我的英语不好。

P.S。我考虑过 Stack，但我不知道如何在我的问题中使用它。 P.P.S。我终于找到了一些有用的东西：How to find the matching pair of braces in a string?

如果我能解决我的问题，我会post这里的解决方案。

Answer 1

据我所知，如果您创建 Tuple，则需要这两个值。因此，我会推出自己的 class:

class MyTuple { public int A; public int B; }

然后，在解析过程中，每次遇到左括号，创建一个MyTuple并将位置分配给.A。然后你 Push 这个实例在你的 Stack 上。继续解析，如果遇到另一个左括号，请创建一个新的 MyTuple 实例并将其 Psuh 也添加到您的 Stack 变量中。如果在 Stack 中遇到右括号 Pop 一个实例，请分配 .B 值并将其作为一个完整的对放入数据结构中。

var s = "brainfuck";
var q = new Stack<MyTuple>();
var res = new YourResultClass();

for(int i = 0; i < s.Length; i++)
{
    if(s[i] == '[')
    {
        var m = new MyTuple();
        m.A = i;
        q.Push(m);
    }
    if(s[i] == ']')
    {
        var e = q.Pop();
        e.B = i;
        res.lsTuples.Add(e);
    }
}
if(q.Count > 0)
    throw new IOException();

Answer 2

这是一个"not very efficient but straightforward"方法。

对于每个左括号 X，通过执行以下操作查找其对：

声明一个变量bracketCount
遍历X
如果您看到另一个左括号，请在 bracketCount
如果您看到另一个右括号，请检查 bracketCount 是否为 0，如果是，则您找到了与 X 对应的右括号！如果不为0，则bracketCount.

Answer 3

好吧，我有各种各样的输入异常，所以我可以只使用一个堆栈。

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

对我来说似乎足够了。

C#：Brainfuck 括号查找器

C#: Brainfuck brackets finder

c#

brainfuck