問題タブ [shunting-yard]

操車場アルゴリズムの実装を検討していますが、文字列をトークンに分割するための最良の方法を理解するための支援が必要です。

お気づきの方もいらっしゃると思いますが、アルゴリズムの最初のステップは「トークンの読み取り」です。これは、簡単なことではありません。トークンは、数値、演算子、および親で構成できます。

次のようなことをしている場合：

（5 + 1）

単純なstring.split（）は、トークンの配列{"（"、 "5"、 "+"、 "1"、 "）"}を提供します。

ただし、次のように複数桁の数字がある場合は、さらに複雑になります。

（（2048 * 124）+ 42）

これで、単純なstring.split（）はうまくいきません。複数桁の数字が問題です。

レクサーを作成できることは知っていますが、本格的なレクサーを作成せずにこれを行う方法はありますか？

私はこれをJavaScriptで実装しており、可能であればレクサーパスをたどる必要がないようにしたいと思います。「*」、「+」、「-」、「/」の演算子を整数とともに使用します。

私はクラスの JavaScript で Shunting-Yard Algorithm の実装に取り​​組んできました。

これまでの私の仕事は次のとおりです。

これまでのところ問題なく動作します。私がそれを与えると：

((5+3) * 8)

次のように出力されます。

インフィックス: ((5+3) * 8) ポストフィックス
(RPN): 5 3 + 8 *
結果: 64

ただし、単項演算子の実装に苦労しているため、次のようなことができます。

(( -5 +3) * 8)

単項演算子 (否定など) を実装する最良の方法は何でしょうか? また、浮動小数点数を処理するための提案はありますか?

最後にもう 1 つ、私が JavaScript で奇妙なことをしているのを見た人がいたら教えてください。これは初めての JavaScript プログラムで、まだ慣れていません。

学術的な目的で、次のようなユーザー入力式をプロットするアプリケーションを作成する必要があります。f（x）= 1 --exp（3 ^（5 * ln（cosx））+ x）

パーサーを作成するために私が選択したアプローチは、RPNの式をShunting-Yardアルゴリズムで変換し、「cos」などのプリミティブ関数を単項演算子として扱うことです。これは、上記の関数が次のような一連のトークンに変換されることを意味します。

問題は、関数をプロットするために何度も評価する必要があるため、各入力値にスタック評価アルゴリズムを適用することは非常に非効率的であるということです。どうすればこれを解決できますか？RPNのアイデアを忘れる必要がありますか？

問題は、BNF で指定されたような入力関数があるとsin(2-cos(3*A/B)^2.5)+0.756*(C*D+3-B)します。再帰降下アルゴリズムを使用して入力を解析し、ダイクストラのアルゴリズムを使用または変更して、この特定の関数を処理するにはどうすればよいでしょうか? sin | で実行する必要があります。コス | 平方根 | ln では、ダイクストラのアルゴリズムが作業を行う必要があります。

編集:私も尋ねるべきかもしれません:特定の機能を表すためのベストプラクティスまたはデータ構造は何ですか?

EDIT：入力セットは次のように取得できます：

編集: Shunting Yard は、入力関数を RPN に変換するアルゴリズムですが、sin | のような別の関数を受け入れるように拡張するにはどうすればよいですか? コス | 平方根 | ん？再帰降下は、Shunting Yard に必要な拡張を提供しますか?

私はshunting-yard アルゴリズムを実装しています。演算子に欠落している引数がある場合、検出に問題があります。ウィキペディアのエントリはこのトピックに関して非常に悪く、以下の例でもコードがクラッシュします。

たとえば、 には引数3 - (5 + )がないため、正しくありません。+

