114

バイナリ (+、-、​​|、&、*、/ など) 演算子、単項 (!) 演算子、および括弧を処理する単純なスタック アルゴリズムを使用して、方程式パーサーを開発しました。

ただし、この方法を使用すると、すべての優先順位が同じになります。演算子に関係なく左から右に評価されますが、括弧を使用して優先順位を強制できます。

したがって、現在 "1+11*5" は 60 を返します。予想される 56 ではありません。

これは現在のプロジェクトに適していますが、後のプロジェクトで使用できる汎用ルーチンが必要です。

明確にするために編集:

優先順位を付けて方程式を解析するための優れたアルゴリズムは何ですか?

実装が簡単で、利用可能なコードのライセンスの問題を回避するために自分でコーディングできることを理解することに興味があります。

文法:

文法の質問がわかりません - これは手書きで書いたものです。YACC や Bison を必要としないほど単純です。「2+3 * (42/13)」などの式で文字列を計算するだけです。

言語:

私はこれを C で行っていますが、言語固有のソリューションではなく、アルゴリズムに興味があります。C は低レベルなので、必要に応じて別の言語に簡単に変換できます。

コード例

上記で説明した単純な式パーサーのテスト コードを投稿しました。プロジェクトの要件が変更されたため、プロジェクトに組み込まれていないため、パフォーマンスやスペースのためにコードを最適化する必要はありませんでした。これは元の詳細な形式であり、容易に理解できるはずです。演算子の優先順位に関してさらに何かを行う場合は、プログラムの残りの部分と単純に一致するため、おそらくマクロ ハックを選択します。ただし、これを実際のプロジェクトで使用する場合は、よりコンパクトで高速なパーサーを使用します。

関連する質問

数学パーサーのスマートな設計?

-アダム

4

24 に答える 24

171

避難所アルゴリズムは、これに適したツールです。ウィキペディアはこれについて非常に混乱していますが、基本的にアルゴリズムは次のように機能します。

1 + 2 * 3 + 4 を評価したいとします。直観的には、最初に 2 * 3 を実行する必要があることを「知っています」が、どうすればこの結果が得られるのでしょうか。重要なのは、文字列を左から右にスキャンしているときに、後続の演算子の優先順位が低い (または等しい)場合に演算子を評価することを認識することです。この例のコンテキストでは、次のことを行います。

  1. 見てください: 1 + 2、何もしないでください。
  2. 1 + 2 * 3 を見てください。まだ何もしていません。
  3. 1 + 2 * 3 + 4 を見てください。次の演算子の優先順位が低いため、2 * 3 を評価する必要があることがわかります。

これをどのように実装しますか?

1 つは数値用、もう 1 つは演算子用の 2 つのスタックが必要です。常に数字をスタックにプッシュします。新しい各演算子をスタックの一番上にある演算子と比較し、スタックの一番上の演算子の優先度が高い場合は、演算子スタックからポップし、数値スタックからオペランドをポップし、演算子を適用して結果をプッシュします。番号スタックに。ここで、スタック演算子の一番上で比較を繰り返します。

例に戻ると、次のように機能します。

N = [ ] オペレーション = [ ]

  • 1 を読み取ります。N = [1]、Ops = [ ]
  • +を読んでください。N = [1]、操作 = [+]
  • 2 を読んでください。N = [1 2]、Ops = [+]
  • 読んでください*。N = [1 2]、演算 = [+ *]
  • 3 を読みます。N = [1 2 3]、Ops = [+ *]
  • +を読んでください。N = [1 2 3]、演算 = [+ *]
    • 3、2 をポップして 2 *3 を実行し、結果を N にプッシュします。N = [1 6]、Ops = [+]
    • +は連想のままなので、1、6 もポップして + を実行します。N = [7]、操作 = []。
    • 最後に [+] をオペレーター スタックにプッシュします。N = [7]、操作 = [+]。
  • 4 を読んでください。N = [7 4]。操作 = [+]。
  • 入力が不足しているので、今すぐスタックを空にしたいと考えています。その上で、結果 11 が得られます。

ほら、そんなに難しくないですよね?また、文法やパーサー ジェネレーターを呼び出すこともありません。

