Javaを使用して単純なLisp式エバリュエーターを実装しようとしています。このテーマに関する情報は実際には豊富にありますが、結果に到達するためにすべて2つの別々のスタックを使用しているようです。1つのスタックだけを使用してそのようなプログラムを実装することは可能かどうか、そしてそのためのいくつかの擬似コードはどのように見えるのか疑問に思います。
ありがとう。
私が話していることの詳細については、を参照してください
2659 次
2 に答える
3
あなたがリンクした両方のインタープリターは、非常に重要な仮定を立てています: +、-、* などはすべてバイナリ関数です。つまり、常に正確に 2 つの引数を取ります。(+ 1 2 3 4 5)実際の Lisp では、一連の数値を合計すると言うことができます。ただし、各演算子のアリティが既知であるという単純化した仮定を受け入れる場合は、1 つのスタックのみでこれを行うことができます。重要なのは、スタックを上下逆さまにすることです。
リンクしたインタープリターには、次のようなスタックがあります。
下 -> ( + ( - 2 1 ) 4 )<- 上 (ここから押してはじきます)
ただし、式を右から逆方向に読み取り、次のようにスタックを構築することもできます。
上 -> ( + ( - 2 1 ) 4 )<- 下
次に、基本的にRPN、逆ポーランド記法を取得します。RPN はスタックとうまく連携します。
アルゴリズムは次のようになります。
- 括弧が表示された場合は無視してください
- オペランドが見つかった場合は、それをスタックにプッシュします
- オペレーターが表示された場合は、それを呼び出します。演算子は必要な数の値を取り出し、その結果をスタックにプッシュします
たとえば、( + ( - 2 1 ) 4 )。アルゴリズムの動作は次のとおりです。
スタック: 空 読み取り: ) アクション:括弧は無視されました。左： ( + ( - 2 1 ) 4
スタック: 空 読み取り: 4 アクション:オペランドがスタックにプッシュされました。左： ( + ( - 2 1 )
スタック: 4読み取り: ) アクション:括弧は無視されました。左： ( + ( - 2 1
スタック: 4読み取り: 1 アクション:オペランドがスタックにプッシュされました。左： ( + ( - 2
スタック: 1 4読み取り: 2 アクション:オペランドがスタックにプッシュされました。左： ( + ( -
スタック: 2 1 4読み取り: -アクション:オペレーターが呼び出されました。スタックから 2 と 1 をポップしてから、プッシュ2-1=1します。 左： ( + (
スタック: 1 4読み取り: ( アクション:括弧は無視されます。左： ( +
スタック: 1 4読み取り: + アクション:オペレーターが呼び出されました。スタックから 1 と 4 をポップし、プッシュ1+4=5します。 左： (
スタック: 5読み取り: ( アクション:括弧は無視されました。左： なし
終わり！予想通り、結果は 5 です。
括弧を無視することについてのPS。入力する式が整形式である限り、これは完全に機能しますが、整形式でない式を取り、それらに無意味な値を与えることができます。例えば(+ - + 1 2 3 4)として解釈され(+ (- (+ 1 2) 3) 4)ます。この動作を防ぎたい場合は、閉じ括弧をスタックにプッシュするだけです。演算子を呼び出すときが来たら、引数と 1 つの余分なトークンを取り出します。token が close-paren であることを確認してください。そうでない場合は、エラーをスローします。結果が得られたら、それをスタックにプッシュします。読み取った次のトークンが開きかっこであることを確認してから、破棄します。
PPS 実際の Lisp のように、関数への引数自体が関数である場合、これはすべてより複雑になります。その場合、RPN が依存する演算子/オペランド間の便利な区別がなく、グループ化要素として括弧にもっと注意を払う必要があります。スタックが 1 つだけで、変数アリティとオペランドとしての関数を使用して、本格的な Lisp 式評価器を実行できるかどうかはわかりません。
于 2012-10-31T08:11:36.433 に答える
0
スタックのないLispスタイルの電卓に役立つことを願って います
于 2013-01-13T16:08:37.603 に答える