アルゴリズムが に到達する直前に)、演算子スタックには が含まれ- ( +、オペランド スタックには が含まれます3 5。次に、次のようになります。

• +オペレータースタックからポップします
• +二項演算子であることを発見
• 2 つのオペランドをポップし、演算子を適用し、結果 ( 8) をオペランド スタックにプッシュします。
• (次に、一致するものをスタックからポップし、続行します

+では、引数が欠落していることをどのように検出できますか? ウィキペディアも更新する場合は、さらに称賛します:-)

後置記法から中置記法へのコンバーターを作成しようとしていますが、助けが必要です。infix-to-postfix conversion に関する質問が既にあります。これは、変換に失敗している例を示しています。(注: マイナス記号がありません!)

以下は私のコンバーターの出力です。1 番目の「列」は後置入力、2 番目は中置出力、3 番目はおそらく取得すべきもの (?) です。

この問題を解決できると思いますか、それとも最後の 2 行は実際に正しく変換されていますか? この問題を解決するアルゴリズムをどのように記述しますか?

+より多くの演算子 ( andだけでなく) を単項演算子と 2 項演算子の両方として設定できると仮定してください-。単項演算子は 2 項演算子よりも優先されます。

参考文献

1. Ruby クイズ #148: Postfix から Infix へ、これもGoogle グループから
2. LiteratePrograms で単項演算子をサポートする分流場アルゴリズム (C、Python、Perl )

infix-to-postfix-to-infix コンバーターをテストしていますが、ある種の不確実性が見つかりました。たとえば、単純な中置和

接尾辞に変換できます

等優先度の演算子は累積しないものとします。もしそうなら、私は得る

一方、次の後置式はすべて初期和に変換できます。

これらの後置式はすべて正しいですか?

更新1

そのようなコンバーターを作るとしたら、どのフォームを選びますか? テスト用に 1 つ選択する必要があります。

PHPで文字列を解釈し、簡単な数学計算を実行して、式がtrueかfalseかについてブール結果を返すことができるものを探しています。

例えば：

1. 「3*{mysalary} / 9=10000」のタイプを訴える
2. PHPは、これを2つの式に分割します-explode（'='、string）;
3. PHPはデータベースフィールドのリストを取得し、「{}」で区切られたフィールドをデータ（intにタイプキャスト）に置き換えます。
4. 次に、PHPは数式を評価します
5. 次に、phpは左側と右側を比較します
6. ブール結果が生成されました。

複雑に聞こえるかもしれませんが、必要なのは非常に単純なことだけです。制約は次のとおりです。1/数学演算子は次のように固定されます：+-/ * 2 /比較演算子は次のように固定されます：=> <> = <= 3 /浮動小数点比較は必要ありません。すべて、整数レベルで実行できます。したがって、必要に応じて、または単に最終結果を丸めるだけで、任意の除算を丸めることができます。

1つの比較演算子を使用して、式は2つだけになります。なんらかのエラーが発生した場合は、falseを返します。

誰かがすでにこれを行うことができる何かを見たことがありますか？私は何かを作ることができることを知っていますが、なぜ車輪の再発明を正しく行うのですか？

何も見たことがない場合は、これを作成するときに考えられる「落とし穴」または警告をいくつか挙げてください。

もう少し読んだ後、私は操車場アルゴリズムを使用できることに気付きました。PHPでこれを実装している人はいますか？

evalはこれを実行する簡単な方法である可能性があることは承知していますが、ユーザーがこの方法を使用して何かを簡単に壊したり、構文エラーを引き起こしたりする可能性があるのではないかと心配しています。ソリューションに含めたくない、または含める場合は、使用方法を厳密に制御する必要があります。

ありがとう。

ジェイソン

Shunting Yard (SY) アルゴリズムを使用して構文を解析しようとしています。構文には次のコマンドが含まれます (これらは他にもたくさんあります!)

基本的に、setxy は関数ですが、関数の引数セパレーターは必要ありません。これにより、括弧と関数引数の区切り記号がないため、SY を介して実行することが非常に困難 (不可能?) になります。

SY を使用して、括弧なし/関数引数セパレーターなしの関数を解析できるかどうか、または別の解析アルゴリズムに進む必要があるかどうか、考えはありますか? もしそうなら、あなたはどちらをお勧めしますか？

ありがとう！DJS22

私は実際にCommonLispで自分で何かを書き、操車場アルゴリズムを実装することに取り組んでいます。かなり醜く出てきて、そのLispy-nessを疑っても大丈夫だと思いましたが、REPLで関数をテストすると、タイトルにエラーが表示されます。

コードは次のとおりです。テストケースは(shunting-yard '(3 + 5))です。

コード自体にエラーがありますか（私の推測）、それとも私のテストケースにありますか？

たくさんの事前のおかげで、これは書くのが本当に楽しかったです、そして私は他の何かに取り組むのを待つことができません、しかし私がこれを動かした後でのみ。