Hilfe beim Parsen meines eigenen Ausdrucksbaums, C #

c# expression-trees parsing

Frage

Ich habe den folgenden Code. Ich habe einen Ausdrucksbaum konstruiert, und ich stecke ihn fest, um das Ergebnis zu finden

Sie finden die Details in meinem Code

public enum OpertaionType { add, sub, div, mul} 

public class Node {
    public Node(Node lhs, Node rhs, OpertaionType opType, int index) {
        this.lhs = lhs;
        this.rhs = rhs;
        this.opType = opType;
        this.index = index;
    }
    Node lhs;
    Node rhs;
    OpertaionType opType;
    int index;
}
class Program
{
    static void Main(string[] args)
    {
        // I don't want this to be part of the node data structure
        // because in the actual implementation I will end up referencing an
        // array of data

        int[] value = new int[5];

        Node[] nodes = new Node[value.Length];
        for (int i = 0; i < value.Length; i++)
        {
            value[i] = i+1;
            nodes[i] = new Node(null, null, 0, i);
        }



        // suppose I constructed the tree like that 
        // note that the end nodes are marked by non-negative index that indexes the
        // values array

        Node a = new Node(nodes[0], nodes[1], OpertaionType.add, -1);
        Node b = new Node(nodes[2], a, OpertaionType.mul, -1);
        Node c = new Node(b, nodes[3], OpertaionType.div, -1);

        // How can I find the result of Node c programatically
        // such that the result is (a[2]*(a[0]+a[1]))/a[3] = 9/4

    }
}

Akzeptierte Antwort

Für ein einfaches elementares Intro zu C # 3.0 eigenen Ausdrucksbäumen, siehe zB hier ; leider bin ich mir eines wirklich breiten und tiefen Textes zu diesem Thema nicht bewusst (vielleicht ein Buch ..?).

Was Ihr eigenes handgewalztes Format betrifft, können Sie es am einfachsten durch Rekursion bewerten; im Pseudocode:

def valof(node):
  if node.index >= 0: 
    return whateverarray[node.index]
  L = valof(node.lhs)
  R = valof(node.rhs)
  if node.opType == add:
    return L + R
  if node.opType == mul:
    return L * R
  # etc etc

Als weitere Wendung sollten Sie daran denken, einen Bruch / rationalen Zahlentyp für Ihre Berechnungen zu verwenden, da Sie scheinbar Bruchergebnisse erhalten möchten, während die Eingabewerte Ganzzahlen sind. Sie sind sich nicht sicher, ob C # einen, sondern den schlimmsten Fall im Netz enthält ;-).


Beliebte Antwort

Sie benötigen einen rekursiven Algorithmus, der das Werte-Array (Code ungeprüft) weitergibt:

class Node{
  //...
  double compute(int[] values){
    if(index >= 0)
      return values[index]; // leaf node; value stored in array
    switch(opType){
      case add: return lhs.compute(values)+rhs.compute(values);
      case sub: return lhs.compute(values)-rhs.compute(values);
      case div: return lhs.compute(values)*rhs.compute(values);
      case mul: return lhs.compute(values)/rhs.compute(values);
    }
    throw new Exception("unsupported operation type");
  }
}

Beachten Sie, dass damit alle Berechnungen doppelt ausgeführt werden. Wenn Sie wirklich 9/4 wollen, müssten Sie einen rationalen Typ verwenden.




Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Ist diese KB legal? Ja, lerne warum