Инфиксная форма записи числа

 

Введение 

Существуют три вида записи выражений:

1. инфиксная форма, в которой  оператор расположен между операндами (например, "а + b");

2. постфиксная форма, в которой  оператор расположен после операндов  ("а b + ");

3. префиксная форма, в которой  оператор расположен перед операндами ("+ а b").

 Постфиксная и префиксная  формы образуют т.н. польскую  и обратную форму записи. Автоматизация вычисления выражений в обратной польской нотации основана на использовании стека.

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

 

2 Обоснование выбора метода решения задач

При решении задач, был использован алгоритм сортировочной станции.

В случае перевода в постфиксную  форму, был организован стек, в  который заносился каждый считанный  символ. Применение стека обусловлено  тем, что необходимо разбирать входное  выражение на операторы и операнды, после чего собирать каждое в отдельности, хранить и в зависимости от иерархии операторов, проставлять скобки. При выполнении этих действий, порядок  входного выражения существенно  изменится, что соответствует системе  LIFO в стеке (Lead Input First Output).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3 Описание алгоритма решения задач

При решении задачи перевода из инфиксной формы в префиксную, был использован алгоритм сортировочной станции, разработанный Эдсгером Дейкстрой:

• Пока есть ещё символы для чтения:
• Читаем очередной символ.
• Если символ является числом, добавить его к выходной строке.
• Если символ является символом функции, помещаем его в стек.
• Если символ является открывающей скобкой, помещаем его в стек.
• Если символ является закрывающей скобкой:
• До тех пор, пока верхним элементом стека не станет открывающая скобка, выталкиваем элементы из стека в выходную строку. При этом открывающая скобка удаляется из стека, но в выходную строку не добавляется. Если после этого шага на вершине стека оказывается символ функции, выталкиваем его в выходную строку. Если стек закончился раньше, чем мы встретили открывающую скобку, это означает, что в выражении либо неверно поставлен разделитель, либо не согласованы скобки.
• Если символ является оператором о1, тогда:
• пока…
• … (если оператор o1 ассоциированный, либо лево-ассоциированный) приоритет o1 меньше либо равен приоритету оператора, находящегося на вершине стека…
• … (если оператор o1 право-ассоциированый) приоритет o1 меньше приоритета оператора, находящегося на вершине стека…
• … выталкиваем верхние элементы стека в выходную строку;
• помещаем оператор o1 в стек.
• Когда входная строка закончилась, вытолкнуть все символы из стека в выходную строку. В стеке должны были остаться только символы операторов; если это не так, значит в выражении не согласованы скобки.

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

Входная последовательность:

((A+B)*C – (D-E))^(F+G).

Вычислим префиксную форму с помощью интернет-сервиса WolframAlfa:

^-*+ ABC – DE + FG

Реверсируем строку, заменяя открывающиеся  скобки на закрывающиеся, а закрывающиеся  на открывающиеся:

(G+F)^((E-D) – C*(B+A)).

Представим выражение в постфиксной  форме:

GF + ED – CBA +*-^

Реверсируем полученный результат:

^-*+ ABC – DE + FG.

4 Результаты работы программы

Результаты работы программы представлены на рисунке 1:

Рисунок 1 – Результат работы программы

 

5 Заключение

В ходе данной работы была подробно изучена польская форма записи: постфиксная и префиксная запись.

Разработанная программа на языке программирования Turbo Pascal.

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

Так же были изучены стеки. Стек –  это память работающая по принципу «Последним пришел–первым вышел». При выполнении работы был организован стек, а так же разработаны механизмы занесения данных в эту область памяти, и их последующее извлечение.

При решении задач так же была использована рекурсия.

Преимущество рекурсивного определения  объекта заключается в том, что  такое конечное определение теоретически способно описывать бесконечно большое  число объектов. С помощью рекурсивной  программы же возможно описать бесконечное  вычисление, причём без явных повторений частей программы.

 

Приложение А. Листинг  программы

program kurslab;

 

uses Crt;

 

const

  oper1 = ['+', '-']; { низкоприоритетные операторы }

  oper2 = ['*', '/', '^']; { высокоприоритетные отераторы }

  symbol = ['a'.. 'z', 'A'.. 'Z', '0'.. '9', '.'];  { литералы }

 

var

  menu: byte;

  sym: char;

  so, si: string;

  p: word;   

 

{ Считывание p-того символа из  строки }

procedure getsym;

begin

  while (p <= length(si)) and (si[p] in [#32, #9]) do inc(p); { Пропуск пробелов и табуляций }

  if p > length(si) then

    sym := #0

  else

  begin

    sym := si[p];

    inc(p)

  end;

end;

 

procedure expression; forward; { Прототип процедуры построения результирующего выражения }

 

{ Построение переменной }

procedure get_var;

begin

  so := so + #32; { разделяем переменные пробелом }

  { формируем следующую переменную }

  while sym in symbol do { последывательным считыванием символа }

  begin                  { при помощи процедуры getsym  }

    so := so + sym;      { и добавлением его к результирующей строке }

    getsym               { до первого встреченного оператора }

  end

end;

 

{ отделение переменных }

procedure term;

var

  a: char;

begin

  if sym = '(' then  { если символ - скобка, то  }

  begin

    getsym;          { считываем символ }

    expression;      { считываем выражение }

    getsym           { считываем символ }

  end

  else               { иначе считываем переменную }

    get_var;

  while sym in oper2 do

  begin

    a := sym;

    getsym;

    term;

    so := so + a

  end

end;

 

{ построение результирующей строки }

procedure expression;

var

  a: char;

begin

  if sym = '+' then

    getsym

  else if sym = '-' then

  begin

    a := '-';

    getsym

  end

  else

    a := #32;

  term;

  if a = '-' then

    so := so + ' (-)';

  while sym in oper1 do

  begin

    a := sym;

    getsym;

    term;

    so := so + a

  end

end;

 

function Reverse(InStr: string): string;

var

  I, L: Byte;

  Res : string;

begin

  Res := '';

  L   := Length(InStr);

  for I := L downto 1 do

  begin

    if InStr[I] = ')' then InStr[I] := '(' else

    if InStr[I] = '(' then InStr[I] := ')';

    Res := Res + InStr[I];

  end;

  Reverse := Res;

end;

 

begin

  clrscr;

  TextColor(LightGreen);

  repeat

    writeln('1) Infix to Prefix');

    writeln('2) Infix to Postfix');

    writeln('3) Exit');

    readln(menu);

   

    case menu of

   

      1:

        begin

          write('Введите строку: ');

          read(si);

          write(si, ' = ');         

          si := Reverse(si); {Реверсируем строку}

          so := #32;

          p := 1;

          getsym; { читаем первый символ }

          expression; { формируем выражение }

          so := Reverse(so);{Реверсируем результат}

          writeln(so);  { вывод результата }    

        end;

         

     

      2:

        begin

          write('Введите строку: ');

          read(si);

          so := #32;

          p := 1;

          getsym; { читаем первый символ }

          expression; { формируем выражение }

          writeln(si);

          writeln(so);  { вывод результата }    

        end;

     

      3: break;

    end;

  until false;

  readln;

end.