dendrocas 0.1.0 copy "dendrocas: ^0.1.0" to clipboard
dendrocas: ^0.1.0 copied to clipboard

Published 3 days ago
SDKDartFlutter
PlatformAndroidiOSLinuxmacOSwebWindows
→

Metadata

A little CAS for building callable mathematical syntax trees from strings.

More...

pub package license

Welcome to dendrocas, a little CAS for parsing mathematical expression strings into callable abstract syntax trees.

To Use #

  1. Add to your project.

    dart pub add dendrocas

  2. Import to your code.

    import 'package:dendrocas/dendrocas.dart';

Basic Use #

Strings to Doubles #

Dendrocas provides a toDouble method on strings that returns a double value of the constant represented. For simple strings, toDouble works similarly to double.parse, but toDouble can also handle more complicated string representations.

Example

final strings = [
   '1.5',
   '2.5e-3',
   '3^2 + 2*5 - 1/2',
   'log(2e)',
   'tan(π/4)',
   'acot(sqrt(3)/2)',
];

for (final s in strings) {
   print('"$s" -> ${s.toDouble()}');
}

"1.5" -> 1.5
"2.5e-3" -> 0.0025
"3^2 + 2*5 - 1/2" -> 18.5
"log(2e)" -> 1.69314718055995
"tan(π/4)" -> 1.0
"acot(sqrt(3)/2)" -> 0.85707194785013

If the string fails to parse or does not reduce to a constant value, toDouble throws a ParseException.

Single Variable Functions #

Dendrocas provides a singleVariableFunction (or svf) property on strings that returns an instance of SVF (single-variable function), a convenience wrapper class that behaves similarly to double Function(num) functions.

Example

final values = [1, 2, 3, 4, 5],
  f = 'pow(x, 2)'.svf;

for (final x in values) {
   final y = f(x);
   print('f($x) = $y');
}

f(1) = 1.0
f(2) = 4.0
f(3) = 9.0
f(4) = 16.0
f(5) = 25.0

An SVF can be built from a constant expression, in which case it represents a constant function, but an attempt to create an SVF from an expression containing more than one distinct variable will throw a ParseException.

Derivatives #

Dendrocas can perform differentiation; for an instance of SVF, a property derivative gives us a new instance of SVF representing the derivative.

Example

final f = 'log(x^2+1)'.svf,
  x = f.variable,
  df = f.derivative;

print(' f($x) = $f');
print("f'($x) = $df");
print(' f(2) = ${f(2)}');
print("f'(2) = ${df(2)}");

 f(x) = log(1+x^2)
f'(x) = 2*x*(1+x^2)^(-1)
 f(2) = 1.6094379124341
f'(2) = 0.8

SVF instances have a property root, which provides access to the root node of the wrapped syntax tree, and variable, which provides access to the function's variable node.

Nodes & Node Hierarchy #

Under the hood, string expressions are parsed into abstract syntax trees. Classes of nodes are organized in a hierarchy according to role in expressions. At the top of the hierarchy is the abstract Node, which is the parent class of Leaf, Projector and Branch.

flowchart BT
   1([Node])
   2([Leaf])
   3([Branch])
   4([Projector])

   2 --- 1
   3 --- 1
   4 --- 1

Leaf #

The abstract class Leaf represents a terminating node, and is parent to instantiable subclasses Constant and Variable.

flowchart BT
   1([Leaf])
   2([Constant])
   3([Variable])

   2 --- 1
   3 --- 1

A Constant wraps a double value and represents a number. A Variable represents a named variable that can be used for substitutions.

Branch #

The abstract class Branch represents an operation and has two children, namely leftChild and rightChild, representing the left and right operands respectively. Branch is parent to the instantiable subclasses Difference, Power, Product, Quotient and Sum.

flowchart BT
   1([Branch])
   2([Difference])
   3([Power])
   4([Product])
   5([Quotient])
   6([Sum])

   2 --- 1
   3 --- 1
   4 --- 1
   5 --- 1
   6 --- 1

Projector #

The abstract class Projector represents a function, and has a single child representing the argument of the function. The instantiable Projector subclasses that inherit from Projector and the strings they are generated from and expressed as are:

Class String Notes
ArcCosecant acsc
ArcCosine acos
ArcCotangent acot Defined as π/2 - atan, with range (0, π), which differs from some textbooks.
ArcHyperbolicCosecant acsch
ArcHyperbolicCosine acosh
ArcHyperbolicCotangent acoth
ArcHyperbolicSecant asech
ArcHyperbolicSine asinh
ArcHyperbolicTangent atanh
ArcSecant asec
ArcSine asin
ArcTangent atan
Cosecant csc
Cosine cos
Cotangent cot
Exponential exp
HyperbolicCosecant csch
HyperbolicCosine cosh
HyperbolicCotangent coth
HyperbolicSecant sech
HyperbolicSine sinh
HyperbolicTangent tanh
Logarithm log "ln" also accepted to generate the node.
Negative -
Secant sec
Sine sin
SquareRoot sqrt
Tangent tan

Constants, Variables & Substitution #

Dendrocas provides string properties constant or c (returning an instance of Constant), variable or v (returning an instance of Variable), and tree or t (returning the root node of a constructed syntax tree). Values can be substituted into a tree using a mapping of Variable to Node.

Example

final x = 'x'.variable,
   y = 'y'.variable,
   x0 = 'e'.constant,
   y0 = 'sqrt(2)'.constant,
   f = 'log(x) + y^2'.tree,
   result = f({x: x0, y: y0});

print('f = $f\n');
print('f(x0, y0)\n= f($x0, $y0)\n= $result');

f = log(x)+y^2

f(x0, y0)
= f(2.718281828459, 1.4142135623731)
= 3

We are not constrained to constants when performing substitutions; we can substitute whole new trees.

Example

final x = 'x'.v,
  f = '5x^2'.t,
  g = '3x+2'.t;

print('    f(x) = $f');
print('    g(x) = $g');
print('(f∘g)(x) = ${f({x: g})}');
print('(g∘f)(x) = ${g({x: f})}');
print('(f∘f)(x) = ${f({x: f})}');

    f(x) = 5*x^2
    g(x) = 2+3*x
(f∘g)(x) = 5*(2+3*x)^2
(g∘f)(x) = 2+15*x^2
(f∘f)(x) = 5*(5*x^2)^2

Example

final x = 'x'.v,
  y = 'y'.v,
  f = 'x^2 + 2y'.t,
  g = 'a + b'.t;

print(' f(x, y)  = $f');
print('f($g, y) = ${f({x: g})}');
print('f(x, $g) = ${f({y: g})}');
print('f($g, $g) = ${f({x: g, y: g})}');

 f(x, y)  = x^2+2*y
f(a+b, y) = (a+b)^2+2*y
f(x, a+b) = x^2+2*(a+b)
f(a+b, a+b) = (a+b)^2+2*(a+b)