于 2008-09-06T18:38:43.503 に答える
70

難しい方法

再帰降下パーサーが必要です。

優先順位を得るには、再帰的に考える必要があります。たとえば、サンプル文字列を使用して、

1+11*5

これを手動で行うには、 を読み取り、プラスを確認して ... で1始まるまったく新しい再帰的解析「セッション」を開始し、 を独自の要素に解析して、 を含む解析ツリーを生成する必要があります。1111 * 51 + (11 * 5)

これは、特に C の無力さが追加されているため、説明しようとしても非常に苦痛に感じます。11それ自体が要因です。私の頭はすでに爆発しています。再帰的な適切な戦略で可能ですが、より良い方法があります...

簡単な(正しい)方法

Bison のような GPL ツールを使用している場合、bison によって生成された C コードは GPL でカバーされていないため、おそらくライセンスの問題について心配する必要はありません (IANAL ですが、GPL ツールは GPL を強制しないと確信しています)。生成されたコード/バイナリ; たとえば、Apple は Aperture などのコードを GCC でコンパイルし、GPL を使用せずにそれを販売しています)。

Bison (または同等のもの、ANTLR など) をダウンロードします。

通常、bison を実行して、この 4 つの関数の電卓を示す目的の C コードを取得できるサンプル コードがいくつかあります。

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

生成されたコードを見て、これが思ったほど簡単ではないことを確認してください。また、Bison のようなツールを使用する利点は、1) 何かを学ぶことができる (特にドラゴンの本を読んで文法を学ぶ場合)、2) NIHが車輪を再発明しようとするのを避けることができる、ということです。実際のパーサー ジェネレーター ツールを使用すると、後でスケールアップして、パーサーが解析ツールの領域であることを他の人に示すことができます。


アップデート:

ここの人々は、多くの適切なアドバイスを提供してくれました。解析ツールをスキップしたり、Shunting Yard アルゴリズムや手巻きの再帰的でまともなパーサーを使用したりすることに対する私の唯一の警告は、小さなおもちゃの言語1が、関数 (sin、cos、log) と変数、条件、およびループします。

Flex/Bison は、小さくて単純なインタープリターにはやり過ぎかもしれませんが、1 回限りのパーサーとエバリュエーターは、変更が必要な場合や機能を追加する必要がある場合に、後で問題を引き起こす可能性があります。あなたの状況はさまざまであり、あなたの判断を下す必要があります。あなたの罪のために他の人を罰 しないでください[2]と十分ではないツールを構築します.

私のお気に入りの解析ツール

