It is possible to manipulate expressions by manipulating the corresponding expression tree created by Jep. The
parse()
and getLastRootNode()
methods can be used to obtain the expression tree of an expression.
This will be useful if you want to do more than just evaluate the expressions
you parse. For example, you may want to determine the derivative of an expression.
In order to be able to this, you need direct access to the expression
tree.
The expression tree consists of Nodes. Each of the nodes in the parse tree is an object of one of the following types:
There are several methods of Node and its sub-classes which can be used to interrogate the node.
node.jjtGetNumChildren()
returns the number of children of the node.
For constants and variable nodes this is 0, for functions and operators this is the number of arguments.node.jjtGetChild(i)
returns the i-th child of the node.((ASTConstant) node).getValue()
returns the value of a constant node.((ASTVarNode) node).getVar()
returns the variable object associated with a variable node.((ASTVarNode) node).getName()
returns the name of the variable.((ASTVarNode) node).getValue()
returns the value of the variable.((ASTFunNode) node).getName()
returns the name of the function.((ASTFunNode) node).getPFMC()
returns PostfixMathCommandI for the function.((ASTOpNode) node).getOperator()
returns the operator.((ASTOpNode) node).getPFMC()
returns PostfixMathCommandI for the function.The com.singularsys.jep.NodeFactory class contains various methods for creating different types of node to make an expression. For example the following produces an expression "5+cos(x)".
NodeFactory nf = jep.getNodeFactory(); Node node = nf.buildOperatorNode( jep.getOperatorTable().getAdd(), nf.buildConstantNode(new Double(5)), nf.buildFunctionNode("cos", nf.buildVariableNode("x")));
There are several methods of traversing the expression tree. The most commonly used method is based on the Visitor pattern. ParserVisitor defines an interface for classes which wish to use this.
public interface ParserVisitor { public Object visit(ASTConstant node,Object data) throws JepException; public Object visit(ASTFunNode node,Object data) throws JepException; public Object visit(ASTVarNode node,Object data) throws JepException; public Object visit(ASTOpNode node,Object data) throws JepException; }
A class which wishes to traverse the tree would need to implement each method,
the data
argument can be used to pass in arbitrary data and they can return arbitrary values.
To start the transversal call
Node.jjtAccept(ParserVisitor pv,Object data)
for the top node of the expression, the visitor pattern will take care of
calling the correct method.
The visit(ASTFunNode)
and visit(ASTOpNode)
methods
will often be similar in functionality as both have a PFMC and a number of child nodes.
They should generally call Node.jjtAccept
for each child.
public Object visit(ASTFunNode node,Object data) throws JepException { int nChild = node.jjtGetNumChildren(); Object[] results = new Object[nChild]; for(int i=0;i<nChild;++i) results[i] = node.jjtGetChild(i).jjtAccept(this,data); // now process this node return res; } // Just call the ASTFunNode method public Object visit(ASTOpNode node,Object data) throws JepException { return visit((ASTFunNode) node,data); }
For visitors which manipulate expressions and return a modified parse tree
the
DoNothingVisitor
and
DeepCopyVisitor
can be used as base classes. DoNothingVisitor visits each node in turn and does nothing, it
provides the Node[] visitChildren(Node node,Object data)
methods
which simplifies the process of visiting the child nodes. DeepCopyVisitor produces a deep copy
of the expression.
For very large equations with 10,000+ nodes the standard ParserVisitor class
can encounter problems with stack overflows due to recursions. The
PostfixTreeWalker
offers a base class for
a transversal strategy which minimizes the number of stack frames
used and the PostfixEvaluator
is an evaluator which uses this strategy. These methods visit each node in postfix fashion
hence for 1+cos(x)
the nodes are visited in the order
1, x, cos, +.
PrefixTreeWalker is similar but visits nodes in a prefix fashion
for 1+cos(x)
the nodes are visited in the order
+, 1, cos, x
.
The TreeAnalyzer provides methods to find the variables, functions, operators and constants in an equation, as well as the number of nodes and depth of the tree.
Jep j=new Jep(); Node n = j.parse("0.5*(cos(x+y)+cos(x-y))"); TreeAnalyzer ta = new TreeAnalyzer(n); // get sorted list of variable names String[] vars=ta.getVariableNames(); System.out.println(ta.toString()); /* Prints Nodes: 11, depth: 5 Variables: 4 - x(2), y(2) Functions: 2 - cos(2) Operators: 4 - "-"(1), "+"(2), "*"(1) Constants: 1 - 0.5(1) */
The SubstitutionVisitor provides methods to substitute one expression into another. For example
Jep jep = new Jep(); Node node = jep.parse("x^2+x"); Node sub = jep.parse("sin(y)"); SubstitutionVisitor sv = new SubstitutionVisitor(jep); Node res = sv.substitute(node,"x",sub);Will give the expression
(sin(y))^2+sin(y)
.