Accessing these string properties throws instances of ParseException if the strings are invalid or the result is not of the expected type (e.g., variable will fail if the string is invalid or does not resolve an instance of Variable). Accessing constant on a string that reduces to an undefined or infinite value does not throw ParseException (because the parsing didn't fail) but yields a valid Constant.

Explicit Tree Construction #

Nodes are generated through string extensions in most use cases, but, for finer control, trees can be constructed directly from the classes and operations available. Nodes have structure and representation properties that can be helpful for examining the structure of generated trees.

Example

final f = Product(
   Constant(3),
   Power(
      Variable('x'),
      Constant(5),
   )
);

print('Built: $f\n');
print('Structure:\n');
print(f.structure);
print('\nRepresentation:\n');
print(f.representation);

Built: 3*x^5

Structure:

☉ Product
| ☉ Constant 3
| ☉ Power
| | ☉ Variable 'x'
| | ☉ Constant 5

Representation:

Product(Constant(3), Power(Variable('x'), Constant(5)))

When a root node is called, the result may have a different structure due to substitutions made during the call or restructuring carried out by dendrocas.

Example

final f = Product(
   Product(
      Constant(10),
      Product(
         Constant(-2),
         Variable('x'),
      ),
   ),
   Product(
      Constant(3),
      Variable('y'),
   ),
), g = f();

print('f = $f\n');
print('Structure:\n');
print(f.structure);
print('\ng = $g\n');
print('Structure:\n');
print(g.structure);

f = 10*(-2)*x*3*y

Structure:

☉ Product
| ☉ Product
| | ☉ Constant 10
| | ☉ Product
| | | ☉ Constant -2
| | | ☉ Variable 'x'
| ☉ Product
| | ☉ Constant 3
| | ☉ Variable 'y'

g = (-60)*x*y

Structure:

☉ Product
| ☉ Constant -60
| ☉ Product
| | ☉ Variable 'x'
| | ☉ Variable 'y'

Example

final f = Sum(
   Power(
      Sine(Variable('x')),
      Constant(2),
   ),
   Power(
      Cosine(Variable('x')),
      Constant(2),
   ),
);

final g = f();

print('$f = $g');

cos(x)^2+sin(x)^2 = 1

The same is true for trees created by applying operations.

Example

final
  one = 1.c,
  two = 2.c,
  three = 3.c,
  x = 'x'.v;

for (final tree in [
   one + two,
   two * three,
   three.power(two),
   x * x + two * x + three * x,
   one + x,
]) {
   print(tree);
   print(tree.structure);
   final restructured = tree();
   if (tree != restructured) {
      print('\nRestructured to: $restructured');
      print(restructured.structure);
   } else {
      print('\n(No restructuring.)');
   }
   print('\n${':' * 20}\n');
}

1+2
☉ Sum
| ☉ Constant 1
| ☉ Constant 2

Restructured to: 3
☉ Constant 3

::::::::::::::::::::

2*3
☉ Product
| ☉ Constant 2
| ☉ Constant 3

Restructured to: 6
☉ Constant 6

::::::::::::::::::::

3^2
☉ Power
| ☉ Constant 3
| ☉ Constant 2

Restructured to: 9
☉ Constant 9

::::::::::::::::::::

3*x+2*x+x*x
☉ Sum
| ☉ Product
| | ☉ Constant 3
| | ☉ Variable 'x'
| ☉ Sum
| | ☉ Product
| | | ☉ Constant 2
| | | ☉ Variable 'x'
| | ☉ Product
| | | ☉ Variable 'x'
| | | ☉ Variable 'x'

Restructured to: x^2+5*x
☉ Sum
| ☉ Power
| | ☉ Variable 'x'
| | ☉ Constant 2
| ☉ Product
| | ☉ Constant 5
| | ☉ Variable 'x'

::::::::::::::::::::

1+x
☉ Sum
| ☉ Constant 1
| ☉ Variable 'x'

(No restructuring.)

::::::::::::::::::::

(Trees created from string property tree are simplified automatically upon creation.)

Explicit Derivative Construction #

The derivative of a tree can be obtained through the derivative method (not to be confused with the derivative property of SVF), which takes in the variable with respect to perform differentiation and returns the root node of the constructed derivative tree.

Example

final x = 'x'.v,
  f = 'atan(x)'.t,
  df = f.derivative(x);

print('f($x) = $f');
print("f'($x) = $df");

f(x) = atan(x)
f'(x) = (1+x^2)^(-1)

For trees containing multiple variables, the derivative method returns a partial derivative.

Example

final a = 'a'.v,
  b = 'b'.v,
  f = 'a b^2 + a^2 b'.t;

print('    f = $f');
print('∂f/∂a = ${f.derivative(a)}');
print('∂f/∂b = ${f.derivative(b)}');

    f = a*b^2+b*a^2
∂f/∂a = b^2+2*a*b
∂f/∂b = a^2+2*a*b

Tree Traversal #

We can extract all nodes that meet a predicate from a tree using the allNodesWhere method on the root.

Example

final tree = '3x^2+2x*y-y^2'.tree;
print(tree.structure);
print('\nNodes: ${tree.nodeCount}, of which:');
print('  Projectors: ${tree.allNodesWhere((n) => n is Projector).length}');
print('    Branches: ${tree.allNodesWhere((n) => n is Branch).length}');
print('      Leaves: ${tree.allNodesWhere((n) => n is Leaf).length}');
print('\nDistinct variables: ${tree.variables}');

final sumOfConstants = tree
   .allNodesWhere((n) => n is Constant)
   .fold(Constant(0), (a, b) => (a + b)() as Constant);

print('Sum of constants: $sumOfConstants');

☉ Sum
| ☉ Product
| | ☉ Constant 2
| | ☉ Product
| | | ☉ Variable 'x'
| | | ☉ Variable 'y'
| ☉ Sum
| | ☉ Negative
| | | ☉ Power
| | | | ☉ Variable 'y'
| | | | ☉ Constant 2
| | ☉ Product
| | | ☉ Constant 3
| | | ☉ Power
| | | | ☉ Variable 'x'
| | | | ☉ Constant 2

Nodes: 16, of which:
  Projectors: 1
    Branches: 7
      Leaves: 8

Distinct variables: {x, y}
Sum of constants: 9

Parse Results & Debugging #

Dendrocas provides a parse function that, instead of throwing a ParseException, returns an instance of ParseResult, which is either Okay with the root node of the generated tree and a string description steps of the steps taken during the construction of the syntax tree, or ParseError containing an error message if the string used was invalid.

Example

final badString = '2 sin(x',
  result = parse(badString);

switch (result) {
  case Okay(node: final root, steps: final steps):
    print('Success; result: $root');
    print('\nSteps:');
    print(steps);
  case ParseError(message: final m):
    print('Failure!');
    print(m);
}

Failure!
Parentheses unbalanced.

final goodString = '2 sin(x)',
  result = parse(goodString);

switch (result) {
  case Okay(node: final root, steps: final steps):
    print('Success; result: $root');
    print('\nSteps:');
    print(steps);
  case ParseError(message: final m):
    print('Failure!');
    print(m);
}

Success; result: 2*sin(x)

Steps:

--- Shunting Yard ---

Expression received: "2 sin(x)"

Tokens identified:
   ╭─╮╭─╮╭─╮╭───╮╭──╮╭─╮╭─╮╭─╮
 # │(││2││*││sin││_(││x││)││)│
   ╰─╯╰─╯╰─╯╰───╯╰──╯╰─╯╰─╯╰─╯

   ╭─╮╭─╮╭───╮╭──╮╭─╮╭─╮╭─╮
 # │2││*││sin││_(││x││)││)│
   ╰─╯╰─╯╰───╯╰──╯╰─╯╰─╯╰─╯
╭─╮
│(│
╰─╯

╭─╮   ╭─╮╭───╮╭──╮╭─╮╭─╮╭─╮
│2│ # │*││sin││_(││x││)││)│
╰─╯   ╰─╯╰───╯╰──╯╰─╯╰─╯╰─╯
   ╭─╮
   │(│
   ╰─╯

╭─╮   ╭───╮╭──╮╭─╮╭─╮╭─╮
│2│ # │sin││_(││x││)││)│
╰─╯   ╰───╯╰──╯╰─╯╰─╯╰─╯
   ╭─╮
   │*│
   ╰─╯
   ╭─╮
   │(│
   ╰─╯

╭─╮   ╭──╮╭─╮╭─╮╭─╮
│2│ # │_(││x││)││)│
╰─╯   ╰──╯╰─╯╰─╯╰─╯
   ╭───╮
   │sin│
   ╰───╯
   ╭─╮
   │*│
   ╰─╯
   ╭─╮
   │(│
   ╰─╯

╭─╮   ╭─╮╭─╮╭─╮
│2│ # │x││)││)│
╰─╯   ╰─╯╰─╯╰─╯
   ╭──╮
   │_(│
   ╰──╯
   ╭───╮
   │sin│
   ╰───╯
   ╭─╮
   │*│
   ╰─╯
   ╭─╮
   │(│
   ╰─╯

╭─╮╭─╮   ╭─╮╭─╮
│2││x│ # │)││)│
╰─╯╰─╯   ╰─╯╰─╯
      ╭──╮
      │_(│
      ╰──╯
      ╭───╮
      │sin│
      ╰───╯
      ╭─╮
      │*│
      ╰─╯
      ╭─╮
      │(│
      ╰─╯

╭─╮╭─╮   ╭─╮
│2││x│ # │)│
╰─╯╰─╯   ╰─╯
      ╭───╮
      │sin│
      ╰───╯
      ╭─╮
      │*│
      ╰─╯
      ╭─╮
      │(│
      ╰─╯

╭─╮╭─╮╭───╮   ╭─╮
│2││x││sin│ # │)│
╰─╯╰─╯╰───╯   ╰─╯
           ╭─╮
           │*│
           ╰─╯
           ╭─╮
           │(│
           ╰─╯

╭─╮╭─╮╭───╮╭─╮   ╭─╮
│2││x││sin││*│ # │)│
╰─╯╰─╯╰───╯╰─╯   ╰─╯
              ╭─╮
              │(│
              ╰─╯

Postfix Tokens:
╭─╮╭─╮╭───╮╭─╮
│2││x││sin││*│
╰─╯╰─╯╰───╯╰─╯

Tree built from "2 sin(x)"
2*sin(x)

☉ Product
| ☉ Constant 2
| ☉ Sine
| | ☉ Variable 'x'

Nodes also have a mermaid property that generates the text for a mermaid illustration, which can be easier to view.

For example.

final tree = '3 log(x^2+1)'.t;
print('Structure:\n');
print(tree.structure);
print('\nMermaid:\n');
print(tree.mermaid);

Structure:

☉ Product
| ☉ Constant 3
| ☉ Logarithm
| | ☉ Sum
| | | ☉ Constant 1
| | | ☉ Power
| | | | ☉ Variable 'x'
| | | | ☉ Constant 2

Mermaid:

graph TB
1([Product]) --> 2((" 3 "))
1 --> 3([Logarithm]) --> 4([Sum]) --> 5((" 1 "))
4 --> 6([Power]) --> 7((" x "))
6 --> 8((" 2 "))

When the mermaid text above is wrapped in mermaid tags, we get the following illustration.

graph TB
1([Product]) --> 2((" 3 "))
1 --> 3([Logarithm]) --> 4([Sum]) --> 5((" 1 "))
4 --> 6([Power]) --> 7((" x "))
6 --> 8((" 2 "))

Expression Parsing Details #

Case #

Dendrocas is case insensitive; e.g. LOG(X) and log(x) mean the same thing.

Variable Names #

Variable names must start with a letter, but can contain digits and underscores; e.g. sin(x2) is fine, and means the sine of a variable called "x2".

Precedence & Associativity #

Dendrocas uses a simple order of operations: parentheses, then functions, then powers, then products and quotients, then sums and differences.

Points to note:

  • Powers are right-associative; e.g. x^2^3 means x^(2^3), not (x^2)^3.

  • Functions bind more tightly than powers; e.g. sin(x)^2 means (sin(x))^2, not sin(x^2).

  • Powers precede negation; e.g. -x^2 means -(x^2), not (-x)^2.

Implicit multiplication #

Dendrocas infers where multiplication is intended between adjacent factors; e.g. 2x means 2*x, x y means x*y (but xy means a variable with the name "xy").

Points to note:

  • The expression e can mean Euler's constant, but is also used for scientific notation; e.g. 5e+1 means 50, but 5e + 1 means 5*e+1.

  • Since variable names cannot start with digits, digits followed by a variable name are inferred to mean multiplication; e.g. 2x means 2*x, whereas x2 means a variable called "x2".

Expression Variations #

Some expressions are equivalent.

Points to note:

  • π and pi mean the same thing (so we cannot create a variable called "pi").

  • e^x and exp(x) mean the same thing (so we cannot create a variable called "e").

  • Powers can be expressed as an operator or a function; e.g. a^b and pow(a, b) mean the same thing.

  • Both expressions ln and log are mapped to the natural logarithm; e.g. ln(x) and log(x) mean the same thing. To construct a logarithm with a different base, use logb; e.g. logb(3, x) is the base-3 logarithm of a variable called "x".

Additional Strings Accepted #

Some strings expressions are accepted but not mapped directly to an underlying tree representation.

Points to note:

  • Brackets are accepted as a convenience, but mean the same thing as parentheses; e.g. sin[exp(x)] means sin(exp(x)).

  • The absolute value function does not have an underlying node representation; e.g. abs(x) constructs the following tree.

graph TB
1([SquareRoot]) --> 2([Power]) --> 3((" x "))
2 --> 4((" 2 "))

The Logarithm node represents the natural logarithm. Both strings "log" and "ln" are mapped to this node. For other bases, we can use the expression "logb(b, x)", which means the base b logarithm of x.

For example, "logb(10, x)" constructs the following tree, restructured from "log(x)/log(10)":

graph TB
1([Product]) --> 2([" 0.4342944819032 "])
1 --> 3([Logarithm]) --> 4((" x "))

Out-of-domain Values #

A ParseException is thrown when an attempt to parse a string fails for any reason. If a node representing a function is called on an out-of-domain value, a ParseException is not thrown (because parsing succeeded), but a Constant whose wrapped value is double.nan is returned.

Example

final a = 'log(-1)'.c;
print('a: $a');
print('a.value: ${a.value}');

a: Undefined
a.value: NaN

Similarly, instances of Constant wrapping double.infinity and double.negativeInfinity are returned for function calls.

Example

final a = 'log(0)'.c, b = '-log(0)'.c;
print('a: $a; a.value: ${a.value}');
print('b: $b; b.value: ${b.value}');

a: NegativeInfinity; a.value: -Infinity
b: Infinity; b.value: Infinity

Instances of SVF will return double.NaN, double.infinity and -double.infinity in analogous cases.

In general, the results returned by node and SVF calls match what we would expect from analogous dart:math function calls, but where Dendrocas can recognize a function has been called on an out-of-domain value, the dart:math behavior is overridden.

Example

{
   print('Using dart:math...');
   final x0 = math.pi / 2;
   print('tan($x0) = ${math.tan(x0)}');
   print('... should be undefined!');
}

{
   print('\nUsing a dendrocas SVF...');
   final tan = 'tan(x)'.svf,
     x0 = math.pi / 2;
   print('tan($x0) = ${tan(x0)}');
   print('... overrides dart:math, returns double.nan.');
}

{
   print('\nUsing a dendrocas tree...');
   final x = 'x'.v,
      tan = 'tan(x)'.t,
      x0 = 'pi/2'.c;
   print('tan($x0) = ${tan({x: x0})}');
   print('... returns "Undefined" instance of Constant.');
}


Using dart:math...
tan(1.5707963267948966) = 16331239353195370.0
... should be undefined!

Using a dendrocas SVF...
tan(1.5707963267948966) = NaN
... overrides dart:math, returns double.nan.

Using a dendrocas tree...
tan(1.5707963267949) = Undefined
... returns "Undefined" instance of Constant.

Single Variable Functions & Trees #

The SVF class is a light wrapper over a syntax tree (i.e. a root Node) to address a common use case, namely constructing mathematical functions from strings. Here is a comparison between the two classes:

SVF Node
Usual Instantiation Via the svf property on String. Via the c, t and v properties on String (and the c property on num).
call Accepts a num, returns a double. Accepts an optional mapping of variables to substitutions (Map<Variable, Node>), returns a Node to a simplified tree after the respective substitutions have been made.
derivative A property that returns an SVF wrapping the derivative. A method that accepts a Variable and returns a derivative with respect to that variable as a Node.
Operations Cannot be operated upon or passed directly as arguments during node construction (though its property root can). Can be operated on using +, -, *, / and the pow method, used in substitutions and passed as arguments during node construction.

Dendrocas and Function-Tree #

Dendrocas is a rewrite-from-scratch of the package function_tree. Function-tree was a little hack thrown together to meet a need in another project and not very carefully designed or thought through, which made debugging difficult and adding new features prone to breaking existing behavior. With dendrocas, more effort has been given to improving modularity, designation of responsibility, self-documentation and testing. Compared to function-tree, dendrocas is a little more careful with string parsing and generally yields more simplified, shallower trees.

Disclosure: Use of AI #

While dendrocas was lovingly (well, mostly lovingly) coded by a human, the public facing Qwen and DeepSeek LLMs were extensively used in chat sessions not connected to the file system to check mathematical identities, catch edge cases, double-check implementations in code excerpts, and generate test scripts (see the test directory), and Claude was used to assist with code review prior to publication.

Thanks! #

Thanks for your interest in this project! Please submit any bug reports here.

← Metadata

0
likes
160
points
35
downloads

Documentation

API reference

Publisher

unverified uploader

Weekly Downloads

Metadata

A little CAS for building callable mathematical syntax trees from strings.

Repository (GitHub)
View/report issues

License

MIT (license)

More

Packages that depend on dendrocas

Back