この仕事に最適なツールは、プログラミング言語 Haskell に付属するParsecライブラリ (再帰的で適切なパーサー用) です。これはBNFや解析用の特殊なツールやドメイン固有の言語 (サンプル コード [3])によく似ていますが、実際には単なる Haskell の通常のライブラリです。つまり、残りの部分と同じビルド ステップでコンパイルされます。任意の Haskell コードを記述してパーサー内で呼び出すことができ、同じコード内で他のライブラリをすべて組み合わせて一致させることができます。(ちなみに、このような構文解析言語を Haskell 以外の言語に埋め込むと、大量の構文上の問題が発生します。私はこれを C# で行いましたが、非常にうまく機能しますが、それほどきれいでも簡潔でもありません。)

ノート:

1 Richard Stallman は、Tcl を使用すべきでない理由で述べています。

Emacs の主要な教訓は、拡張用の言語は単なる「拡張言語」であってはならないということです。実質的なプログラムを作成および保守するために設計された、実際のプログラミング言語でなければなりません。人々はそれをしたいと思うからです!

[2] はい、私はその「言語」を使用することで永遠に傷ついています。

また、私がこのエントリを提出したとき、プレビューは正しかったが、SO の不十分なパーサーが最初の段落で私の終了アンカー タグを食べたことに注意してください。おそらく微妙で小さな間違いを犯すでしょう

[3] Parsec を使用した Haskell パーサーのスニペット: 指数、括弧、乗算用の空白、および定数 (pi や e など) で拡張された 4 つの関数の計算機。

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result
于 2008-08-26T22:39:39.693 に答える
26

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

さまざまなアプローチの非常に良い説明:

  • 再帰下降認識
  • 操車場アルゴリズム
  • 古典的な解決策
  • 優先順位の上昇

簡単な言語と擬似コードで書かれています。

私は「優先順位の上昇」が好きです。

于 2010-03-25T16:27:22.177 に答える
18

単純な再帰降下パーサーと演算子優先解析の組み合わせに関する素晴らしい記事がここにあります。最近パーサーを作成している場合は、非常に興味深く、有益な内容になっているはずです。

于 2008-10-09T06:06:34.077 に答える
17

昔、私は独自の構文解析アルゴリズムを作成しましたが、これは構文解析に関するどの本 (Dragon Book など) でも見つけることができませんでした。Shunting Yard アルゴリズムへのポインターを見ると、似ていることがわかります。

約 2 年前、私はそれについて、Perl のソース コードを添えてhttp://www.perlmonks.org/?node_id=554516に投稿しました。他の言語への移植は簡単です。私が最初に実装したのは Z80 アセンブラーでした。

数値を直接計算するのに理想的ですが、必要に応じて解析ツリーを作成するために使用できます。

更新より多くの人が Javascript を読む (または実行する) ことができるようになったため、コードを再編成した後、Javascript でパーサーを再実装しました。パーサー全体は、エラー報告とコメントを含めて 5k 以下の Javascript コード (パーサーで約 100 行、ラッパー関数で 15 行) です。

http://users.telenet.be/bartl/expressionParser/expressionParser.htmlでライブ デモを見つけることができます。

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}
于 2008-09-22T13:51:48.120 に答える
13

現在解析に使用している文法を説明していただけると助かります。問題はそこにあるようです!

編集:

あなたが文法の質問を理解していないという事実と、「あなたはこれを手で書いた」という事実は、「1+11*5」の形式 (つまり、演算子の優先順位) の式で問題が発生する理由を説明している可能性が非常に高いです。 . たとえば、「算術式の文法」をグーグルで検索すると、適切なポインタが得られるはずです。そのような文法は複雑である必要はありません:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

たとえば、トリックを実行し、いくつかのより複雑な式 (関数や累乗などを含む) を処理するために簡単に拡張できます。

たとえば、このスレッドをご覧になることをお勧めします。

文法/構文解析のほとんどすべての紹介では、算術式を例として扱います。

文法を使用することは、特定のツール ( Yacc、Bison など)を使用することをまったく意味しないことに注意してください。実際、あなたはすでに次の文法を使用していることは間違いありません。

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(またはそのようなもの)それを知らずに!

于 2008-08-26T14:59:37.337 に答える
8

ブーストスピリットの使用を考えたことはありますか?次のように、C++ で EBNF のような文法を記述できます。

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));
于 2009-04-28T20:36:41.443 に答える
5

優先度解析のもう 1 つのリソースは、Wikipedia のOperator-precedence パーサーエントリです。Dijkstra の分流ヤード アルゴリズムとツリーの代替アルゴリズムをカバーしていますが、より注目すべきは、優先順位を無視したパーサーの前に自明に実装できる、非常に単純なマクロ置換アルゴリズムをカバーしています。

#include <stdio.h>
int main(int argc, char *argv[]){
  printf("((((");
  for(int i=1;i!=argc;i++){
    if(argv[i] && !argv[i][1]){
      switch(argv[i]){
      case '^': printf(")^("); continue;
      case '*': printf("))*(("); continue;
      case '/': printf("))/(("); continue;
      case '+': printf(")))+((("); continue;
      case '-': printf(")))-((("); continue;
      }
    }
    printf("%s", argv[i]);
  }
  printf("))))\n");
  return 0;
}

次のように呼び出します。

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

これは、そのシンプルさが素晴らしく、非常に理解しやすいものです。

于 2009-04-23T19:10:11.443 に答える
5

質問をすると、再帰の必要はまったくありません。答えは次の 3 つです: Postfix 記法、Shunting Yard アルゴリズム、Postfix 式の評価:

