1

プロローグの後置式を式リストから再帰的に評価するプログラムを作成しました。たとえば、次のリストがあるとします。

[+,1,2]

3 を返す必要があります。私が述語を作成した方法は、値を逆方向に読み取るように、リストの最後に到達するまで自分自身を再帰的に呼び出すことです。(このリストを左から右に読むのと同じ: [2,1,+])。

私の問題は、再帰呼び出しで複数の値を返そうとすると、すべての値が突然消えることです。

コードは次のとおりです。

eval_list([Head|Tail],_,Result):-
   Tail==[], % last element of list
   Result=Head,
   write(Head),
   write(' was stored in Result!\n').

eval_list([Head|Tail],Store1,Result):-
      eval_list(Tail,Store2, NewResult),
      (\+integer(Store2))
   ->
      % if no integer is bound to Store2, bind Store1 to Head
      Store1=Head,
      Result is NewResult,
      write(Head),
      write(' is stored value!\n')
   ;  (integer(Store2)) ->
    % if an integer is bound to store2, we perform operation specified by the Head with the stored number
      X is Store2+NewResult,
      Result is X,
      write('performed operation!\n')
   ;
      % if doesnt catch either of these states the program is broken
      (  print('something broke\n'),
         print(Store1),
         nl,
         print(Store2),
         nl,
         print(Head),
         nl,
         print(Result),
         nl
      ).

次の出力が得られます。

?- eval_list([+,1,2],X,Result).
2 was stored in Result!
1 is stored value!
something broke
_G1162
_L147
+
_G1163
true.

値が消える理由、またはリストを評価するためのより良い方法があるかどうかがわかりません。

4

1 に答える 1

6

プログラミングテクニックに関するアドバイス。述語定義の本体と if-else 構造では、明示的な統合ではなく、ヘッド マッチングと統合を使用する必要があります。また、アルゴリズムが本質的に再帰的でない限り (たとえば、ツリーの順序どおりのトラバーサル)、末尾再帰的でない再帰も避ける必要があります。これにより、コードが書きやすくなり、読みやすくなり、理解しやすくなります。今のところ、あなたのコードをデバッグする気さえありませんが、あなたのコードがStore2整数にバインドされることは決してないようで、プログラムへの入力に関係なく、常にバインドされていない変数になります。

今あなたのプログラムに。あなたが達成しようとしていることは明らかではありません。フォームの list のみを評価したい場合は、次の[Arithmetic_operator, Operand1, Operand2]ように書く方がはるかに簡単です。

arith_eval(Expression_list, Result) :-
    Arithmetic_expr =.. Expression_list, % look up what =.. stands for!
    Result is Arithmetic_expr.

あなたが使用しているこの過度に複雑なアプローチの必要性はわかりません。

任意に複雑な式を評価できるようにしたい場合は、後置式で記述され、演算子のアリティが固定されています (したがって、合計 7 に対してと言うことができますが2, 3, +、 とは言えません):2, 4, 1, +

  • 入力から 1 つの要素を読み取る
    • 要素をスタックの一番上にプッシュします
    • スタックを減らしてみてください:
      • スタックの一番上にある場合は、pop 演算子とオペランド
      • 評価
      • 結果をスタックの一番上に戻す
  • 入力が空の場合、スタックは結果です

次のように、さまざまな演算子の効果を明示的に定義できます (ここでは、 と のみ+) -。

eval_stack([+,A,B|Tail],[Result|Tail]) :-
    number(A), number(B),
    !,
    Result is B + A.
eval_stack([-,A,B|Tail],[Result|Tail]) :-
    number(A), number(B),
    !,
    Result is B - A.
eval_stack(Stack,Stack).

演算子がスタックの一番上に一致し、その下にオペランドがある場合に適用され、結果がスタックにプッシュされるか、スタックが変更されないままになることに注意してください。

そして、入力からスタックにプッシュできます。

evaluate([Next|Rest], Stack, Result) :-
    eval_stack([Next|Stack],NewStack),
    evaluate(Rest,NewStack,Result).
evaluate([],Result,Result). % end of input

したがって、これを次のように呼び出すことができます。

?- evaluate([2,3,+,3,6,-,+],[],Result).
Result = [2].

?- evaluate([2,3,4,-,-,5,+],[],Result).
Result = [8].

?- evaluate([2,3,4,-,-,5,+,1,3,2,-],[],Result).
Result = [1,1,8].

したがって、これら 2 つの述語 ,evaluate(Input,Stack,Result)とeval_stack(Stack,NewStack)は、固定アリティ演算子のみを使用して有効な後置算術式を評価するために必要なすべてです。

于 2013-04-11T11:38:06.930 に答える