muqsit / arithmexp Goto Github PK

A powerful mathematical expression parser and evaluator for PHP featuring variable substitution, user-defined constants, functions, deterministic functions, macros, operators, and compiler optimizations.

Home Page: https://arithmexp.pages.dev

License: GNU General Public License v3.0

PHP 100.00%

composer-library php calculator logic math parser pmmp pocketmine-mp virion mathematical-expression-parser

arithmexp's People

Contributors

Stargazers

Watchers

Forkers

pm-pl

arithmexp's Issues

Improve sub-expression comparison in Operator Strength Reduction

Operator Strength Reduction's implementation is too straightforward at the moment. As it does a mere leftTokens == rightTokens comparison for division, multiplication and subtraction, (x * y) - (x * y) translates to a ConstantExpression(0) while (x * y) - (y * x) stays the same.

Result of subtraction optimization produces wrong value

Optimization on the expression (x - 0) - (0 - y) should result in x + y, not x - y.

arithmexp/tests/muqsit/arithmexp/OptimizerTest.php

Line 281 in 328895e

$expected = $this->unoptimized_parser->parse("x - y");

Unary operations must have lower precedence than exponentiation

Currently, all unary operations are given a higher precedence than all binary operations. Following PHP's operator precedence, the exponentiation binary operation must have a higher precedence than the unary operations. Due to conflicting precedence, the result of the expression -3 ** 2 does not match with the result in PHP:

var_dump($parser->parse("-3 ** 2")->evaluate());
// int(9)
// is evaluated as: (-3) ** 2

var_dump(-3 ** 2);
// int(-9)
// is evaluated as: -(3 ** 2)

Confusion of - and + operators with negative and positive numbers

Since "-" and "+" are binary operators, two operands need to be explicitly declared on either sides of the operator, such as 3 + 5. This limits expressions from declaring negative or positive numbers without explicitly adding a zero on the missing side.

6 - -1
// ArithmeticExpressionException: "No right-side operand found for 'T_OPERATOR' at '-' [5:5] while parsing '6 - -1'"

6 - (0-1)
// 7

Add support for Solver Equations

Supports solving equations like:

Simul Equation
- 2 Unknowns
- 3 Unknowns
- 4 Unknowns
- n Unknowns
Polynomial
- $ax^2 + bx + c$
- $ax^3 + bx^2 + cx + d$
- $ax^4 + bx^3 + cx^2 + dx + e$
- $a_n x^n + a_{n-1}x + a_{n-2}x^{n-2} + \dots + a_1x^1 + a_0$
Equation (Find values of variable)

Maybe this feature is not suitable for your library but it would be nice if it was added.
I found a similar library for this feature but it seems to be no longer maintained.
https://github.com/Samshal/Equation-Solver

Comparison Operators

Something like:

$parser = Parser::createDefault();

$expression = $parser->parse("2 + 3 > 5");
var_dump($expression->evaluate()); // bool(false)

$expression = $parser->parse("2 + 3 => 5");
var_dump($expression->evaluate()); // bool(true)

Comparison Operators: https://www.php.net/manual/en/language.operators.comparison.php

Add support for arbitrary-length numbers

$parser = Parser::createDefault();

$expression = $parser->parse("111111111111111111111111111111111111111111111111111111111111111111111111111");
var_dump($expression->evaluate()); // int(9223372036854775807)

$expression = $parser->parse("111111111111111111111111111111111111111111111");
var_dump($expression->evaluate()); // int(9223372036854775807)

$expression = $parser->parse("99999999999999999999999");
var_dump($expression->evaluate()); // int(9223372036854775807)

$expression = $parser->parse("9999999999999999999999999999999999");
var_dump($expression->evaluate()); // int(9223372036854775807)

Support for `6/2(1+2)` expression

6/2(1+2)
i think this expression should be parsed as 6/[2(1+2)] instead of throwing an error.

* Sorry I couldn't find a suitable title for this issue

> https://youtu.be/URcUvFIUIhQ (may be related)

Add more unit tests

Replace recursive method calls with an iterative approach

Recursion has an overhead on memory, can result in stack overflow for deeply nested expressions, and makes stack traces spammy (see below). The parser performs recursive method calls when traversing the token tree in various places such as here, here, here, and here.

muqsit@*********:~/arithmexp/tests$ php test3.php "x + min(mt_rand(1, 3), mt_rand(2, mt_rand(3, 4, 5)), 7) * y"

Fatal error: Uncaught muqsit\arithmexp\ParseException: Cannot resolve function call at "mt_rand(3, 4, 5)" (34:50) in "x + min(mt_rand(1, 3), mt_rand(2, mt_rand(3, 4, 5)), 7) * y": Too many parameters supplied to function call: Expected 2 parameters, got 3 parameters
 | x + min(mt_rand(1, 3), mt_rand(2, mt_rand(3, 4, 5)), 7) * y
 |                                   ^^^^^^^^^^^^^^^^ in /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/ParseException.php:32
Stack trace:
#0 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/ParseException.php(144): muqsit\arithmexp\ParseException::generateWithHighlightedSubstring(Object(muqsit\arithmexp\ParseException))
#1 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(352): muqsit\arithmexp\ParseException::unresolvableFcallTooManyParams('x + min(mt_rand...', Object(muqsit\arithmexp\token\FunctionCallToken), Object(muqsit\arithmexp\function\FunctionInfo), 3)
#2 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#3 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#4 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#5 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#6 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#7 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#8 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(283): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#9 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(143): muqsit\arithmexp\Parser->transformFunctionCallTokens('x + min(mt_rand...', Array)
#10 /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/Parser.php(97): muqsit\arithmexp\Parser->processTokens('x + min(mt_rand...', Array)
#11 /home/muqsit/arithmexp/tests/test3.php(13): muqsit\arithmexp\Parser->parseExpression('x + min(mt_rand...')
#12 {main}
  thrown in /home/muqsit/arithmexp/tests/vendor/muqsit/arithmexp/src/muqsit/arithmexp/ParseException.php on line 32

Variables should be allowed to contain numeric characters

Support for factorial

Something like this

$parser = Parser::createDefault();
$expression = $parser->parse("2! + 3!");
var_dump($expression->evaluate()); // int(8)

$parser = Parser::createDefault();
$expression = $parser->parse("fact(2) + fact(3)");
// https://www.php.net/manual/en/function.gmp-fact.php
var_dump($expression->evaluate()); // int(8)

2! + 3! instead of 1*2 + 1*2*3

Properly implement operator precedence

At the moment, operator precedence is implemented by performing a simple lookup on a sorted array of operators.

arithmexp/src/muqsit/arithmexp/token/BinaryOperatorToken.php

Lines 10 to 17 in ebcb0ad

 public const OPERATOR_PRECEDENCE = [ 

 self::OPERATOR_TYPE_EXPONENTIAL, 

 self::OPERATOR_TYPE_MODULO, 

 self::OPERATOR_TYPE_DIVISION, 

 self::OPERATOR_TYPE_MULTIPLICATION, 

 self::OPERATOR_TYPE_ADDITION, 

 self::OPERATOR_TYPE_SUBTRACTION 

 ];

This means there are no operators with equal precedence in the library at the moment. Associativity (left-associativity vs right-associativity) is what should be the determining factor for precedence when it comes to operators with equal precedence.

Cannot negate variables in expression directly

Trying to parse the expression 4 * -var throws the following error

ArithmeticExpressionException: "No right-side operand found for 'T_OPERATOR' at '*' [3:3] while parsing '4 * -var'"

The expressions 4 * (-var) and -var * 4 work as expected, however.

Add support for various forms of brackets

I think it should parse curly braces and square brackets from the input.
These brackets make the expression easier to read and write.
An example a + {[b - (c / d)] * 3} better a + ((b - (c / d)) * 3}

Optimizer does not account for INF and NAN

Description

Operator Strength Reduction optimizer directly substitutes a sub-expression x - x with 0, not accounting for INF or NAN values being supplied to x (inf - inf and nan - nan must produce nan). Other affected cases include 0 * inf returning 0 instead of NAN, and sqrt(-1) / sqrt(-1) getting substituted for 1 despite sqrt(-1) === NAN (NAN / NAN === NAN).

As variable resolution occurs during evaluation, x - x cannot be resolved during parsing although 1 - 1 and inf - inf can. One way to address this would be to resolve operations between numeric literal operands during parsing and implement a mechanism to toggle optimizations that disregard INF and NAN (like GCC's FloatingPointMath flags).

Workarounds

Filter out operator strength reduction optimization from ExpressionOptimizerRegistry

$parser = Parser::createDefault();

$optimizations = new ExpressionOptimizerRegistry();
foreach($parser->getExpressionOptimizerRegistry()->getRegistered() as $identifier => $value){
	if(!($value instanceof OperatorStrengthReductionExpressionOptimizer)){
		$optimizations->register($identifier, $value);
	}
}

$parser = new Parser(
	$parser->getBinaryOperatorRegistry(),
	$parser->getUnaryOperatorRegistry(),
	$parser->getConstantRegistry(),
	$parser->getFunctionRegistry(),
	$optimizations,
	$parser->getScanner()
);

Disable optimizations altogether — $parser = Parser::createUnoptimized();

	public const OPERATOR_PRECEDENCE = [
	self::OPERATOR_TYPE_EXPONENTIAL,
	self::OPERATOR_TYPE_MODULO,
	self::OPERATOR_TYPE_DIVISION,
	self::OPERATOR_TYPE_MULTIPLICATION,
	self::OPERATOR_TYPE_ADDITION,
	self::OPERATOR_TYPE_SUBTRACTION
	];