6225

Перевод числа из инфиксной формы в постфиксную

Курсовая

Информатика, кибернетика и программирование

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

Русский

2012-12-30

199 KB

236 чел.

1 Введение

Одной из главных причин, лежащих в основе появления языков программирования высокого уровня, являются вычислительные задачи, требующие больших объёмов рутинных вычислений. Поэтому к языкам пpогpаммиpования предъявлялись требования максимального приближения формы записи вычислений к естественному языку математики. В этой связи одной из пеpвых областей системного пpогpаммиpования сфоpмировалось исследование способов тpансляции выpажений. Здесь получены многочисленные pезультаты, однако наибольшее pаспpостpанение получил метод тpансляции с помощью обpатной польской записи, которую в 1920 году пpедложил польский математик Ян Лукашевич.

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

В данной курсовой работе будет реализован перевод выражений из инфиксной формы в постфиксную.


2 Постановка задачи

 Необходимо написать программу, выполняющую перевод выражения из инфиксной формы в постфиксную, включающего операции сложения, вычитания, умножения, возведения в степень и деления, операнды (A, B, C)

Дополнительные данные, необходимые для решения:

Переменные A, B, C
3
 Обоснование выбора метода решения

Рассмотрим алгоритм реализации данной программы на примере с использованием бинарного дерева (алгоритм 1)

Алгоритм 1.

Пусть задано пpостое аpифметическое выpажение вида:

(A+B)*(C+D)-E (1)

Пpедставим это выpажение в виде деpева, в котоpом узлам соответствуют опеpации, а ветвям - опеpанды.Постpоение начнем с коpня, в качестве котоpого выбиpается опеpация, выполняющаяся последней. Левой ветви соответствует левый опеpанд опеpации, а пpавой ветви - пpавый. Деpево выpажения (1) показано на pисунке 1.

                           -

                         /   \

                       /       \

                      *         E

                    /    \

                  /        \

                /            \

              /                \

            +                    +

           / \                    / \

        /      \                /     \

      A       B            C      D

                      Pисунок 1

Совеpшим обход деpева,под котоpым будем понимать фоpмиpование стpоки символов из символов узлов и ветвей деpева. Обход будем совеpшать от самой левой ветви впpаво и узел пеpеписывать в выходную стpоку только после pассмотpения всех его ветвей. Результат обхода деpева имеет вид:

AB+CD+*E- (2)

Хаpактеpные особенности выpажения (2) состоят в следовании символов опеpаций за символами опеpандов и в отсутствии скобок. Такая запись называется обpатной польской записью.

Обpатная польская запись обладает pядом замечательных свойств, котоpые пpевpащают ее в идеальный пpомежуточный язык пpи тpансляции. Во-пеpвых, вычисление выpажения, записанного в обpатной польской записи, может пpоводиться путем однокpатного пpосмотpа, что является весьма удобным пpи генеpации объектного кода пpогpамм. Напpимеp, вычисление выpажения (2) может быть пpоведено следующим обpазом:

# п/п

Анализируемая строка

Действие

0

AB + C D + * E -

r1=A+B

1

r1 C D + * E -

r2=C+D

2

r1 r2 * E -

r1=r1*r2

3

r1 E -

r1=r1-E

4

r1

Вычисление окончено

Здесь r1,r2 - вспомогательные пеpеменные.

Алгоритм 2.

Во-втоpых, получение обpатной польской записи из исходного выpажения может осуществляться весьма пpосто на основе пpостого алгоpитма, пpедложенного Дейкстpой (алгоритм 2). Для этого вводится понятие стекового пpиоpитета опеpаций (таблица 1):

Операция

Приоритет

(

0

)

1

+|-

2

*|/

3

**

4

Таблица 1

Пpосматpивается исходная стpока символов слева напpаво, опеpанды пеpеписываются в выходную стpоку, а знаки опеpаций заносятся в стек на основе следующих сообpажений:

  •  а) если стек пуст, то опеpация из входной стpоки пеpеписывается в стек;
  •  б) опеpация выталкивает из стека все опеpации с большим или pавным пpиоpитетом в выходную стpоку;
  •  в) если очеpедной символ из исходной стpоки есть откpывающая скобка, то он пpоталкивается в стек;
  •  г) закpывающая кpуглая скобка выталкивает все опеpации из стека до ближайшей откpывающей скобки, сами скобки в выходную стpоку не пеpеписываются, а уничтожают дpуг дpуга.

Пpоцесс получения обpатной польской записи выpажения (1) схематично пpедставлен на pисунке 2:

Просматриваемый символ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Входная строка

(

A

+

B

)

*

(

C

+

D

)

-

E

Состояние стека

