expression_trees.md (16972B)
1 # Expression trees 2 3 When parsing an expression via `math.parse(expr)`, math.js generates an 4 expression tree and returns the root node of the tree. An expression tree can 5 be used to analyze, manipulate, and evaluate expressions. 6 7 Example: 8 9 ```js 10 const node = math.parse('sqrt(2 + x)') 11 ``` 12 13 In this case, the expression `sqrt(2 + x)` is parsed as: 14 15 ``` 16 FunctionNode sqrt 17 | 18 OperatorNode + 19 / \ 20 ConstantNode 2 x SymbolNode 21 ``` 22 23 Alternatively, this expression tree can be build by manually creating nodes: 24 25 ```js 26 const node1 = new math.ConstantNode(2) 27 const node2 = new math.SymbolNode('x') 28 const node3 = new math.OperatorNode('+', 'add', [node1, node2]) 29 const node4 = new math.FunctionNode('sqrt', [node3]) 30 ``` 31 32 The resulting expression tree with root node `node4` is equal to the expression 33 tree generated by `math.parse('sqrt(2 + x)')`. 34 35 36 ## API 37 38 ### Methods 39 40 All nodes have the following methods: 41 42 - `clone() : Node` 43 44 Create a shallow clone of the node. 45 The node itself is cloned, its childs are not cloned. 46 47 - `cloneDeep() : Node` 48 49 Create a deep clone of the node. 50 Both the node as well as all its childs are cloned recursively. 51 52 - `compile() : Object` 53 54 Compile an expression into optimized JavaScript code. `compile` returns an 55 object with a function `evaluate([scope])` to evaluate. Example: 56 57 ```js 58 const node = math.parse('2 + x') // returns the root Node of an expression tree 59 const code = node.compile() // returns {evaluate: function (scope) {...}} 60 const evaluate = code.evaluate({x: 3}) // returns 5 61 ``` 62 63 - `evaluate([scope]) : Object` 64 65 Compile and evaluate an expression, this is the equivalent of doing 66 `node.compile().evaluate(scope)`. Example: 67 68 ```js 69 const node = math.parse('2 + x') // returns the root Node of an expression tree 70 const evaluate = node.evaluate({x: 3}) // returns 5 71 ``` 72 73 - `equals(other: Node) : boolean` 74 75 Test whether this node equals an other node. Does a deep comparison of the 76 values of both nodes. 77 78 - `filter(callback: function) : Node[]` 79 80 Recursively filter nodes in an expression tree. The `callback` function is 81 called as `callback(node: Node, path: string, parent: Node) : boolean` for 82 every node in the tree, and must return a boolean. The function `filter` 83 returns an array with nodes for which the test returned true. 84 Parameter `path` is a string containing a relative JSON Path. 85 86 Example: 87 88 ```js 89 const node = math.parse('x^2 + x/4 + 3*y') 90 const filtered = node.filter(function (node) { 91 return node.isSymbolNode && node.name === 'x' 92 }) 93 // returns an array with two entries: two SymbolNodes 'x' 94 ``` 95 96 - `forEach(callback: function) : Node[]` 97 98 Execute a callback for each of the child nodes of this node. The `callback` 99 function is called as `callback(child: Node, path: string, parent: Node)`. 100 Parameter `path` is a string containing a relative JSON Path. 101 102 See also `traverse`, which is a recursive version of `forEach`. 103 104 Example: 105 106 ```js 107 const node = math.parse('3 * x + 2') 108 node.forEach(function (node, path, parent) { 109 switch (node.type) { 110 case 'OperatorNode': 111 console.log(node.type, node.op) 112 break 113 case 'ConstantNode': 114 console.log(node.type, node.value) 115 break 116 case 'SymbolNode': 117 console.log(node.type, node.name) 118 break 119 default: 120 console.log(node.type) 121 } 122 }) 123 // outputs: 124 // OperatorNode * 125 // ConstantNode 2 126 ``` 127 128 - `map(callback: function) : Node[]` 129 130 Transform a node. Creates a new Node having it's childs be the results of 131 calling the provided callback function for each of the childs of the original 132 node. The `callback` function is called as `callback(child: Node, path: string, 133 parent: Node)` and must return a Node. Parameter `path` is a string containing 134 a relative JSON Path. 135 136 See also `transform`, which is a recursive version of `map`. 137 138 - `toHTML(options: object): string` 139 140 Get a HTML representation of the parsed expression. Example: 141 142 ```js 143 const node = math.parse('sqrt(2/3)') 144 node.toHTML() 145 // returns 146 // <span class="math-function">sqrt</span> 147 // <span class="math-paranthesis math-round-parenthesis">(</span> 148 // <span class="math-number">2</span> 149 // <span class="math-operator math-binary-operator math-explicit-binary-operator">/</span> 150 // <span class="math-number">3</span> 151 // <span class="math-paranthesis math-round-parenthesis">)</span> 152 ``` 153 154 Information about the available HTML classes in [HTML Classes](html_classes.md). 155 Information about the options in [Customization](customization.md#custom-html-latex-and-string-output). 156 157 - `toString(options: object) : string` 158 159 Get a string representation of the parsed expression. This is not exactly 160 the same as the original input. Example: 161 162 ```js 163 const node = math.parse('3+4*2') 164 node.toString() // returns '3 + (4 * 2)' 165 ``` 166 167 Information about the options in [Customization](customization.md#custom-html-latex-and-string-output). 168 169 - `toTex(options: object): string` 170 171 Get a [LaTeX](https://en.wikipedia.org/wiki/LaTeX) representation of the 172 expression. Example: 173 174 ```js 175 const node = math.parse('sqrt(2/3)') 176 node.toTex() // returns '\sqrt{\frac{2}{3}}' 177 ``` 178 179 Information about the options in [Customization](customization.md#custom-html-latex-and-string-output). 180 181 - `transform(callback: function)` 182 183 Recursively transform an expression tree via a transform function. Similar 184 to `Array.map`, but recursively executed on all nodes in the expression tree. 185 The callback function is a mapping function accepting a node, and returning 186 a replacement for the node or the original node. Function `callback` is 187 called as `callback(node: Node, path: string, parent: Node)` for every node 188 in the tree, and must return a `Node`. Parameter `path` is a string containing 189 a relative JSON Path. 190 191 The transform function will stop iterating when a node is replaced by the 192 callback function, it will not iterate over replaced nodes. 193 194 For example, to replace all nodes of type `SymbolNode` having name 'x' with a 195 ConstantNode with value `3`: 196 197 ```js 198 const node = math.parse('x^2 + 5*x') 199 const transformed = node.transform(function (node, path, parent) { 200 if (node.isSymbolNode && node.name === 'x') { 201 return new math.ConstantNode(3) 202 } 203 else { 204 return node 205 } 206 }) 207 transformed.toString() // returns '3 ^ 2 + 5 * 3' 208 ``` 209 210 - `traverse(callback)` 211 212 Recursively traverse all nodes in a node tree. Executes given callback for 213 this node and each of its child nodes. Similar to `Array.forEach`, except 214 recursive. 215 The callback function is a mapping function accepting a node, and returning 216 a replacement for the node or the original node. Function `callback` is 217 called as `callback(node: Node, path: string, parent: Node)` for every node 218 in the tree. Parameter `path` is a string containing a relative JSON Path. 219 Example: 220 221 ```js 222 const node = math.parse('3 * x + 2') 223 node.traverse(function (node, path, parent) { 224 switch (node.type) { 225 case 'OperatorNode': 226 console.log(node.type, node.op) 227 break 228 case 'ConstantNode': 229 console.log(node.type, node.value) 230 break 231 case 'SymbolNode': 232 console.log(node.type, node.name) 233 break 234 default: 235 console.log(node.type) 236 } 237 }) 238 // outputs: 239 // OperatorNode + 240 // OperatorNode * 241 // ConstantNode 3 242 // SymbolNode x 243 // ConstantNode 2 244 ``` 245 246 247 ### Properties 248 249 Each `Node` has the following properties: 250 251 - `comment: string` 252 253 A string holding a comment if there was any in the expression, or else the 254 string will be empty string. A comment can be attached to the root node of 255 an expression or to each of the childs nodes of a `BlockNode`. 256 257 - `isNode: true` 258 259 Is defined with value `true` on Nodes. Additionally, each type of node 260 adds it's own flag, for example a `SymbolNode` as has a property 261 `isSymbolNode: true`. 262 263 - `type: string` 264 265 The type of the node, for example `'SymbolNode'` in case of a `SymbolNode`. 266 267 268 ## Nodes 269 270 math.js has the following types of nodes. All nodes are available at the 271 namespace `math`. 272 273 274 ### AccessorNode 275 276 Construction: 277 278 ``` 279 new AccessorNode(object: Node, index: IndexNode) 280 ``` 281 282 Properties: 283 284 - `object: Node` 285 - `index: IndexNode` 286 - `name: string` (read-only) The function or method name. Returns an empty string when undefined. 287 288 Examples: 289 290 ```js 291 const node1 = math.parse('a[3]') 292 293 const object = new math.SymbolNode('a') 294 const index = new math.IndexNode([3]) 295 const node2 = new math.AccessorNode(object, index) 296 ``` 297 298 299 ### ArrayNode 300 301 Construction: 302 303 ``` 304 new ArrayNode(items: Node[]) 305 ``` 306 307 Properties: 308 309 - `items: Node[]` 310 311 Examples: 312 313 ```js 314 const node1 = math.parse('[1, 2, 3]') 315 316 const one = new math.ConstantNode(1) 317 const two = new math.ConstantNode(2) 318 const three = new math.ConstantNode(3) 319 const node2 = new math.ArrayNode([one, two, three]) 320 ``` 321 322 323 ### AssignmentNode 324 325 Construction: 326 327 ``` 328 new AssignmentNode(object: SymbolNode, value: Node) 329 new AssignmentNode(object: SymbolNode | AccessorNode, index: IndexNode, value: Node) 330 ``` 331 332 Properties: 333 334 - `object: SymbolNode | AccessorNode` 335 - `index: IndexNode | null` 336 - `value: Node` 337 - `name: string` (read-only) The function or method name. Returns an empty string when undefined. 338 339 Examples: 340 341 ```js 342 const node1 = math.parse('a = 3') 343 344 const object = new math.SymbolNode('a') 345 const value = new math.ConstantNode(3) 346 const node2 = new math.AssignmentNode(object, value) 347 ``` 348 349 350 ### BlockNode 351 352 A `BlockNode` is created when parsing a multi line expression like `a=2;b=3` or 353 `a=2\nb=3`. Evaluating a `BlockNode` returns a `ResultSet`. The results can be 354 retrieved via `ResultSet.entries` or `ResultSet.valueOf()`, which contains 355 an `Array` with the results of the visible lines (i.e. lines not ending with 356 a semicolon). 357 358 Construction: 359 360 ``` 361 block = new BlockNode(Array.<{node: Node} | {node: Node, visible: boolean}>) 362 ``` 363 364 Properties: 365 366 - `blocks: Array.<{node: Node, visible: boolean}>` 367 368 Examples: 369 370 ```js 371 const block1 = math.parse('a=1; b=2; c=3') 372 373 const a = new math.SymbolNode('a') 374 const one = new math.ConstantNode(1) 375 const ass1 = new math.AssignmentNode(a, one) 376 377 const b = new math.SymbolNode('b') 378 const two = new math.ConstantNode(2) 379 const ass2 = new math.AssignmentNode(b, two) 380 381 const c = new math.SymbolNode('c') 382 const three = new math.ConstantNode(3) 383 const ass3 = new math.AssignmentNode(c, three) 384 385 const block2 = new BlockNode([ 386 {node: ass1, visible: false}, 387 {node: ass2, visible: false}, 388 {node: ass3, visible: true} 389 ]) 390 ``` 391 392 393 ### ConditionalNode 394 395 Construction: 396 397 ``` 398 new ConditionalNode(condition: Node, trueExpr: Node, falseExpr: Node) 399 ``` 400 401 Properties: 402 403 - `condition: Node` 404 - `trueExpr: Node` 405 - `falseExpr: Node` 406 407 Examples: 408 409 ```js 410 const node1 = math.parse('a > 0 ? a : -a') 411 412 const a = new math.SymbolNode('a') 413 const zero = new math.ConstantNode(0) 414 const condition = new math.OperatorNode('>', 'larger', [a, zero]) 415 const trueExpr = a 416 const falseExpr = new math.OperatorNode('-', 'unaryMinus', [a]) 417 const node2 = new math.ConditionalNode(condition, trueExpr, falseExpr) 418 ``` 419 420 ### ConstantNode 421 422 Construction: 423 424 ``` 425 new ConstantNode(value: *) 426 ``` 427 428 Properties: 429 430 - `value: *` 431 432 Examples: 433 434 ```js 435 const node1 = math.parse('2.4') 436 437 const node2 = new math.ConstantNode(2.4) 438 const node3 = new math.ConstantNode('foo') 439 ``` 440 441 442 ### FunctionAssignmentNode 443 444 Construction: 445 446 ``` 447 new FunctionAssignmentNode(name: string, params: string[], expr: Node) 448 ``` 449 450 Properties: 451 452 - `name: string` 453 - `params: string[]` 454 - `expr: Node` 455 456 Examples: 457 458 ```js 459 const node1 = math.parse('f(x) = x^2') 460 461 const x = new math.SymbolNode('x') 462 const two = new math.ConstantNode(2) 463 const expr = new math.OperatorNode('^', 'pow', [x, 2]) 464 const node2 = new math.FunctionAssignmentNode('f', ['x'], expr) 465 ``` 466 467 468 ### FunctionNode 469 470 Construction: 471 472 ``` 473 new FunctionNode(fn: Node | string, args: Node[]) 474 ``` 475 476 Properties: 477 478 - `fn: Node | string` (read-only) The object or function name which to invoke. 479 - `args: Node[]` 480 481 Examples: 482 483 ```js 484 const node1 = math.parse('sqrt(4)') 485 486 const four = new math.ConstantNode(4) 487 const node3 = new math.FunctionNode(new SymbolNode('sqrt'), [four]) 488 ``` 489 490 491 ### IndexNode 492 493 Construction: 494 495 ``` 496 new IndexNode(dimensions: Node[]) 497 new IndexNode(dimensions: Node[], dotNotation: boolean) 498 ``` 499 500 Each dimension can be a single value, a range, or a property. The values of 501 indices are one-based, including range end. 502 503 An optional property `dotNotation` can be provided describing whether this index 504 was written using dot notation like `a.b`, or using bracket notation 505 like `a["b"]`. Default value is `false`. This information is used when 506 stringifying the IndexNode. 507 508 Properties: 509 510 - `dimensions: Node[]` 511 - `dotNotation: boolean` 512 513 Examples: 514 515 ```js 516 const node1 = math.parse('A[1:3, 2]') 517 518 const A = new math.SymbolNode('A') 519 const one = new math.ConstantNode(1) 520 const two = new math.ConstantNode(2) 521 const three = new math.ConstantNode(3) 522 523 const range = new math.RangeNode(one, three) 524 const index = new math.IndexNode([range, two]) 525 const node2 = new math.AccessNode(A, index) 526 ``` 527 528 ### ObjectNode 529 530 Construction: 531 532 ``` 533 new ObjectNode(properties: Object.<string, Node>) 534 ``` 535 536 Properties: 537 538 - `properties: Object.<string, Node>` 539 540 Examples: 541 542 ```js 543 const node1 = math.parse('{a: 1, b: 2, c: 3}') 544 545 const a = new math.ConstantNode(1) 546 const b = new math.ConstantNode(2) 547 const c = new math.ConstantNode(3) 548 const node2 = new math.ObjectNode({a: a, b: b, c: c}) 549 ``` 550 551 552 ### OperatorNode 553 554 Construction: 555 556 ``` 557 new OperatorNode(op: string, fn: string, args: Node[], implicit: boolean = false) 558 ``` 559 560 Additional methods: 561 562 - `isUnary() : boolean` 563 564 Returns true when the `OperatorNode` contains exactly one argument, 565 like with a unary minus: 566 567 ```js 568 const a = new math.ConstantNode(2) 569 const b = new math.OperatorNode('-', 'unaryMinus', [a]) 570 b.isUnary() // true 571 ``` 572 573 - `isBinary() : boolean` 574 575 Returns true when the `OperatorNode` contains exactly two arguments, 576 like with most regular operators: 577 578 ```js 579 const a = new math.ConstantNode(2) 580 const b = new math.ConstantNode(3) 581 const c = new math.OperatorNode('+', 'add', [a, b]) 582 c.isBinary() // true 583 ``` 584 585 Properties: 586 587 - `op: string` 588 - `fn: string` 589 - `args: Node[]` 590 - `implicit: boolean` True in case of an implicit multiplication, false otherwise 591 592 Examples: 593 594 ```js 595 const node1 = math.parse('2.3 + 5') 596 597 const a = new math.ConstantNode(2.3) 598 const b = new math.ConstantNode(5) 599 const node2 = new math.OperatorNode('+', 'add', [a, b]) 600 ``` 601 602 ### ParenthesisNode 603 604 Construction: 605 606 ``` 607 new ParenthesisNode(content: Node) 608 ``` 609 610 Properties: 611 612 - `content: Node` 613 614 Examples: 615 616 ```js 617 const node1 = math.parse('(1)') 618 619 const a = new math.ConstantNode(1) 620 const node2 = new math.ParenthesisNode(a) 621 ``` 622 623 ### RangeNode 624 625 Construction: 626 627 ``` 628 new RangeNode(start: Node, end: Node [, step: Node]) 629 ``` 630 631 Properties: 632 633 - `start: Node` 634 - `end: Node` 635 - `step: Node | null` 636 637 Examples: 638 639 ```js 640 const node1 = math.parse('1:10') 641 const node2 = math.parse('0:2:10') 642 643 const zero = new math.ConstantNode(0) 644 const one = new math.ConstantNode(1) 645 const two = new math.ConstantNode(2) 646 const ten = new math.ConstantNode(10) 647 648 const node3 = new math.RangeNode(one, ten) 649 const node4 = new math.RangeNode(zero, ten, two) 650 ``` 651 652 ### RelationalNode 653 654 Construction: 655 656 ``` 657 new RelationalNode(conditionals: string[], params: Node[]) 658 ``` 659 660 `conditionals` is an array of strings, each of which may be 'smaller', 'larger', 'smallerEq', 'largerEq', 'equal', or 'unequal'. The `conditionals` array must contain exactly one fewer item than `params`. 661 662 Properties: 663 664 - `conditionals: string[]` 665 - `params: Node[]` 666 667 A `RelationalNode` efficiently represents a chained conditional expression with two or more comparison operators, such as `10 < x <= 50`. The expression is equivalent to `10 < x and x <= 50`, except that `x` is evaluated only once, and evaluation stops (is "short-circuited") once any condition tests false. Operators that are subject to chaining are `<`, `>`, `<=`, `>=`, `==`, and `!=`. For backward compatibility, `math.parse` will return an `OperatorNode` if only a single conditional is present (such as `x > 2`). 668 669 Examples: 670 671 ```js 672 673 const ten = new math.ConstantNode(10) 674 const x = new math.SymbolNode('x') 675 const fifty = new math.ConstantNode(50) 676 677 const node1 = new math.RelationalNode(['smaller', 'smallerEq'], [ten, x, fifty]) 678 const node2 = math.parse('10 < x <= 50') 679 ``` 680 681 682 ### SymbolNode 683 684 Construction: 685 686 ``` 687 new SymbolNode(name: string) 688 ``` 689 690 Properties: 691 692 - `name: string` 693 694 Examples: 695 696 ```js 697 const node = math.parse('x') 698 699 const x = new math.SymbolNode('x') 700 ```