1)。後置記法 = 優先順位を明示的に指定する必要をなくすために発明されました。ネットでもっと読むが、ここにその要点があります: infix expression ( 1 + 2 ) * 3 一方、人間にとっては読みやすく、処理は機械による計算にはあまり効率的ではありません。とは?「優先的にキャッシュして式を書き換え、常に左から右に処理する」という単純なルール。したがって、中置 ( 1 + 2 ) * 3 は後置 12+3* になります。演算子は常にオペランドの後に配置されるため、POST。

2)。後置式を評価しています。簡単。後置文字列から数字を読み取ります。オペレーターが表示されるまで、それらをスタックにプッシュします。演算子の種類を確認してください - 単項? バイナリ?三次?この演算子を評価するために必要な数のオペランドをスタックからポップします。評価。結果をスタックにプッシュしてください! そして、ほぼ完了しました。スタックが探しているエントリ = 値が 1 つだけになるまで、これを続けます。

やりましょう ( 1 + 2 ) * 後置にある 3 は "12+3*" です。最初の数値 = 1 を読み取ります。スタックにプッシュします。次に読む。数 = 2. スタックにプッシュします。次に読む。オペレーター。どれ?+。どんな?Binary = には 2 つのオペランドが必要です。スタックを 2 回ポップ = argright は 2、argleft は 1 です。1 + 2 は 3 です。スタックに 3 をプッシュします。後置文字列から次に読み取ります。その数。3.押す。次に読む。オペレーター。どれ?*。どんな?バイナリ = 2 つの数値が必要 -> スタックを 2 回ポップします。最初に argright にポップし、2 回目に argleft にポップします。評価操作 - 3 かける 3 は 9 です。スタックに 9 をプッシュします。次の後置文字を読み取ります。ヌルです。入力終了。ポップ スタック onec = それがあなたの答えです。

3)。Shunting Yard は、人間が (簡単に) 読める中置式を後置式に変換するために使用されます (また、ある程度の練習の後、人間も簡単に読めるようになります)。手動で簡単にコーディングできます。上記のコメントとネットを参照してください。

于 2012-06-09T00:07:27.993 に答える
5

不正行為をして、 Shunting Yard Algorithmを使用することをお勧めします。これは単純な電卓タイプのパーサーを作成する簡単な手段であり、優先順位を考慮します。

物事を適切にトークン化し、変数などを含めたい場合は、ここで他の人が提案するように再帰降下パーサーを作成しますが、電卓スタイルのパーサーが必要な場合は、このアルゴリズムで十分です:-)

于 2008-08-28T18:53:58.393 に答える
4

使いたい言語はありますか? ANTLRを使用すると、Java の観点からこれを行うことができます。Adrian Kuhn は、Ruby で実行可能な文法を作成する方法について優れた記事を書いています。実際、彼の例は、あなたの算術式の例とほとんど同じです。

于 2008-08-26T15:04:04.033 に答える
4

それは、どの程度「一般的」になりたいかによって異なります。

sin(4+5)*cos(7^3) のように数学関数を解析できるようにするなど、本当に一般的なものにしたい場合は、おそらく解析ツリーが必要になるでしょう。

その中で、完全な実装をここに貼り付けるのは適切ではないと思います。悪名高い「ドラゴンブック」の1つをチェックすることをお勧めします。

しかし、優先順位のサポートだけが必要な場合は、最初に式を後置形式に変換することでそれを行うことができます。この形式では、コピーアンドペーストできるアルゴリズムがgoogleから入手できるか、バイナリで自分でコーディングできると思います木。

後置形式になっている場合は、スタックがどのように役立つかを既に理解しているので、それ以降は簡単です。

于 2008-08-26T15:06:22.263 に答える
4

超コンパクト (1 クラス、< 10 KiB) Java Math EvaluatorのソースをWeb サイトに投稿しました。これは、受け入れられた回答のポスターの頭蓋爆発を引き起こしたタイプの再帰降下パーサーです。

完全な優先順位、括弧、名前付き変数、単一引数関数をサポートしています。

于 2008-12-17T19:34:12.187 に答える
4

Shunting Yard アルゴリズムに関する PIClist でこれを見つけました。

ハロルドは次のように書いています。

