インミックス式をツリーに変換するにはどうすればよいですか？最初にプログラミングするのではなく、手動でやりたいと思います。たとえば、この中置式を見てみましょう：インフィクスをバイナリツリーに変換する
b = (x * a) - y/b * (c + d)
これをツリーにするためのルールは何ですか？またはこれを行うためにどのようなステップをお勧めしますか？時々これらの式は、それらの中に明示的な括弧を持っていないので、私はここに問題を抱えている：
b = x * a - y/b * c + d
あなたはここに記述している問題は、一般的にを解析表現と呼ばれ、一般的にプロセス内の2つのステップがあります：
最初にがあります。ここでは、入力文字列を取り出し、入力の1つの「ピース」を表す小さな論理ユニットに分割します。例えば、あなたがトークンのこの一連生じる可能性があります
b = x * a - y/b * c + d
入力文字列与えられた：
[b] [=] [x] [*] [a] [-] [y] [/] [b] [*] [c] [+] [d]
この方法は、あなたがに「が入力され、「入力文字の列である」から移動します個々の変数、演算子などのシーケンス。この手順を実行するには多くの方法があります。また、手作業で文字列を処理したり、正規表現で作業したりすることもよくあります。最初のステップとして、この部分が機能するかどうかを確認してください。
2番目のステップは、おそらく最もよく掛かっているもので、の構文解析です。トークンのシーケンスを取得してステートメントの意味を再構成します。これには通常、演算子の優先順位を計算し、実際に必要なツリー構造を構築する必要があります。そのツリーは、しばしば、表現ツリーまたはabstract syntax tree（AST）と呼ばれます。
これを実行する方法はたくさんあります。式を解析するために、私の個人的な行き先はDijkstra's shunting-yard algorithmです。このアルゴリズムは、2つのスタックを維持し、スタックを使用して一度に1つのトークンを処理して、演算子を適用する必要があるかどうかを判断することによって機能します。
これを行う方法の例を見たい場合は、私が定期的に教える離散数学クラスのためにtruth table generatorを作成しました。論理式を入力すると、コードがスキャンしてトークンシーケンスを取得した後、シャントヤードアルゴリズムを使用してASTを構築し、ASTを使用して真理値表ツールを生成します。 source codeは、各ステップが別々に実行されるように分解されており、参考になる場合があります。