C#: Brainfuck Klammern Finder

Question

Also ja, ich mache Brainfuck Interpreter, aber ich muss auch AST von seinem Code erstellen. Primitive Operationen (+ -.,> <) können ziemlich einfach in einem Knoten verwendet werden. Die Schleifenoperationen sehen dagegen ziemlich komplex aus. Also, was ich brauche, ist, Verbindungen zwischen [und] Knoten zu machen. Dafür benutze ich ein spezielles Node-Feld in] node.

Und jetzt denke ich, dass ich Verknüpfungen zwischen ihnen erstellen kann, indem Sie Klammern Positionen in einer Zeichenfolge verwenden. Aber hier ist ein Problem - wie kann ich passende Paare von Klammern erstellen?

Hier ist die Probe meines Code:

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

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

I Positionen von Klammern erhalten, indem spezielle Methode verwenden und sie in einer entsprechenden Liste platzieren. Aber was sollte ich für die Erstellung von Paaren verwenden? Wie

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

LBs: 2, 5, 17

RBs: 11, 14, 23

Also muss ich Tupeln < 2,14> < 5, 11> < 17, erhalten 23>.

Nun, ich kann irgendwie sehen, dass die rechte Klammer Position haben muss, die größer ist als die linke Klammer: mit Blick auf LB 17 und RB 14 können wir sagen, dass sie nicht miteinander verbunden sind. Aber ich denke, es gibt einen Weg, es besser zu machen.

Also ja, alle Antworten werden hilfreich sein. Entschuldigung für mein schlechtes Englisch.

P.S. Ich habe über einen Stack nachgedacht, aber ich weiß nicht, wie ich ihn in meinem Problem verwenden soll. P.P.S. Ich habe endlich etwas Nützliches gefunden: How to find the matching pair of braces in a string?

Wenn ich mein Problem lösen werde, werde ich die Lösung hier posten.

Answer 1

Nun, ich habe alle Arten von Ausnahmen für die Eingabe, so dass ich nur einen Stapel verwenden kann.

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

Scheint gut genug für mich.

Answer 2

Soweit ich weiß, benötigen Sie beide Werte, wenn Sie eine Tuple erstellen. Aus diesem Grunde würde ich meine eigene Klasse rollen:

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

Dann während der Analyse, jedes Mal, wenn eine öffnende Klammer erfüllen, ein MyTuple schaffen und die Position zu .A zuweisen. Dann haben Sie Push diese Instanz auf Ihrem Stack. Wenn Sie eine andere öffnende Klammer treffen, erstellen Sie eine neue MyTuple Instanz und Psuh es auch zu Ihrer Stack Variable. Wenn Sie eine schließende Klammer Pop eine Instanz von der Stack erfüllen, weisen Sie den .B Wert zu und fügen Sie es als ein abgeschlossenes Paar in Ihre Datenstruktur ein.

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 3

Hier ist ein "nicht sehr effizient, aber geradlinig" Weg.

Für jede öffnende Klammer X, indem Sie diese für seine Paar aussehen:

• eine
• nach XbracketCount
• Schleife durch die Zeichen Variable deklarieren Wenn Sie eine andere öffnende Klammer sehen, fügen Sie 1 bis die bracketCount
• Wenn Sie eine andere schließende Klammer sehen, überprüfen Sie, ob bracketCount 0 ist, wenn es ist, haben Sie die schließende Klammer entsprechend X gefunden! Wenn es nicht 0 ist, subtrahiere 1 von bracketCount.