ずっと前に、簡単に評価できるように代数式を RPN に変換するアルゴリズムを読んだことを覚えています。各中置値、演算子、または括弧は、線路上の鉄道車両によって表されました。1 種類の車が別のトラックに分かれ、もう 1 種類の車はそのまま直進しました。詳細は覚えていませんが (もちろん!)、コードを書くのは面白いだろうといつも思っていました。これは、6800 (68000 ではない) アセンブリ コードを書いていたときの話です。

これが「シャント ヤード アルゴリズム」であり、ほとんどのマシン パーサーが使用するものです。ウィキペディアの解析に関する記事を参照してください。分流ヤード アルゴリズムをコーディングする簡単な方法は、2 つのスタックを使用することです。1 つは「プッシュ」スタックで、もう 1 つは「リデュース」または「結果」スタックです。例:

pstack = () // 空 rstack = () 入力: 1+2*3 優先順位 = 10 // 最小の削減 = 0 // 削減しない

start: token '1': isnumber, put in pstack (push) token '+': isoperator set precedence=2 if precedence < previous_operator_precedence then reduce() // 下記参照 put '+' in pstack (push) token '2' : isnumber, pstack に入れる (プッシュ) トークン '*': isoperator, set precedence=1, put in pstack (push) // 優先順位をチェック // トークンの上 '3': isnumber, pstack に入れる (プッシュ) end of入力、削減する必要があります (目標は空 pstack) reduce() //完了

削減するには、プッシュ スタックから要素をポップして結果スタックに配置します。「演算子」「数値」の形式の場合、常に pstack の上位 2 つのアイテムを交換します。

pstack: '1' '+' '2' ' '3' rstack: () ... pstack: () rstack: '3' '2' ' '1' '+'

式が次のようになる場合:

1*2+3

次に、削減トリガーは、既にプッシュされた「*」よりも優先順位が低いトークン「+」の読み取りであったため、次のようになります。

pstack: '1' ' ' '2' rstack: () ... pstack: () rstack: '1' '2' ' '

次に「+」を押してから「3」を押し、最後に減らしました:

pstack: '+' '3' rstack: '1' '2' ' ' ... pstack: () rstack: '1' '2' ' '3' '+'

したがって、短いバージョンは次のとおりです。数字をプッシュします。演算子をプッシュするときは、前の演算子の優先順位を確認します。現在プッシュされるオペレーターよりも高かった場合は、まず縮小してから、現在のオペレーターをプッシュします。括弧を処理するには、単に「前の」演算子の優先順位を保存し、pstack にマークを付けて、括弧のペアの内側を解くときに還元アルゴリズムに還元を停止するように指示します。閉じ括弧は、入力の終わりと同様にリダクションをトリガーし、pstack から開き括弧マークを削除し、「前の操作」の優先順位を復元して、閉じ括弧の後に解析を続行できるようにします。これは、再帰を使用しても使用しなくても実行できます (ヒント: '(' ...) に遭遇した場合は、スタックを使用して以前の優先順位を保存してください。これの一般化されたバージョンは、分流ヤード アルゴリズムを実装したパーサー ジェネレーターを使用することです。yacc または bison または taccle (yacc の tcl アナログ) を使用します。

ピーター

-アダム

于 2008-12-09T20:35:26.153 に答える
3

Apache License 2.0の条件の下で、ダイクストラの操車場アルゴリズムに基づく式パーサーをリリースしました。

http://projects.congrace.de/exp4j/index.html

于 2011-07-23T17:16:40.177 に答える
2

私は F# で式パーサーを作成し、ここでブログを書きました。分流場アルゴリズムを使用していますが、infix から RPN に変換する代わりに、計算結果を蓄積する 2 つ目のスタックを追加しました。演算子の優先順位は正しく処理されますが、単項演算子はサポートされていません。ただし、式の解析を学ぶためではなく、F# を学ぶためにこれを書きました。

于 2008-11-05T22:30:17.937 に答える
2

