13

PHP で CAS (Computer Algebra System) を作成していますが、現在行き詰まっています。私はこのウェブサイトを使用しています。

今、トークナイザーを書きました。次のような式に変換されます。

1+2x-3*(4-5*(3x))

これに：

NUMBER PLUS_OPERATOR NUMBER VAR[X] MINUS_OPERATOR NUMBER MULTIPLY_OPERATOR GROUP

(ここで、グループはトークンの別のセットです)。この方程式をどのように単純化できますか? ええ、私はあなたができることを知っています: X-vars を追加しますが、それらはサブグループにあります。これらのトークンを処理するために使用できる最良の方法は何ですか?

4

3 に答える 3

21

次の非常に便利なステップは、解析ツリーを構築することです。

ここに画像の説明を入力

中置パーサーを作成することで、これらのいずれかを作成できます。これを行うには、単純な再帰降下パーサーを作成するか、大きな銃を持ち込んでパーサー ジェネレーターを使用します。どちらの場合でも、形式的な文法を構築するのに役立ちます。

expression: additive

additive: multiplicative ([+-] multiplicative)*

multiplicative: primary ('*' primary)*

primary: variable
       | number
       | '(' expression ')'

この文法は2x構文を処理しませんが、簡単に追加できるはずです。

文法規則での再帰の巧妙な使用に注目してください。 primary変数、数値、および括弧で囲まれた式のみをキャプチャし、演算子に遭遇すると停止します。 記号で区切られたmultiplicative1 つ以上の式を解析しますが、または記号に遭遇すると停止します。 とで区切られた1 つ以上の式を解析しますが、 に遭遇すると停止します。したがって、再帰スキームによって演算子の優先順位が決まります。primary*+-additivemultiplicative+-)

以下で行ったように、手動で予測パーサーを実装することはそれほど難しくありません( 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 + ...

その部分はお任せします。構文解析木を使用すると、物事がより簡単になります。

于 2011-03-24T03:52:21.333 に答える
3

PHP は、文字列、数値、および配列を得意としています。しかし、本当にツリーが必要な「シンボリック式」を処理するためのネイティブな機構がないため、シンボリック式操作を実装するには不十分な言語です。はい、そのすべての機械を実装できます。難しいのは、代数操作を行うことです。半洗練されたものを構築したい場合、それはかなりの作業です。理想的には、変換を直接かつ簡単に作成するのに役立つ機械が必要です。

たとえば、任意の代数規則をどのように実装しますか? 結合性と交換性？「離れた場所でのマッチング」という用語、例えば

  (3*a+b)-2(a-b)+a ==> 3a-b

DMS プログラム変換システムを使用して簡単な CAS を実装する方法をご覧いただけます。DMS には交換性や結合性などの難しい数学的構造が組み込まれており、代数規則を明示的に記述して記号式を操作できます。

于 2011-03-23T22:59:20.417 に答える
1

Joel S. Cohen による本 Computer Algebra and Symbolic Computation: Mathematical Methods では、代数式の自動簡約化のアルゴリズムが説明されています。

このアルゴリズムは、C# のSymbolismコンピューター代数ライブラリで使用されます。あなたの例では、次のC＃プログラム：

var x = new Symbol("x");

(1 + 2 * x - 3 * (4 - 5 * (3 * x)))
    .AlgebraicExpand()
    .Disp();

コンソールに次のように表示されます。

-11 + 47 * x
于 2013-01-02T01:02:42.100 に答える