Структура данных - синтаксический анализ выражений

Способ написания арифметического выражения известен как notation. Арифметическое выражение может быть записано в трех различных, но эквивалентных обозначениях, т. Е. Без изменения сути или вывода выражения. Эти обозначения -

Обозначение инфиксов
Префиксное (польское) обозначение
Постфиксная (обратнопольская) нотация

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

Обозначение инфиксов

Записываем выражение в infix обозначение, например a - b + c, где используются операторы in-между операндами. Нам, людям, легко читать, писать и говорить в инфиксной нотации, но это плохо сочетается с вычислительными устройствами. Алгоритм обработки инфиксной записи может быть трудным и дорогостоящим с точки зрения затрат времени и места.

Обозначение префикса

В этих обозначениях оператор prefixed в операнды, т.е. оператор записывается перед операндами. Например,+ab. Это эквивалентно его инфиксной записиa + b. Обозначение префикса также известно какPolish Notation.

Постфиксная нотация

Этот стиль обозначений известен как Reversed Polish Notation. В этом стиле записи операторpostfixed в операнды, т. е. оператор записывается после операндов. Например,ab+. Это эквивалентно его инфиксной записиa + b.

Следующая таблица вкратце пытается показать разницу во всех трех обозначениях -

Sr. No.	Обозначение инфиксов	Обозначение префикса	Постфиксная нотация
1	а + б	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	а * (Ь + с)	∗ a + bc	abc + ∗
4	а / б + в / г	+ / ab / cd	ab / cd / +
5	(а + б) * (с + г)	* + Ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - d	- ∗ + abcd	ab + c ∗ d -

Анализ выражений

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

Чтобы разобрать любое арифметическое выражение, нам также необходимо позаботиться о приоритете операторов и ассоциативности.

Приоритет

Когда операнд находится между двумя разными операторами, какой оператор примет операнд первым, определяется приоритетом оператора над другими. Например -

Поскольку операция умножения имеет приоритет перед сложением, сначала будет вычисляться b * c. Таблица приоритета операторов представлена позже.

Ассоциативность

Ассоциативность описывает правило, при котором в выражении появляются операторы с одинаковым приоритетом. Например, в выражении a + b - c оба символа + и - имеют одинаковый приоритет, тогда какая часть выражения будет вычислена первой, определяется ассоциативностью этих операторов. Здесь и +, и - остаются ассоциативными, поэтому выражение будет оцениваться как(a + b) − c.

Приоритет и ассоциативность определяют порядок оценки выражения. Ниже приведена таблица приоритетов и ассоциативности операторов (от высшей к низшей).

Sr. No.	Оператор	Приоритет	Ассоциативность
1	Возведение в степень ^	Наибольший	Правый ассоциативный
2	Умножение (*) и деление (/)	Второй по величине	Левая ассоциативная
3	Сложение (+) и вычитание (-)	Самый низкий	Левая ассоциативная

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

В a + b*c, часть выражения b*cбудет оцениваться первым, умножение будет иметь приоритет перед сложением. Здесь мы используем скобки дляa + b быть оцененным в первую очередь, например (a + b)*c.

Постфиксный алгоритм оценки

Теперь мы рассмотрим алгоритм того, как оценивать постфиксную нотацию -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

Чтобы увидеть реализацию на языке программирования C, щелкните здесь .