Expression Trees

[ftneek]

I've attached some recursive CAS programs for building an expression tree from an expression (build_tree), and building an expression from an expression tree (build_expr).


  trees.hpprgm (Size: 3.48 KB / Downloads: 8)

build_tree(x^2) -> ['^',[[x],[2]]]
build_expr(['^',[[x],[2]]]) -> x^2

By default, expressions are evaluated before building the tree:
build_tree(Zeta(2))
-> ['*',[['^',[[π],[2]]],['inv',[[6]]]]]

But you can build the tree unevaluated by quoting it first:
build_tree('Zeta(2)')
-> ['Zeta',[[2]]]

Currently the expression is always evaluated when rebuilt, and I don't know a way to prevent that:
build_expr(['Zeta',[[2]]])
-> 1/6*π^2

I wrote it because I wanted to be able to apply custom simplification rules to an expression. There was no Gamma simplification available on the prime, but now there is. Lets see it in action:

simplify(Gamma(16/3,0)+Gamma(16/3,inf))
-> Gamma(16/3,0)+Gamma(16/3,inf) (no Gamma simplification)

sgamma(Gamma(16/3,0)+Gamma(16/3,inf))
-> 3640/243*Gamma(1/3) (simplified )

I included sgamma as well. It just automatically builds an expression tree, rebuilds the expression while applying the simplification rules, and returns the result simplified.

For my purposes, simplification happens for the expression Gamma(a,b) when b==0 or inf

Quote:// Custom simplification rules
if f=='Gamma' and l[2]==inf then return 0 end;
if f=='Gamma' and l[2]==0 then return f(l[1]) end;

If anyone has rules for simplifying other functions they can easily be added, and a simple modification would allow you to customize which set of rules get applied to an expression. An improvement for a future version could be to use iteration rather than recursion, but using recursion in python syntax we can build trees with a one-liner:

Code:

// Recursively build a tree from an expression
// Base case: if the expression is a number, variable, etc., return it as a single-element list
// Else, build a list of trees for each argument
// Return the expression tree as [operator, [arguments]]
def build_tree(ex):
 return (type(ex)!=DOM_SYMBOLIC)? ([ex]):([ex[0], [build_tree(ex[j]) for j in range(size(ex)).+1]])