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

Алгоритм работает в соответствии со схемой, показанной на рис. 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 b – c * d +.

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

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

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

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

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

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

Дата добавления: 2015-06-28