Вычисление списка постфиксных выражений

Я написал программу для рекурсивного вычисления постфиксного выражения в прологе из списка выражений. Например, учитывая следующий список:

[+,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.

Я не понимаю, почему мои значения исчезают или есть ли лучший способ оценить список.


list recursion prolog tail-recursion postfix-notation
person thegalah    schedule 11.04.2013    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Несколько советов по технике программирования. Вы должны использовать сопоставление заголовков и унификацию вместо явной унификации в теле ваших определений предикатов и конструкциях if-else. Вам также следует избегать рекурсии без хвостовой рекурсии, если только ваш алгоритм не является рекурсивным по своей сути (например, обход дерева по порядку). Это облегчит написание, чтение и понимание кода. Прямо сейчас мне даже не хочется отлаживать ваш код, но похоже, что ваша Store2 никогда не будет привязана к целому числу и всегда будет несвязанной переменной, независимо от того, какие входные данные есть в вашей программе.

Теперь к вашей программе. Непонятно, чего вы пытаетесь достичь. Если вы хотите только оценить список формы [Arithmetic_operator, Operand1, Operand2], было бы намного проще написать:

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

Я не вижу необходимости в этом чрезмерно сложном подходе, который вы используете.

Если вы хотите иметь возможность вычислять произвольно сложные выражения, написанные постфиксом, с фиксированной арностью оператора (так что вы можете сказать 2, 3, +, но не 2, 4, 1, + для суммы 7):

  • Read one element from your input
    • Push the element to the top of the stack
    • Try to reduce the stack:
      • pop operator and operands, if on top of the stack
      • оценивать
      • поместить результат обратно на вершину стека
  • Когда ввод пуст, ваш стек - это ваш результат

Вы можете явно определить эффект различных операторов (здесь только + и -) следующим образом:

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].

Таким образом, эти два предиката, evaluate(Input,Stack,Result) и eval_stack(Stack,NewStack), — это все, что вам нужно для оценки допустимых постфиксных арифметических выражений только с операторами фиксированной арности.

person Community    schedule 11.04.2013
comment
Подход, который я пытался использовать, заключался в том, чтобы перевернуть постфиксное выражение, чтобы моя рекурсивная программа могла читать его в обратном порядке справа налево: P Я привел пример, чтобы упростить задачу, ха-ха. Я хочу иметь возможность обрабатывать выражение любого размера. Насколько я понимаю, ваша версия программы продолжает реорганизовывать выражение до тех пор, пока оно не совпадет с одним из предикатов eval_stack, после чего часть выражения заменяется результатом? Спасибо за ваш ответ, я пытаюсь понять это уже пару дней :) - person thegalah; 11.04.2013
comment
@thegalah У меня тоже такое чувство.... :) если для этого нет очень веской причины, всегда старайтесь найти решение, которое читает список Prolog слева направо. Затем вы можете использовать унификацию, сопоставление и хвостовую рекурсию для естественного перебора списков. И да, но посмотрите мое редактирование ответа (и проголосуйте, чтобы другие тоже могли его использовать). - person ; 11.04.2013
comment
@false да, конечно. В то время, когда я отвечал на этот вопрос, я даже не знал, что такое DCG. Я должен посмотреть на это снова, когда я высплюсь. - person ; 18.11.2014
comment
@Boris: ты можешь написать новый ответ! Прогресс происходит - person false; 18.11.2014