pyparsing を使用した Python ソリューションは、こちらにあります。優先順位のあるさまざまな演算子を使用して中置記法を解析することはかなり一般的であるため、pyparsing にはinfixNotation(以前のoperatorPrecedence) 式ビルダーも含まれます。これを使用すると、「AND」、「OR」、「NOT」などを使用してブール式を簡単に定義できます。または、4 関数演算を拡張して、! などの他の演算子を使用することもできます。階乗の場合、またはモジュラスの場合は「%」、または P および C 演算子を追加して順列と組み合わせを計算します。'-1' または 'T' 演算子 (反転および転置用) の処理を​​含む、行列表記用の中置パーサーを作成できます。4 関数パーサーの operatorPrecedence の例 ('!'.

于 2009-09-04T08:02:45.863 に答える
2

私は現在、設計パターンと読みやすいプログラミングの学習ツールとして正規表現パーサーを構築する一連の記事に取り組んでいます。readablecodeを見ることができます。この記事では、シャント ヤード アルゴリズムの明確な使用法を紹介しています。

于 2008-10-09T06:12:02.130 に答える
2

MathEclipse パーサープロジェクトの Java で再帰降下パーサーを実装しました。また、 Google Web Toolkitモジュールとして使用することもできます

于 2008-10-03T13:23:45.133 に答える
1

アルゴリズムは、再帰降下パーサーとして C で簡単にエンコードできます。

#include <stdio.h>
#include <ctype.h>

/*
 *  expression -> sum
 *  sum -> product | product "+" sum
 *  product -> term | term "*" product
 *  term -> number | expression
 *  number -> [0..9]+
 */

typedef struct {
    int value;
    const char* context;
} expression_t;

expression_t expression(int value, const char* context) {
    return (expression_t) { value, context };
}

/* begin: parsers */

expression_t eval_expression(const char* symbols);

expression_t eval_number(const char* symbols) {
    // number -> [0..9]+
    double number = 0;        
    while (isdigit(*symbols)) {
        number = 10 * number + (*symbols - '0');
        symbols++;
    }
    return expression(number, symbols);
}

expression_t eval_term(const char* symbols) {
    // term -> number | expression
    expression_t number = eval_number(symbols);
    return number.context != symbols ? number : eval_expression(symbols);
}

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

expression_t eval_sum(const char* symbols) {
    // sum -> product | product "+" sum
    expression_t product = eval_product(symbols);
    if (*product.context != '+')
        return product;

    expression_t sum = eval_sum(product.context + 1);
    return expression(product.value + sum.value, sum.context);
}

expression_t eval_expression(const char* symbols) {
    // expression -> sum
    return eval_sum(symbols);
}

/* end: parsers */

int main() {
    const char* expression = "1+11*5";
    printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);

    return 0;
}

次のライブラリが役に立つかもしれません: yupana - 厳密に算術演算。 tinyexpr - 算術演算 + C 数学関数 + ユーザーが提供するもの。 mpc - パーサーコンビネータ

説明

代数式を表す一連の記号をキャプチャしましょう。最初の 1 つは数値で、10 進数が 1 回以上繰り返されます。 このような表記をプロダクションルールと呼びます。

number -> [0..9]+

オペランドを持つ加算演算子は別の規則です。シーケンスを表すいずれかnumberまたは任意の記号です。sum "*" sum

sum -> number | sum "+" sum

に置き換えnumberてみてください。これは、次に拡張できるものでありsum "+" sum、最終的に還元できるものは、正しい足し算式です。number "+" number[0..9]+ "+" [0..9]+1+8

他の置換も正しい式を生成します: sum "+" sum-> number "+" sum-> number "+" sum "+" sum-> number "+" sum "+" number-> number "+" number "+" number->12+3+5

少しずつ、すべての可能な代数式を表現する一連の生成規則、別名文法に似ている可能性があります。

expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+                                                                    

オペレータの優先順位を制御するには、他のものに対するプロダクション ルールの位置を変更します。*上記の文法を見てください。プロダクション ルール forがこの下に配置されていると、前に評価+が強制されることに注意してください。実装では、パターン認識と評価を組み合わせるだけで、生産ルールを厳密に反映します。productsum

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

ここでは、最初に評価し、その後に文字termがない場合はそれを返します。これはプロダクション ルールでは左の選択肢です。*term.value * product.value term "*" product

于 2018-01-25T15:05:51.973 に答える