Помогите разобрать мое собственное дерево выражений, C # - PullRequest
Новая
       15

Помогите разобрать мое собственное дерево выражений, C #

1 голос
/ 08 августа 2009

У меня есть следующий код. Я построил дерево выражений, и я застрял при его анализе, чтобы найти результат

Подробности вы найдете в моем коде 

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

    }
}

Ответы [ 2 ]

3 голосов
/ 08 августа 2009

Вам нужен рекурсивный алгоритм, передающий массив значений (код не проверен): 

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

Обратите внимание, что это выполняет все вычисления в два раза; если вы действительно хотите 9/4, вам нужно использовать рациональный тип.

1 голос
/ 08 августа 2009

Для простого элементарного введения в собственные деревья выражений C # 3.0 см., Например. здесь ; к сожалению, я не знаю по-настоящему широкого и глубокого текста по этому вопросу (может быть, книга ..?)

Что касается вашего собственного раскрученного формата, вы можете оценить его наиболее просто с помощью рекурсии; в псевдокоде: 

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

В качестве еще одного поворота, поскольку вы, похоже, хотите получить дробные результаты, в то время как входные значения являются целыми числами, не забудьте использовать тип дроби / рационального числа для своих вычислений - не уверен, что в C # имеется один, но в худшем случае вы можете найти множество в сети; -).

...