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

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

Главная Форумы Программирование Помощь с решением задач на Prolog Задачи на строки и файлы Вычисление арифметического выражения (ПОЛИЗ)

В этой теме 3 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 1 год, 7 мес. назад.

  • Автор
    Сообщения
  • #2531

    questioner
    Участник

    Нужно реализовать калькулятор арифметических выражений на SWI Prolog. При этом требуется сначала преобразовать выражение в обратную польскую запись (ПОЛИЗ), а уже потом вычислить его значение.

  • #2532

    ПОЛИЗ — очень удобный формат для вычисления выражений, он отличается лишь тем, что операторы располагаются после операндов, т.е. 3+5 будет записываться как 3 5 +
    Алгоритм преобразования строки в польскую инверсную запись использует вспомогательный стек и формирует на выходе новую строку в формате ПОЛИЗ:

    1. если исходная строка пуста нужно вытолкнуть из стека все содержимое в выходную строку и завершить работу;
    2. если в начале строки располагается число — оно переписывается в выходную строку, остальная часть строки обрабатывается рекурсивно;
    3. если в начале строки стоит открывающая скобка — она добавляется в стек, остальная строка обрабатывается рекурсивно;
    4. если в начале строки стоит закрывающая скобка — из стека в выходную строку вытесняется все до тех пор, пока не встретится открывающая скобка (сами скобки в строку не вытесняются);
    5. если в начале строки стоит оператор — из стека в выходную строку вытесняется все до тех пор, пока не встретится оператор с меньшим приоритетом или скобка. Считанный оператор добавляется в обновленный стек, а остальная часть строки обрабатывается рекурсивно.

    Если выражение может содержать унарные операторы — то алгоритм незначительно усложняется — необходим флажок, несущий информацию о типе следующего оператора — он является бинарным если перед ним стоит закрывающая скобка или число.

  • #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) — это позволит корректно выполнить их обработку при вычислении выражения.

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

  • #2536

    Мы смогли преобразовать строку в ПОЛИЗ, теперь нужно вычислить выражение. Для начала надо описать поведение операторов — функция обработки унарного оператора принимает один операнд, а бинарного — два. Сама обработка операндов тривиальна — например, унарный минус возвращает -Operand:

    calculate_binary_operator(plus, LeftOperand, RightOperand, Result):-
      !, Result is LeftOperand + RightOperand.
    calculate_binary_operator(minus, LeftOperand, RightOperand, Result):-
      !, Result is LeftOperand - RightOperand.
    calculate_binary_operator(multiplication, LeftOperand, RightOperand, Result):-
      !, Result is LeftOperand * RightOperand.
    calculate_binary_operator(division, LeftOperand, RightOperand, Result):-
      !, Result is LeftOperand / RightOperand.
      
    calculate_unary_operator(unary_minus, Operand, OperatorResult):-
      OperatorResult is -Operand.

    Функция вычисления выражения, записанного в ПОЛИЗ использует вспомогательный буфер для хранения операндов и промежуточных вычислений:

    1. если выражение кончилось (эквивалентно пустому списку), то в буфере должно быть единственное значение, которое и является результатом вычислений;
    2. если в начале выражения стоит число — оно перемещается в буфер;
    3. если в начале стоит унарный оператор — из буфера выбирается первое число, к которому этот оператор применяется, результат помещается в буфер;
    4. если в начале строки стоит бинарный оператор — первые два числа буфера — операнды, к которым применяется оператор, результат помещается в буфер.

    calculate_reverse_polish_notation([], [Result], Result):-!.
    calculate_reverse_polish_notation([(number, Value)|Tail], Operands, Result):-
      calculate_reverse_polish_notation(Tail, [Value|Operands], Result), !.
    calculate_reverse_polish_notation([UnaryOperator|Tail], [Operand|TailOperands], Result):-
      calculate_unary_operator(UnaryOperator, Operand, OperatorResult),
      calculate_reverse_polish_notation(Tail, [OperatorResult|TailOperands], Result).
    calculate_reverse_polish_notation([Operator|Tail], [RightOperand, LeftOperand|TailOperands], Result):-
      calculate_binary_operator(Operator, LeftOperand, RightOperand, OperatorResult),
      calculate_reverse_polish_notation(Tail, [OperatorResult|TailOperands], Result).

    Для удобства можно написать вспомогательную функцию, которая принимает строку, преобразует ее в ПОЛИЗ, вычисляет выражение и возвращает число:

    calculate_string(String, Result):-
      string_to_expression(unary, String, [], [], Expression),
      calculate_reverse_polish_notation(Expression, [], Result).

Для ответа в этой теме необходимо авторизоваться.