README

描述
什么是Shunting Yard算法
Shunting Yard算法的实现
RPN表达式求解器
AST树构建器
安装
用法
类似项目
文档

描述

该库的主要目标是使用 Doctrine 语法分析器将表达式转换为计算机可理解的表达式

Doctrine 语法分析器
Shunting Yard算法

由于Shunting Yard的输入是 Doctrine 语法分析器，因此库不仅限于数学表达式。

库提供Shunting Yard算法输出的“评估器”，或将其转换为AST树

什么是Shunting Yard算法

最佳解释可以在维基百科（https://en.wikipedia.org/wiki/Shunting-yard_algorithm）或这篇文章中找到，作者是@igorw。

但为了简单起见，主要思想是将字符列表转换为多个小组。

简单示例：(1 + 2) * 3对我们（人类）来说非常简单，但对于计算机来说，它需要将其拆分成小块。然后逐个评估它们。对于计算机，表达式需要这样评估

这是一个二叉树，是的，它也是一种AST。所以为了解决这个表达式，计算机首先评估这个组（我们将结果命名为(a)）

      +
     / \
    1   2

然后评估这个组

   *
  / \
(a)  3

Shunting Yard算法将你的表达式转换为一个中间表达式：RPN表达式。表达式(1 + 2) * 3的RPN表达式是1 2 + 3 *。

这个表达式可以这样读取

参数1
参数2
运算符+（它接受2个参数：前两个参数）
参数3
运算符*（它接受2个参数：操作的结果和前面的参数）

Shunting Yard算法的实现

像大多数Shunting Yard实现一样，它可以解析“简单”表达式（具有简单运算符）并减少括号。它可以解析一元和二元函数（如sin(x)，max(x,y)），但也可以解析任何函数（例如fct(a,b,c,x,y,z)）。

但主要的“功能”是使用Doctrine Lexer。

RPN表达式求解器

RPN求解器允许你解决RPN表达式（Doctrine Lexer标记的列表）。它支持任何可变参数的运算符/函数。

AST树构建器

AST树构建器可以将RPN表达式（Doctrine Lexer标记的列表）转换为AST树。
树的根是一个节点，最后一个（最终）节点（在什么是Shunting Yard算法中，它是运算符*）。这个根节点由值（树的叶子）和节点（分支）组成。

限制

求解器无法解决可变参数（或可选参数）的函数

安装

使用composer安装

composer require macfja/lexer-expression

用法

非常简单的Doctrine DQL

use \Doctrine\ORM\Query\Lexer;

$dql = 'SELECT u FROM User u WHERE u.id = MAX(5, 7)';
$lexer = new Lexer($dql);
$sy = new ShuntingYard();
$sy->setLexer($lexer);
$sy->setOpenParenthesis(Lexer::T_OPEN_PARENTHESIS);
$sy->setCloseParenthesis(Lexer::T_CLOSE_PARENTHESIS);
$sy->setOperators(array(
    new ShuntingYardOperator(Lexer::T_MAX,    10, ShuntingYardOperator::ASSOCIATIVITY_LEFT),
    new ShuntingYardOperator(Lexer::T_SELECT, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT),
    new ShuntingYardOperator(Lexer::T_FROM,   10, ShuntingYardOperator::ASSOCIATIVITY_LEFT),
    new ShuntingYardOperator(Lexer::T_WHERE,  2,  ShuntingYardOperator::ASSOCIATIVITY_LEFT),
    new ShuntingYardOperator(Lexer::T_DOT,    10, ShuntingYardOperator::ASSOCIATIVITY_LEFT),
    new ShuntingYardOperator(Lexer::T_EQUALS, 10, ShuntingYardOperator::ASSOCIATIVITY_LEFT)
));
$sy->setArgumentSeparator(Lexer::T_COMMA);
var_dump($sy->parse());

非常简单的数学表达式

在test目录中有3个示例。表达式是(1 + 2) / ((3 + 4 * 5) - 6)。

test/MathRPN.php：只是一个表达式到RPN的示例
test/MathSolve.php：一个使用求解器的示例
test/MathAST.php：一个使用树构建器的示例

表达式的树如下

          "/"
         /   \
        /     \
       /      "-"
      /      /   \
     /     "+"    6
    /     /   \
  "+"    3    "*"
 /   \       /   \
1     2     4     5

macfja / lexer-expression

维护者

详细信息