Ответ в теме: Вычисление арифметического выражения (ПОЛИЗ)

      Комментарии к записи Ответ в теме: Вычисление арифметического выражения (ПОЛИЗ) отключены
#2534

Для начала нужно описать все нужные операторы и их приоритеты:

binary_operator(0'-, minus).
binary_operator(0'+, plus).
binary_operator(0'*, multiplication).
binary_operator(0'/, division).
unary_operator(0'-, unary_minus).
priority(open_bracket, -1).
priority(close_bracket, 0).
priority(plus, 1).
priority(minus, 1).
priority(multiplication, 2).
priority(division, 2).
priority(unary_minus, 3).

Тут видно, что приоритеты унарных операторов должны быть выше чем у бинарных, а у скобок — наименьшими (это важно, т.к. при обработке оператора из стека должны выталкиваться операторы с большим приоритетом, но процесс должен останавливаться также и на скобках).

Функции выталкивания из стека до открывающей скобки и до оператора с меньшим приоритетом:

pop_stack_before_open_bracket([open_bracket|TailStack], PoppedBuffer, TailStack, PoppedBuffer):-!.
pop_stack_before_open_bracket([Head|TailStack], ExpressionBuffer, PoppedStack, PoppedBuffer):-
pop_stack_before_open_bracket(TailStack, [Head|ExpressionBuffer], PoppedStack, PoppedBuffer).
pop_stack_before_less_priority(_Priority, [], PoppedBuffer, [], PoppedBuffer):-!.
pop_stack_before_less_priority(Priority, [HeadStack|TailStack], PoppedBuffer, [HeadStack|TailStack], PoppedBuffer):-
priority(HeadStack, HeadStackPriority), HeadStackPriority < Priority, !. % stop popping
pop_stack_before_less_priority(Priority, [HeadStack|TailStack], ExpressionBuffer, PoppedStack, PoppedBuffer):-
pop_stack_before_less_priority(Priority, TailStack, [HeadStack|ExpressionBuffer], PoppedStack, PoppedBuffer).

Тут важно, что при выталкивании скобок скобок нерекурсивным решением является лишь случай с открывающей скобкой в начале стека — вариант с пустым стеком не рассматривается, т.к. он бы означал нарушение баланса скобок в выражении.

Преобразование выражений в польскую инверсную запись на Prolog записывается полностью по приведенному выше алгоритму (каждое правило соответствует одному пункту алгоритма):

string_to_expression(_BinaryOrUnary, "", Stack, Buffer, Expression):-
%% if string is empty - pop the stack
!, reverse(Stack, ReversedStack),
append(ReversedStack, Buffer, ReversedExpression),
reverse(ReversedExpression, Expression).
string_to_expression(_BinaryOrUnary, String, Stack, Buffer, Expression):-
%% if read the number - push it into buffer
get_positive(String, Number, TailString), !,
string_to_expression(binary, TailString, Stack, [(number, Number)|Buffer], Expression).
string_to_expression(_BinaryOrUnary, [0'(|TailString], Stack, Buffer, Expression):-
%% if read the open bracket - push it into stack
!, string_to_expression(unary, TailString, [open_bracket|Stack], Buffer, Expression).
string_to_expression(_BinaryOrUnary, [0')|TailString], Stack, Buffer, Expression):-
%% if read the close bracket - pop stack before open bracket
!, pop_stack_before_open_bracket(Stack, Buffer, PoppedStack, PoppedBuffer),
string_to_expression(binary, TailString, PoppedStack, PoppedBuffer, Expression).
string_to_expression(binary, [OperatorSymbol|TailString], Stack, Buffer, Expression):-
%% if read binary_operator - pop stack before head stack has bigger or equal priority than that binary_operator
binary_operator(OperatorSymbol, Operator), !,
priority(Operator, OperatorPriority),
pop_stack_before_less_priority(OperatorPriority, Stack, Buffer, PoppedStack, PoppedBuffer),
string_to_expression(unary, TailString, [Operator|PoppedStack], PoppedBuffer, Expression).
string_to_expression(unary, [OperatorSymbol|TailString], Stack, Buffer, Expression):-
unary_operator(OperatorSymbol, UnaryOperator),
priority(UnaryOperator, OperatorPriority),
pop_stack_before_less_priority(OperatorPriority, Stack, Buffer, PoppedStack, PoppedBuffer),
string_to_expression(unary, TailString, [UnaryOperator|PoppedStack], PoppedBuffer, Expression).

Видно, что обработка унарного оператора ничем не отличается от бинарного, но в стек добавляется другой символ (unari_minus вместо minus) — это позволит корректно выполнить их обработку при вычислении выражения.

На скриншоте показаны примеры, с которыми проводилась проверка корректности преобразования в ПОЛИЗ.