rationalize.js 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823
  1. import { isInteger } from '../../utils/number.js';
  2. import { factory } from '../../utils/factory.js';
  3. var name = 'rationalize';
  4. var dependencies = ['config', 'typed', 'equal', 'isZero', 'add', 'subtract', 'multiply', 'divide', 'pow', 'parse', 'simplifyConstant', 'simplifyCore', 'simplify', '?bignumber', '?fraction', 'mathWithTransform', 'matrix', 'AccessorNode', 'ArrayNode', 'ConstantNode', 'FunctionNode', 'IndexNode', 'ObjectNode', 'OperatorNode', 'SymbolNode', 'ParenthesisNode'];
  5. export var createRationalize = /* #__PURE__ */factory(name, dependencies, _ref => {
  6. var {
  7. config,
  8. typed,
  9. equal,
  10. isZero,
  11. add,
  12. subtract,
  13. multiply,
  14. divide,
  15. pow,
  16. parse,
  17. simplifyConstant,
  18. simplifyCore,
  19. simplify,
  20. fraction,
  21. bignumber,
  22. mathWithTransform,
  23. matrix,
  24. AccessorNode,
  25. ArrayNode,
  26. ConstantNode,
  27. FunctionNode,
  28. IndexNode,
  29. ObjectNode,
  30. OperatorNode,
  31. SymbolNode,
  32. ParenthesisNode
  33. } = _ref;
  34. /**
  35. * Transform a rationalizable expression in a rational fraction.
  36. * If rational fraction is one variable polynomial then converts
  37. * the numerator and denominator in canonical form, with decreasing
  38. * exponents, returning the coefficients of numerator.
  39. *
  40. * Syntax:
  41. *
  42. * rationalize(expr)
  43. * rationalize(expr, detailed)
  44. * rationalize(expr, scope)
  45. * rationalize(expr, scope, detailed)
  46. *
  47. * Examples:
  48. *
  49. * math.rationalize('sin(x)+y')
  50. * // Error: There is an unsolved function call
  51. * math.rationalize('2x/y - y/(x+1)')
  52. * // (2*x^2-y^2+2*x)/(x*y+y)
  53. * math.rationalize('(2x+1)^6')
  54. * // 64*x^6+192*x^5+240*x^4+160*x^3+60*x^2+12*x+1
  55. * math.rationalize('2x/( (2x-1) / (3x+2) ) - 5x/ ( (3x+4) / (2x^2-5) ) + 3')
  56. * // -20*x^4+28*x^3+104*x^2+6*x-12)/(6*x^2+5*x-4)
  57. * math.rationalize('x/(1-x)/(x-2)/(x-3)/(x-4) + 2x/ ( (1-2x)/(2-3x) )/ ((3-4x)/(4-5x) )') =
  58. * // (-30*x^7+344*x^6-1506*x^5+3200*x^4-3472*x^3+1846*x^2-381*x)/
  59. * // (-8*x^6+90*x^5-383*x^4+780*x^3-797*x^2+390*x-72)
  60. *
  61. * math.rationalize('x+x+x+y',{y:1}) // 3*x+1
  62. * math.rationalize('x+x+x+y',{}) // 3*x+y
  63. *
  64. * const ret = math.rationalize('x+x+x+y',{},true)
  65. * // ret.expression=3*x+y, ret.variables = ["x","y"]
  66. * const ret = math.rationalize('-2+5x^2',{},true)
  67. * // ret.expression=5*x^2-2, ret.variables = ["x"], ret.coefficients=[-2,0,5]
  68. *
  69. * See also:
  70. *
  71. * simplify
  72. *
  73. * @param {Node|string} expr The expression to check if is a polynomial expression
  74. * @param {Object|boolean} optional scope of expression or true for already evaluated rational expression at input
  75. * @param {Boolean} detailed optional True if return an object, false if return expression node (default)
  76. *
  77. * @return {Object | Node} The rational polynomial of `expr` or an object
  78. * `{expression, numerator, denominator, variables, coefficients}`, where
  79. * `expression` is a `Node` with the node simplified expression,
  80. * `numerator` is a `Node` with the simplified numerator of expression,
  81. * `denominator` is a `Node` or `boolean` with the simplified denominator or `false` (if there is no denominator),
  82. * `variables` is an array with variable names,
  83. * and `coefficients` is an array with coefficients of numerator sorted by increased exponent
  84. * {Expression Node} node simplified expression
  85. *
  86. */
  87. function _rationalize(expr) {
  88. var scope = arguments.length > 1 && arguments[1] !== undefined ? arguments[1] : {};
  89. var detailed = arguments.length > 2 && arguments[2] !== undefined ? arguments[2] : false;
  90. var setRules = rulesRationalize(); // Rules for change polynomial in near canonical form
  91. var polyRet = polynomial(expr, scope, true, setRules.firstRules); // Check if expression is a rationalizable polynomial
  92. var nVars = polyRet.variables.length;
  93. var noExactFractions = {
  94. exactFractions: false
  95. };
  96. var withExactFractions = {
  97. exactFractions: true
  98. };
  99. expr = polyRet.expression;
  100. if (nVars >= 1) {
  101. // If expression in not a constant
  102. expr = expandPower(expr); // First expand power of polynomials (cannot be made from rules!)
  103. var sBefore; // Previous expression
  104. var rules;
  105. var eDistrDiv = true;
  106. var redoInic = false;
  107. // Apply the initial rules, including succ div rules:
  108. expr = simplify(expr, setRules.firstRules, {}, noExactFractions);
  109. var s;
  110. while (true) {
  111. // Alternate applying successive division rules and distr.div.rules
  112. // until there are no more changes:
  113. rules = eDistrDiv ? setRules.distrDivRules : setRules.sucDivRules;
  114. expr = simplify(expr, rules, {}, withExactFractions);
  115. eDistrDiv = !eDistrDiv; // Swap between Distr.Div and Succ. Div. Rules
  116. s = expr.toString();
  117. if (s === sBefore) {
  118. break; // No changes : end of the loop
  119. }
  120. redoInic = true;
  121. sBefore = s;
  122. }
  123. if (redoInic) {
  124. // Apply first rules again without succ div rules (if there are changes)
  125. expr = simplify(expr, setRules.firstRulesAgain, {}, noExactFractions);
  126. }
  127. // Apply final rules:
  128. expr = simplify(expr, setRules.finalRules, {}, noExactFractions);
  129. } // NVars >= 1
  130. var coefficients = [];
  131. var retRationalize = {};
  132. if (expr.type === 'OperatorNode' && expr.isBinary() && expr.op === '/') {
  133. // Separate numerator from denominator
  134. if (nVars === 1) {
  135. expr.args[0] = polyToCanonical(expr.args[0], coefficients);
  136. expr.args[1] = polyToCanonical(expr.args[1]);
  137. }
  138. if (detailed) {
  139. retRationalize.numerator = expr.args[0];
  140. retRationalize.denominator = expr.args[1];
  141. }
  142. } else {
  143. if (nVars === 1) {
  144. expr = polyToCanonical(expr, coefficients);
  145. }
  146. if (detailed) {
  147. retRationalize.numerator = expr;
  148. retRationalize.denominator = null;
  149. }
  150. }
  151. // nVars
  152. if (!detailed) return expr;
  153. retRationalize.coefficients = coefficients;
  154. retRationalize.variables = polyRet.variables;
  155. retRationalize.expression = expr;
  156. return retRationalize;
  157. }
  158. return typed(name, {
  159. Node: _rationalize,
  160. 'Node, boolean': (expr, detailed) => _rationalize(expr, {}, detailed),
  161. 'Node, Object': _rationalize,
  162. 'Node, Object, boolean': _rationalize
  163. }); // end of typed rationalize
  164. /**
  165. * Function to simplify an expression using an optional scope and
  166. * return it if the expression is a polynomial expression, i.e.
  167. * an expression with one or more variables and the operators
  168. * +, -, *, and ^, where the exponent can only be a positive integer.
  169. *
  170. * Syntax:
  171. *
  172. * polynomial(expr,scope,extended, rules)
  173. *
  174. * @param {Node | string} expr The expression to simplify and check if is polynomial expression
  175. * @param {object} scope Optional scope for expression simplification
  176. * @param {boolean} extended Optional. Default is false. When true allows divide operator.
  177. * @param {array} rules Optional. Default is no rule.
  178. *
  179. *
  180. * @return {Object}
  181. * {Object} node: node simplified expression
  182. * {Array} variables: variable names
  183. */
  184. function polynomial(expr, scope, extended, rules) {
  185. var variables = [];
  186. var node = simplify(expr, rules, scope, {
  187. exactFractions: false
  188. }); // Resolves any variables and functions with all defined parameters
  189. extended = !!extended;
  190. var oper = '+-*' + (extended ? '/' : '');
  191. recPoly(node);
  192. var retFunc = {};
  193. retFunc.expression = node;
  194. retFunc.variables = variables;
  195. return retFunc;
  196. // -------------------------------------------------------------------------------------------------------
  197. /**
  198. * Function to simplify an expression using an optional scope and
  199. * return it if the expression is a polynomial expression, i.e.
  200. * an expression with one or more variables and the operators
  201. * +, -, *, and ^, where the exponent can only be a positive integer.
  202. *
  203. * Syntax:
  204. *
  205. * recPoly(node)
  206. *
  207. *
  208. * @param {Node} node The current sub tree expression in recursion
  209. *
  210. * @return nothing, throw an exception if error
  211. */
  212. function recPoly(node) {
  213. var tp = node.type; // node type
  214. if (tp === 'FunctionNode') {
  215. // No function call in polynomial expression
  216. throw new Error('There is an unsolved function call');
  217. } else if (tp === 'OperatorNode') {
  218. if (node.op === '^') {
  219. // TODO: handle negative exponents like in '1/x^(-2)'
  220. if (node.args[1].type !== 'ConstantNode' || !isInteger(parseFloat(node.args[1].value))) {
  221. throw new Error('There is a non-integer exponent');
  222. } else {
  223. recPoly(node.args[0]);
  224. }
  225. } else {
  226. if (oper.indexOf(node.op) === -1) {
  227. throw new Error('Operator ' + node.op + ' invalid in polynomial expression');
  228. }
  229. for (var i = 0; i < node.args.length; i++) {
  230. recPoly(node.args[i]);
  231. }
  232. } // type of operator
  233. } else if (tp === 'SymbolNode') {
  234. var _name = node.name; // variable name
  235. var pos = variables.indexOf(_name);
  236. if (pos === -1) {
  237. // new variable in expression
  238. variables.push(_name);
  239. }
  240. } else if (tp === 'ParenthesisNode') {
  241. recPoly(node.content);
  242. } else if (tp !== 'ConstantNode') {
  243. throw new Error('type ' + tp + ' is not allowed in polynomial expression');
  244. }
  245. } // end of recPoly
  246. } // end of polynomial
  247. // ---------------------------------------------------------------------------------------
  248. /**
  249. * Return a rule set to rationalize an polynomial expression in rationalize
  250. *
  251. * Syntax:
  252. *
  253. * rulesRationalize()
  254. *
  255. * @return {array} rule set to rationalize an polynomial expression
  256. */
  257. function rulesRationalize() {
  258. var oldRules = [simplifyCore,
  259. // sCore
  260. {
  261. l: 'n+n',
  262. r: '2*n'
  263. }, {
  264. l: 'n+-n',
  265. r: '0'
  266. }, simplifyConstant,
  267. // sConstant
  268. {
  269. l: 'n*(n1^-1)',
  270. r: 'n/n1'
  271. }, {
  272. l: 'n*n1^-n2',
  273. r: 'n/n1^n2'
  274. }, {
  275. l: 'n1^-1',
  276. r: '1/n1'
  277. }, {
  278. l: 'n*(n1/n2)',
  279. r: '(n*n1)/n2'
  280. }, {
  281. l: '1*n',
  282. r: 'n'
  283. }];
  284. var rulesFirst = [{
  285. l: '(-n1)/(-n2)',
  286. r: 'n1/n2'
  287. },
  288. // Unary division
  289. {
  290. l: '(-n1)*(-n2)',
  291. r: 'n1*n2'
  292. },
  293. // Unary multiplication
  294. {
  295. l: 'n1--n2',
  296. r: 'n1+n2'
  297. },
  298. // '--' elimination
  299. {
  300. l: 'n1-n2',
  301. r: 'n1+(-n2)'
  302. },
  303. // Subtraction turn into add with un�ry minus
  304. {
  305. l: '(n1+n2)*n3',
  306. r: '(n1*n3 + n2*n3)'
  307. },
  308. // Distributive 1
  309. {
  310. l: 'n1*(n2+n3)',
  311. r: '(n1*n2+n1*n3)'
  312. },
  313. // Distributive 2
  314. {
  315. l: 'c1*n + c2*n',
  316. r: '(c1+c2)*n'
  317. },
  318. // Joining constants
  319. {
  320. l: 'c1*n + n',
  321. r: '(c1+1)*n'
  322. },
  323. // Joining constants
  324. {
  325. l: 'c1*n - c2*n',
  326. r: '(c1-c2)*n'
  327. },
  328. // Joining constants
  329. {
  330. l: 'c1*n - n',
  331. r: '(c1-1)*n'
  332. },
  333. // Joining constants
  334. {
  335. l: 'v/c',
  336. r: '(1/c)*v'
  337. },
  338. // variable/constant (new!)
  339. {
  340. l: 'v/-c',
  341. r: '-(1/c)*v'
  342. },
  343. // variable/constant (new!)
  344. {
  345. l: '-v*-c',
  346. r: 'c*v'
  347. },
  348. // Inversion constant and variable 1
  349. {
  350. l: '-v*c',
  351. r: '-c*v'
  352. },
  353. // Inversion constant and variable 2
  354. {
  355. l: 'v*-c',
  356. r: '-c*v'
  357. },
  358. // Inversion constant and variable 3
  359. {
  360. l: 'v*c',
  361. r: 'c*v'
  362. },
  363. // Inversion constant and variable 4
  364. {
  365. l: '-(-n1*n2)',
  366. r: '(n1*n2)'
  367. },
  368. // Unary propagation
  369. {
  370. l: '-(n1*n2)',
  371. r: '(-n1*n2)'
  372. },
  373. // Unary propagation
  374. {
  375. l: '-(-n1+n2)',
  376. r: '(n1-n2)'
  377. },
  378. // Unary propagation
  379. {
  380. l: '-(n1+n2)',
  381. r: '(-n1-n2)'
  382. },
  383. // Unary propagation
  384. {
  385. l: '(n1^n2)^n3',
  386. r: '(n1^(n2*n3))'
  387. },
  388. // Power to Power
  389. {
  390. l: '-(-n1/n2)',
  391. r: '(n1/n2)'
  392. },
  393. // Division and Unary
  394. {
  395. l: '-(n1/n2)',
  396. r: '(-n1/n2)'
  397. }]; // Divisao and Unary
  398. var rulesDistrDiv = [{
  399. l: '(n1/n2 + n3/n4)',
  400. r: '((n1*n4 + n3*n2)/(n2*n4))'
  401. },
  402. // Sum of fractions
  403. {
  404. l: '(n1/n2 + n3)',
  405. r: '((n1 + n3*n2)/n2)'
  406. },
  407. // Sum fraction with number 1
  408. {
  409. l: '(n1 + n2/n3)',
  410. r: '((n1*n3 + n2)/n3)'
  411. }]; // Sum fraction with number 1
  412. var rulesSucDiv = [{
  413. l: '(n1/(n2/n3))',
  414. r: '((n1*n3)/n2)'
  415. },
  416. // Division simplification
  417. {
  418. l: '(n1/n2/n3)',
  419. r: '(n1/(n2*n3))'
  420. }];
  421. var setRules = {}; // rules set in 4 steps.
  422. // All rules => infinite loop
  423. // setRules.allRules =oldRules.concat(rulesFirst,rulesDistrDiv,rulesSucDiv)
  424. setRules.firstRules = oldRules.concat(rulesFirst, rulesSucDiv); // First rule set
  425. setRules.distrDivRules = rulesDistrDiv; // Just distr. div. rules
  426. setRules.sucDivRules = rulesSucDiv; // Jus succ. div. rules
  427. setRules.firstRulesAgain = oldRules.concat(rulesFirst); // Last rules set without succ. div.
  428. // Division simplification
  429. // Second rule set.
  430. // There is no aggregate expression with parentesis, but the only variable can be scattered.
  431. setRules.finalRules = [simplifyCore,
  432. // simplify.rules[0]
  433. {
  434. l: 'n*-n',
  435. r: '-n^2'
  436. },
  437. // Joining multiply with power 1
  438. {
  439. l: 'n*n',
  440. r: 'n^2'
  441. },
  442. // Joining multiply with power 2
  443. simplifyConstant,
  444. // simplify.rules[14] old 3rd index in oldRules
  445. {
  446. l: 'n*-n^n1',
  447. r: '-n^(n1+1)'
  448. },
  449. // Joining multiply with power 3
  450. {
  451. l: 'n*n^n1',
  452. r: 'n^(n1+1)'
  453. },
  454. // Joining multiply with power 4
  455. {
  456. l: 'n^n1*-n^n2',
  457. r: '-n^(n1+n2)'
  458. },
  459. // Joining multiply with power 5
  460. {
  461. l: 'n^n1*n^n2',
  462. r: 'n^(n1+n2)'
  463. },
  464. // Joining multiply with power 6
  465. {
  466. l: 'n^n1*-n',
  467. r: '-n^(n1+1)'
  468. },
  469. // Joining multiply with power 7
  470. {
  471. l: 'n^n1*n',
  472. r: 'n^(n1+1)'
  473. },
  474. // Joining multiply with power 8
  475. {
  476. l: 'n^n1/-n',
  477. r: '-n^(n1-1)'
  478. },
  479. // Joining multiply with power 8
  480. {
  481. l: 'n^n1/n',
  482. r: 'n^(n1-1)'
  483. },
  484. // Joining division with power 1
  485. {
  486. l: 'n/-n^n1',
  487. r: '-n^(1-n1)'
  488. },
  489. // Joining division with power 2
  490. {
  491. l: 'n/n^n1',
  492. r: 'n^(1-n1)'
  493. },
  494. // Joining division with power 3
  495. {
  496. l: 'n^n1/-n^n2',
  497. r: 'n^(n1-n2)'
  498. },
  499. // Joining division with power 4
  500. {
  501. l: 'n^n1/n^n2',
  502. r: 'n^(n1-n2)'
  503. },
  504. // Joining division with power 5
  505. {
  506. l: 'n1+(-n2*n3)',
  507. r: 'n1-n2*n3'
  508. },
  509. // Solving useless parenthesis 1
  510. {
  511. l: 'v*(-c)',
  512. r: '-c*v'
  513. },
  514. // Solving useless unary 2
  515. {
  516. l: 'n1+-n2',
  517. r: 'n1-n2'
  518. },
  519. // Solving +- together (new!)
  520. {
  521. l: 'v*c',
  522. r: 'c*v'
  523. },
  524. // inversion constant with variable
  525. {
  526. l: '(n1^n2)^n3',
  527. r: '(n1^(n2*n3))'
  528. } // Power to Power
  529. ];
  530. return setRules;
  531. } // End rulesRationalize
  532. // ---------------------------------------------------------------------------------------
  533. /**
  534. * Expand recursively a tree node for handling with expressions with exponents
  535. * (it's not for constants, symbols or functions with exponents)
  536. * PS: The other parameters are internal for recursion
  537. *
  538. * Syntax:
  539. *
  540. * expandPower(node)
  541. *
  542. * @param {Node} node Current expression node
  543. * @param {node} parent Parent current node inside the recursion
  544. * @param (int} Parent number of chid inside the rercursion
  545. *
  546. * @return {node} node expression with all powers expanded.
  547. */
  548. function expandPower(node, parent, indParent) {
  549. var tp = node.type;
  550. var internal = arguments.length > 1; // TRUE in internal calls
  551. if (tp === 'OperatorNode' && node.isBinary()) {
  552. var does = false;
  553. var val;
  554. if (node.op === '^') {
  555. // First operator: Parenthesis or UnaryMinus
  556. if ((node.args[0].type === 'ParenthesisNode' || node.args[0].type === 'OperatorNode') && node.args[1].type === 'ConstantNode') {
  557. // Second operator: Constant
  558. val = parseFloat(node.args[1].value);
  559. does = val >= 2 && isInteger(val);
  560. }
  561. }
  562. if (does) {
  563. // Exponent >= 2
  564. // Before:
  565. // operator A --> Subtree
  566. // parent pow
  567. // constant
  568. //
  569. if (val > 2) {
  570. // Exponent > 2,
  571. // AFTER: (exponent > 2)
  572. // operator A --> Subtree
  573. // parent *
  574. // deep clone (operator A --> Subtree
  575. // pow
  576. // constant - 1
  577. //
  578. var nEsqTopo = node.args[0];
  579. var nDirTopo = new OperatorNode('^', 'pow', [node.args[0].cloneDeep(), new ConstantNode(val - 1)]);
  580. node = new OperatorNode('*', 'multiply', [nEsqTopo, nDirTopo]);
  581. } else {
  582. // Expo = 2 - no power
  583. // AFTER: (exponent = 2)
  584. // operator A --> Subtree
  585. // parent oper
  586. // deep clone (operator A --> Subtree)
  587. //
  588. node = new OperatorNode('*', 'multiply', [node.args[0], node.args[0].cloneDeep()]);
  589. }
  590. if (internal) {
  591. // Change parent references in internal recursive calls
  592. if (indParent === 'content') {
  593. parent.content = node;
  594. } else {
  595. parent.args[indParent] = node;
  596. }
  597. }
  598. } // does
  599. } // binary OperatorNode
  600. if (tp === 'ParenthesisNode') {
  601. // Recursion
  602. expandPower(node.content, node, 'content');
  603. } else if (tp !== 'ConstantNode' && tp !== 'SymbolNode') {
  604. for (var i = 0; i < node.args.length; i++) {
  605. expandPower(node.args[i], node, i);
  606. }
  607. }
  608. if (!internal) {
  609. // return the root node
  610. return node;
  611. }
  612. } // End expandPower
  613. // ---------------------------------------------------------------------------------------
  614. /**
  615. * Auxilary function for rationalize
  616. * Convert near canonical polynomial in one variable in a canonical polynomial
  617. * with one term for each exponent in decreasing order
  618. *
  619. * Syntax:
  620. *
  621. * polyToCanonical(node [, coefficients])
  622. *
  623. * @param {Node | string} expr The near canonical polynomial expression to convert in a a canonical polynomial expression
  624. *
  625. * The string or tree expression needs to be at below syntax, with free spaces:
  626. * ( (^(-)? | [+-]? )cte (*)? var (^expo)? | cte )+
  627. * Where 'var' is one variable with any valid name
  628. * 'cte' are real numeric constants with any value. It can be omitted if equal than 1
  629. * 'expo' are integers greater than 0. It can be omitted if equal than 1.
  630. *
  631. * @param {array} coefficients Optional returns coefficients sorted by increased exponent
  632. *
  633. *
  634. * @return {node} new node tree with one variable polynomial or string error.
  635. */
  636. function polyToCanonical(node, coefficients) {
  637. if (coefficients === undefined) {
  638. coefficients = [];
  639. } // coefficients.
  640. coefficients[0] = 0; // index is the exponent
  641. var o = {};
  642. o.cte = 1;
  643. o.oper = '+';
  644. // fire: mark with * or ^ when finds * or ^ down tree, reset to "" with + and -.
  645. // It is used to deduce the exponent: 1 for *, 0 for "".
  646. o.fire = '';
  647. var maxExpo = 0; // maximum exponent
  648. var varname = ''; // variable name
  649. recurPol(node, null, o);
  650. maxExpo = coefficients.length - 1;
  651. var first = true;
  652. var no;
  653. for (var i = maxExpo; i >= 0; i--) {
  654. if (coefficients[i] === 0) continue;
  655. var n1 = new ConstantNode(first ? coefficients[i] : Math.abs(coefficients[i]));
  656. var op = coefficients[i] < 0 ? '-' : '+';
  657. if (i > 0) {
  658. // Is not a constant without variable
  659. var n2 = new SymbolNode(varname);
  660. if (i > 1) {
  661. var n3 = new ConstantNode(i);
  662. n2 = new OperatorNode('^', 'pow', [n2, n3]);
  663. }
  664. if (coefficients[i] === -1 && first) {
  665. n1 = new OperatorNode('-', 'unaryMinus', [n2]);
  666. } else if (Math.abs(coefficients[i]) === 1) {
  667. n1 = n2;
  668. } else {
  669. n1 = new OperatorNode('*', 'multiply', [n1, n2]);
  670. }
  671. }
  672. if (first) {
  673. no = n1;
  674. } else if (op === '+') {
  675. no = new OperatorNode('+', 'add', [no, n1]);
  676. } else {
  677. no = new OperatorNode('-', 'subtract', [no, n1]);
  678. }
  679. first = false;
  680. } // for
  681. if (first) {
  682. return new ConstantNode(0);
  683. } else {
  684. return no;
  685. }
  686. /**
  687. * Recursive auxilary function inside polyToCanonical for
  688. * converting expression in canonical form
  689. *
  690. * Syntax:
  691. *
  692. * recurPol(node, noPai, obj)
  693. *
  694. * @param {Node} node The current subpolynomial expression
  695. * @param {Node | Null} noPai The current parent node
  696. * @param {object} obj Object with many internal flags
  697. *
  698. * @return {} No return. If error, throws an exception
  699. */
  700. function recurPol(node, noPai, o) {
  701. var tp = node.type;
  702. if (tp === 'FunctionNode') {
  703. // ***** FunctionName *****
  704. // No function call in polynomial expression
  705. throw new Error('There is an unsolved function call');
  706. } else if (tp === 'OperatorNode') {
  707. // ***** OperatorName *****
  708. if ('+-*^'.indexOf(node.op) === -1) throw new Error('Operator ' + node.op + ' invalid');
  709. if (noPai !== null) {
  710. // -(unary),^ : children of *,+,-
  711. if ((node.fn === 'unaryMinus' || node.fn === 'pow') && noPai.fn !== 'add' && noPai.fn !== 'subtract' && noPai.fn !== 'multiply') {
  712. throw new Error('Invalid ' + node.op + ' placing');
  713. }
  714. // -,+,* : children of +,-
  715. if ((node.fn === 'subtract' || node.fn === 'add' || node.fn === 'multiply') && noPai.fn !== 'add' && noPai.fn !== 'subtract') {
  716. throw new Error('Invalid ' + node.op + ' placing');
  717. }
  718. // -,+ : first child
  719. if ((node.fn === 'subtract' || node.fn === 'add' || node.fn === 'unaryMinus') && o.noFil !== 0) {
  720. throw new Error('Invalid ' + node.op + ' placing');
  721. }
  722. } // Has parent
  723. // Firers: ^,* Old: ^,&,-(unary): firers
  724. if (node.op === '^' || node.op === '*') {
  725. o.fire = node.op;
  726. }
  727. for (var _i = 0; _i < node.args.length; _i++) {
  728. // +,-: reset fire
  729. if (node.fn === 'unaryMinus') o.oper = '-';
  730. if (node.op === '+' || node.fn === 'subtract') {
  731. o.fire = '';
  732. o.cte = 1; // default if there is no constant
  733. o.oper = _i === 0 ? '+' : node.op;
  734. }
  735. o.noFil = _i; // number of son
  736. recurPol(node.args[_i], node, o);
  737. } // for in children
  738. } else if (tp === 'SymbolNode') {
  739. // ***** SymbolName *****
  740. if (node.name !== varname && varname !== '') {
  741. throw new Error('There is more than one variable');
  742. }
  743. varname = node.name;
  744. if (noPai === null) {
  745. coefficients[1] = 1;
  746. return;
  747. }
  748. // ^: Symbol is First child
  749. if (noPai.op === '^' && o.noFil !== 0) {
  750. throw new Error('In power the variable should be the first parameter');
  751. }
  752. // *: Symbol is Second child
  753. if (noPai.op === '*' && o.noFil !== 1) {
  754. throw new Error('In multiply the variable should be the second parameter');
  755. }
  756. // Symbol: firers '',* => it means there is no exponent above, so it's 1 (cte * var)
  757. if (o.fire === '' || o.fire === '*') {
  758. if (maxExpo < 1) coefficients[1] = 0;
  759. coefficients[1] += o.cte * (o.oper === '+' ? 1 : -1);
  760. maxExpo = Math.max(1, maxExpo);
  761. }
  762. } else if (tp === 'ConstantNode') {
  763. var valor = parseFloat(node.value);
  764. if (noPai === null) {
  765. coefficients[0] = valor;
  766. return;
  767. }
  768. if (noPai.op === '^') {
  769. // cte: second child of power
  770. if (o.noFil !== 1) throw new Error('Constant cannot be powered');
  771. if (!isInteger(valor) || valor <= 0) {
  772. throw new Error('Non-integer exponent is not allowed');
  773. }
  774. for (var _i2 = maxExpo + 1; _i2 < valor; _i2++) {
  775. coefficients[_i2] = 0;
  776. }
  777. if (valor > maxExpo) coefficients[valor] = 0;
  778. coefficients[valor] += o.cte * (o.oper === '+' ? 1 : -1);
  779. maxExpo = Math.max(valor, maxExpo);
  780. return;
  781. }
  782. o.cte = valor;
  783. // Cte: firer '' => There is no exponent and no multiplication, so the exponent is 0.
  784. if (o.fire === '') {
  785. coefficients[0] += o.cte * (o.oper === '+' ? 1 : -1);
  786. }
  787. } else {
  788. throw new Error('Type ' + tp + ' is not allowed');
  789. }
  790. } // End of recurPol
  791. } // End of polyToCanonical
  792. });