(

(

+

(

+

(

*

(

*

(

*

+

*

+

(

*

*

(

*

-

-

Выходная строка

A

B

+

C

D

+

*

E

-

Рисунок 2

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

Обратная польская запись обладает pядом замечательных свойств, котоpые пpевpащают ее в идеальный пpомежуточный язык пpи тpансляции. Во-пеpвых, вычисление выpажения, записанного в обpатной польской записи, может пpоводиться путем однокpатного пpосмотpа, что является весьма удобным пpи генеpации объектного кода пpогpамм.

Во-втоpых, получение обpатной польской записи из исходного выpажения может осуществляться весьма пpосто на основе пpостого алгоpитма, пpедложенного Дейкстpой – метод стеков с приоритетами (алгоритм 2).

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


4
 Обоснование выбора структур данных

Для решения поставленной задачи мы можем использовать стек или бинарное дерево. Но преимущества стека для решения данной задачи не только в том, что для реализации мы будем использовать интерацию. Когда мы достигаем операции, то относящиеся к ней операнды будут двумя предыдущими элементами. Т. е. данная структура использует принцип LIFO (Last In - First  Out, последним пришел – первым вышел). Именно такой же принцип обслуживания реализуется и в стеке. Поэтому его удобнее всего использовать.

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO. Для реализации стеков используются указатели, связывающие последовательные элементы . Эта реализация освобождает нас от использования непрерывной области памяти для хранения стека и, следовательно, от необходимости перемещения элементов при вставке или удалении элементов стека. Однако ценой за это удобство становится дополнительная память для хранения указателей.

В этой реализации стек состоит из ячеек, каждая из которых содержит элемент стека и указатель на следующую ячейку. Если стек состоит из элементов a1, a2, …, an, то для i = 1, 2, …, n-1, ячейка, содержащая элемент ai, имеет также указатель на ячейку, содержащую элемент ai+1. Ячейка, содержащая элемент an, имеет указатель nil (нуль). Имеется также ячейка header (заголовок), которая указывает на ячейку, содержащую a1. Ячейка header не содержит элементов стека. В случае пустого стека заголовок имеет указатель nil, не указывающий ни на какую ячейку. Стек показан на рисунке 3.

 

Рисунок 3. Стек

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

Используя же бинарное дерево, нам нужно будет писать сложные и громоздкие процедуры построения и обхода дерева-формулы, в то время как процедуры для добавления элемента в стек являются простыми и удобными в использовании.


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

 Основной алгоритм программы был описан в п. 3. Здесь же хотелось бы более подробно рассмотреть работу функций push и pop.

Функция push.

Функция push добавляет элемент в стек. При добавлении элемента в стек кроме создания элемента (рисунок 4) и заполнения его информационной части (рисунок 5) требуется связать его с предыдущим элементом (рисунок 6) и обновить указатель на вершину стека (рисунок 7).

Рисунок 4. Создание элемента

Рисунок 5. Заполнение информационной части


Рисунок 6. Связывание элемента с предыдущим

Рисунок 7. Обновление указателя на вершину стека

 Функция pop.

Функция pop производит выборку элемента из стека. Выборка элемента из стека состоит в получении информационной части элемента (рисунок 8), переносе указателя на вершину стека на следующий элемент (рисунок 9) и освобождении памяти из под элемента (рисунок 10).

Рисунок 8. Получение информационной части элемента

Рисунок 9. Перенос указателя на вершину стека на следующий элемент

Рисунок 10. Освобождение памяти из под элемента

6 Описание пользовательского интерфейса

Данная программа вначале  обращается к пользователю для ввода данных в инфиксной форме (рисунок 11)

Рисунок 11. Ввод данных

После ввода данных в инфиксной форме программа сразу же выдает

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

Рисунок 12. Результат


7 Описание результата

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

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


8 Заключение

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

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


9 Список литературы

1. Павловская Т. А., Программирование на языке высокого уровня. Учебник для вузов, СПб.: Питер, 2004., 393 с.: ил.

        2. Лэнгсам И., Огенстайн М., Тененбаум А., Структуры данных для персональных ЭВМ, М.: Мир, 1989., 568 с.

3. Мизрохин С.В., TURBO PASCAL и объектно-ориентированное программирование, M.: Финансы и статистика, 1992., 192с.

4. А. Епанешников, В. Епанешников, Программирование в среде Turbo Pascal 7.0, М.: Диалог-МИФИ, 1995., 288 с.

5. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джефри, Д., Структуры данных и алгоритмы, М.: Издательский дом «Вильяме», 2003., 384 с.: ил.


Приложение А (обязательное)

Листинг программы

uses crt;

type

       pnode = ^node;

       node = record

        p : pnode;

        data : char;

       end;

var     top, temp : pnode;

       post, inf : string;

       symb, outdata: char;

       i : integer;

function push (top : pnode; data : char) : pnode;

var

       p : pnode;

begin

       new (p);

       p^.data := data;

       p^.p := top;

       push := p;

end;

function pop (top : pnode; var data : char) : pnode;

begin

       data := top^.data;

       pop := top^.p;

       dispose (top);

end;

function empty (top : pnode) : boolean;

begin

       if top = nil then empty := true

       else empty := false;

end;

function pred (oper1 : char; oper2 : char) : boolean;

begin

       pred := true;

       if (oper1 = '(') or (oper2 = '(') then pred := false;

       if oper2 = '^' then pred := false;

       if ((oper1 = '-') or (oper1 = '+'))

       and ((oper2 = '*') or (oper2 = '/')) then pred := false;

end;

begin

       clrscr;

       write ('Stroka v infiksnoi forme: '); readln (inf);

       inf := inf + ' ';

       post := '';

       top := nil;

       i := 1;

       repeat

               symb := inf[i];

               if (symb >= 'A') and (symb <= 'Z') then begin

                       post := post + symb;

                       inc (i);

               end

               else begin

                       while (empty (top) = false) and

                       (pred (top^.data, symb) = true) do begin

                               top := pop (top, outdata);

                               post := post + outdata;

                       end;

                       if (empty (top) = true) or (symb <> ')')

                       then top := push (top, symb)

                       else top := pop (top, outdata);

                       inc (i);

               end;

       until symb = ' ';

       while empty (top) = false do begin

               top := pop (top, outdata);

               post := post + outdata;

       end;

       writeln ('Stroka v postfiksnoi forme: ', post);

       readln;

end.


 

А также другие работы, которые могут Вас заинтересовать

39545. Анализ ассортимента и качества игрушек (на примере OAO «Детский Мир-Центр») 223.5 KB
  Можно сказать что игрушки появились одновременно с появлением человека. Надо было както занимать детей в первобытном племени – и их мамы давали им всякие камушки деревяшки необычной формы – это и были первые игрушки. Игрушки и игры на всех этапах развития общества отражали в своеобразной форме материальную и духовную жизнь людей. Поэтому игрушки должны служить средством познания мира ребенком воспитывать патриотизм любовь к труду рождать мечту развивать мысль.
39546. Проектируемое предприятие общественного питания в г. Саратове 7.93 MB
  Каждый человек в среднем ежегодно тратит на быструю еду более полутора тысяч рублей. рублей в год.4 Расчет и подбор механического оборудования Наиболее характерным механическим оборудованием используемым в цехе является мясорубка и овощерезка. Фактическую продолжительность работы tфакт определяем по формуле: tфакт=Q G Коэффициент использования ηфакт определяется по формуле: ηфакт=tф Т Подбор мясорубки.
39547. Анализ состояния малого предпринимательства в нижегодской области 776 KB
  Теоретические основы и развитие государственной поддержки малого предпринимательства. Роль малого предпринимательства в экономике. Понятие и сущность малого предпринимательства. Основы государственной поддержки малого предпринимательства.
39548. Расчет и проектирование Локальной Вычислительной Сети для организации «Подольский совет ветеранов» 1.83 MB
  В связи с техническим прогрессом, и необходимости минимизации бумажного документооборота, организациям как государственным так и коммерческим, необходим более функциональный и надежный вид ведения документации, и своевременность получения необходимой информации в короткие сроки для улучшения качества выполняемой работы и достижения максимального результата. Для этого в каждой организации используется Локальная вычислительная сеть.
39549. Динамика вариабельности сердечного ритма у одних и тех же студентов, занимающихся силовыми нагрузками в тренажерном зале на протяжении двух лет (до и после учебного занятия) 245.5 KB
  Ведь именно изменения параметров ритма сердца отражают адаптивные возможности регуляторных систем организма и динамику их развития. Состояние механизмов регуляции сегодня изучают с помощью математического анализа ритма сердца [21]. Математический анализ ритма сердца является достаточно информативным методом для изучения самых разнообразных стрессовых реакций организма [4].
39550. Методические основы проектирования интерьера учебного помещения на факультете технологии и предпринимательства 1.57 MB
  Влияние цвета света формы в интерьере на психику человека. При этом визуальная среда с которой человек соприкасается каждый день представляет собой такой же экологический фактор как и упомянутые выше и имеет не меньшую степень важности для человека. определение сущности интерьера и его элементов; анализ истории развития интерьера учебных помещений; определение основных требований к организации внутреннего пространства учебных помещений; рассмотрение освещения и предпочтительных цветовых гармоний интерьера в учебном помещении; определение...
39551. Разработка компактного неодимового лазера с диодной накачкой и волоконным выходом 17.44 MB
  В рабочем теле лазера путём накачки создаётся избыточное количество атомов в верхнем энергетическом состоянии. рис1 Вынужденное испускание фотона Классическая трёхуровневая система накачки рабочей среды используется например в рубиновом лазере. Именно это делает возможным использование немонохроматического излучения в качестве накачки. Следует отметить что создать инверсию населённостей атомов хрома Cr с помощью накачки непосредственно с уровня E0 на уровень E1 нельзя.
39552. ПУТИ СОВЕРШЕНСТВОВАНИЯ СИСТЕМЫ УПРАВЛЕНИЯ ФИНАНСАМИ МО Г. НОВОРОССИЙСК 1.91 MB
  Валовое производство молока составляло 554 тыс. тонн производство мяса в живом весе 148 тыс. Восемь сельскохозяйственных предприятий производят почти 36 тыс. тонн молока; 14 тыс.
39553. МАЗ предназначен для обеспечения подразделений головного предприятия автотранспортными средствами обес. 343.47 KB
  20 Площадь помещения м 2 88 Объем помещения м3 528 Средний разряд рабочих 2 Среднемесячная заработная плата рабочего с учетом премий руб. руб. руб.зд Км руб.