Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм перевода выражений в польскую запись




 

Алгоритм работает в соответствии со схемой, показанной на рис. 3.

 
 

 

 


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

Таблица 1

Значение приоритета p[s[i]]      
Операторы (символы s[i]) (,) +, – *, /

 

Пусть s[i] - анализируемый i-й символ входной строки, Store[top] - верхний элемент стека. Тогда алгоритм перевода выражений в польскую запись можно представить в виде следующей последовательности шагов.

Шаг 1. Если анализируемый символ s[i] входной строки является операндом, то он переписывается в выходную строку.

Шаг 2. Если s[i] является оператором, который имеет больший приоритет, чем оператор в вершине стека, т.е. p[s[i]]>p[Store[top]],
то символ s[i] записывается в стек. В противном случае, т.е. если
p[s[i]]£ p[Store[top]], то из стека сначала последовательно вы­бираются и помещаются в выходную строку операторы, имеющие прио­ритет больший или равный p[s[i]], а затем символ s[i] запи­сывается в стек.

Шаг 3. Если анализируемый символ s[i] = "(", то он помещается в стек, не выталкивая при этом ни одного оператора.

Шаг 4. Если s[i] = ")", то из стека выталкиваются и записывают­ся в выходную строку все операторы до первого встретившегося сим­вола "(". Символы "(" и ")" уничтожают друг друга и в выходную строку не включаются.

Шаг 5. Шаги 1-4 повторяются до тех пор, пока не будут просмотрены все символы входной строки. Затем оставшиеся в стеке операторы переносятся в выходную строку.

В качестве примера рассмотрим формирование польской записи для выражения (1). Процесс работа алгоритма представлен в табл. 2.

Таблица 2

Шаг алгоритма                    
Входная строка ( a - b ) * c + d  
  Состояние стека   ( #   ( # - ( # - ( #     #   * #   * #   + #   + #     #
Выходная строка   a   b   c * d +

 

Символ # выполняет роль вспомогательного оператора c нулевым приоритетом, который всегда находится в cтеке и необходим для корректного выполнения второго пункта алгоритма в том случае, когда стек пуст. Результатом является следующая строка польской записи: a bc * d +.

2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

2.1. Показать, что заданное арифметическое выражение яв­ляется синтаксически корректным. Для этого выполнить вывод выра­жения из начального символа описанной выше грамматики, как это показано на рис. 1, и построить синтаксическое дерево, подобное рис. 2.

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

2.3. Составить схему алгоритма перевода выражений в польскую запись.

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

2.5. Получить результаты машинного решения и сравнить их с результатами выполнения п. 2.2.

 




Поделиться с друзьями:


Дата добавления: 2015-06-28; Просмотров: 1088; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.