Postfix expression list

Question

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

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

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

Answer 1

Некоторые рекомендации по технике программирования. Вы должны использовать совпадение и унификацию головы вместо явной унификации в теле ваших определений предикатов, а конструкции 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):

• Прочитайте один элемент из вашего входа
  • Нажмите элемент в верхней части стека
  • Попробуйте уменьшить стек:
    • поп-оператор и операнды, если на вершине стек
    • оценить
    • толчок результат обратно на вершину стека
• Когда вход пуст, ваш стек ваш результат

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

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) все, что бы необходимо оценить действительные арифметические выражения после исправления только с операторами фиксированной аргументации.