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

Способ написания арифметического выражения известен как 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, щелкните здесь .