C# assistance with parsing my own expression tree

c# expression-trees parsing

Question

I have the following code. I constructed an expression tree and I am stuck parsing it to find the result

You will find the details within my 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

    }
}
1
1
8/8/2009 5:21:28 PM

Fastest Entity Framework Extensions

Bulk Insert
Bulk Delete
Bulk Update
Bulk Merge

Accepted Answer

For a simple elementary intro to C# 3.0's own expression trees, see e.g. here; unfortunately I am not aware of a really broad and deep text on the subject (maybe a book..?).

As for your own hand-rolled format, you can evaluate it most simply by recursion; in 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

As a further twist, as you appear to want fraction results while the input values are integers, remember to use a fraction / rational number type for your computations - not sure if C# comes with one, but worst case you can find plenty on the net;-).

1
8/8/2009 5:12:59 PM

Popular Answer

You need a recursive algorithm, passing the values array (code untested):

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

Notice that this performs all computations in double; if you really want 9/4, you would need to use a rational type.

Martin v. Löwis

Related Questions

Parsing of Lambda Expression Trees

To get the actual value, you need to apply the logic of the expression tree to whatever context you've got....The whole point of expression trees is that they represent the ...logic... as data rather than evaluating the expression. You'll need to work out what the lambda expression truly means. That may mean evaluating some parts of it against loca...
c# expression-trees lambda
asked by Jon Skeet

In C#, how can I build an Expression Tree by parsing XML?

I'd start by looking at the DLR, which has a published expression tree mechanism.
.net c# expression-trees linq xml
asked by Will Dean

How can I parse random strings into expression trees in C#?

Try out ...Irony.... Though the documentation is lacking, the samples will get you up and running very quickly. Irony is a project for parsing code and building abstract syntax trees, but you might have to write a little logic to create a form that suits your needs. The ...DLR... may be the complement for this, since it can dynamically generate / e...
.net c# expression-trees parsing
asked by OregonGhost

An expression tree may be sent as a parameter to another expression tree.

I have two expression trees defined like this:...private Expression<Func<TEntity, TPropertyResult>> PropertyAccessor { get; set; } ...and...private Expression<Func<TPropertyResult, bool>> TestExpression { get; set; } ...I need to create a new expression tree that will result in the equivalent of:...var expression = p => this.TestExpression(this.Pro...
c# expression-trees lambda
asked by Pierre-Alain Vigeant

Create an expression tree from a boolean condition.

In can create expression trees from delegates. For example, if you define your method so that it takes a delegate as a parameter, you can use it as follows:...public void Foo(Func<bool> fn) { // invoke the passed delegate var result = fn(); } Foo(() => "MyField" == "MyValue"); ...In order to create an expression tree, rather than execute t...
c# expression-trees linq
asked by ColinE

Creating an expression tree from a list of tokens

In a nutshell then, even though you have a token list you still need a parser. ...Parsec can handle alternative token streams, but you'll probably have to refer to the manual - a PDF available at Daan Leijen's "legacy" home page - ...http://legacy.cs.uu.nl/daan/download/parsec/parsec.pdf.... You can roll your own parser without using a combinator l...
algorithm expression-trees haskell
asked by stephen tetley

Parser tree or expression tree

I'm doing a command line calculator, so I need to parse expressions....calc 2*(3+4)*5 ...I already have the scanner step done, returning a token's array. Now I'm at parser step. However I have no clue about how to do a parser/expression tree....This is all I have so far:...NODE* create_node(TOKEN* t) { NODE* n = (NODE*)malloc(sizeof(NODE)); ...
c expression-trees parsing
asked by Fabricio

How can I create a LINQ-friendly 'return false' expression using C# expression trees?

Expression<Func<T, bool>> falsePredicate = x => false;
.net c# expression-trees linq
asked by Rui Jarimba

Need help creating an expression tree for Where clause

Googled it out!...var paramExpr = Expression.Parameter(typeof(TSource), "src"); var memberExpr = (MemberExpression)property.Body; List<Expression> arrayInits = new List<Expression>(); var arrExpr = Expression.Constant(((string)values[0]).Split(new char[] { ';' })); MethodInfo containsMethod = typeof(ICollection<string>).GetMethod("Contains"); v...
c# expression-trees linq-to-entities
asked by Trainee4Life

Building an expression tree using a stack and a binary tree c

I am given an arithmetic formula containing operators +, -, *, / and parentheses (which might or might not change the natural precedence of operators). An example would be the following one: a / b + f – (c + d) * e – a * c. and I am asked to use a stack (implemented as a linked list) in order to keep track of the operands and the operators: an...
binary-tree c expression-trees stack
asked by user1680944

Fastest Entity Framework Extensions

Bulk Insert
Bulk Delete
Bulk Update
Bulk Merge
View more on Stack Overflow

Prime Library

Performance

Expression Evaluator

More Projects...
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow