我正在用 PHP 创建一个 CAS(计算机代数系统),但现在陷入困境。我正在使用this website .
现在我写了一个分词器。它将转换如下方程:
1+2x-3*(4-5*(3x))
对此:
NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP
(其中 group 是另一组标记)。我怎样才能简化这个方程?是的,我知道你可以做什么:添加 X 变量,但它们位于子组中。我可以用来处理这些 token 的最佳方法是什么?
最佳答案
下一步真正有用的是构建解析树:
您可以通过编写中缀解析器来制作其中之一。您可以通过编写一个简单的递归下降解析器来做到这一点,或者通过引入大枪和using a parser generator来做到这一点。 。无论哪种情况,它都有助于构建正式语法:
expression: additive
additive: multiplicative ([+-] multiplicative)*
multiplicative: primary ('*' primary)*
primary: variable
| number
| '(' expression ')'
请注意,此语法不处理 2x
语法,但应该很容易添加。
注意语法规则中递归的巧妙使用。 primary
仅捕获变量、数字和带括号的表达式,并在遇到运算符时停止。 multiplicative
解析由 *
符号分隔的一个或多个 primary
表达式,但当遇到 +
或 -
符号。 additive
解析由 +
和 -
分隔的一个或多个 乘法
表达式,但在遇到 时停止>)
。因此,递归方案决定了运算符的优先级。
实现predictive parser并不是太困难。手动,正如我在下面所做的那样( see full example at ideone.com ):
function parse()
{
global $tokens;
reset($tokens);
$ret = parseExpression();
if (current($tokens) !== FALSE)
die("Stray token at end of expression\n");
return $ret;
}
function popToken()
{
global $tokens;
$ret = current($tokens);
if ($ret !== FALSE)
next($tokens);
return $ret;
}
function parseExpression()
{
return parseAdditive();
}
function parseAdditive()
{
global $tokens;
$expr = parseMultiplicative();
for (;;) {
$next = current($tokens);
if ($next !== FALSE && $next->type == "operator" &&
($next->op == "+" || $next->op == "-"))
{
next($tokens);
$left = $expr;
$right = parseMultiplicative();
$expr = mkOperatorExpr($next->op, $left, $right);
} else {
return $expr;
}
}
}
function parseMultiplicative()
{
global $tokens;
$expr = parsePrimary();
for (;;) {
$next = current($tokens);
if ($next !== FALSE && $next->type == "operator" &&
$next->op == "*")
{
next($tokens);
$left = $expr;
$right = parsePrimary();
$expr = mkOperatorExpr($next->op, $left, $right);
} else {
return $expr;
}
}
}
function parsePrimary()
{
$tok = popToken();
if ($tok === FALSE)
die("Unexpected end of token list\n");
if ($tok->type == "variable")
return mkVariableExpr($tok->name);
if ($tok->type == "number")
return mkNumberExpr($tok->value);
if ($tok->type == "operator" && $tok->op == "(") {
$ret = parseExpression();
$tok = popToken();
if ($tok->type == "operator" && $tok->op == ")")
return $ret;
else
die("Missing end parenthesis\n");
}
die("Unexpected $tok->type token\n");
}
好的,现在你有了这个可爱的解析树,甚至还有一张漂亮的图片。怎么办?您的目标(目前)可能是简单地组合术语以获得以下形式的结果:
n1*a + n2*b + n3*c + n4*d + ...
我会把这部分留给你。拥有解析树应该会让事情变得更加简单。
关于php - 构建计算机代数系统,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5412612/