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

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

  • Инфиксная нотация
  • Префикс (польский)
  • Postfix (обратная польская) нотация

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

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

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

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

В этой записи оператор перед префиксом операнда, т. Е. Оператор записывается перед операндами. Например, + ab . Это эквивалентно его инфиксной записи a + b . Префиксная нотация также известна как польская нотация .

Постфиксная запись

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

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

Sr.No. Инфиксная нотация Префиксная нотация Постфиксная запись
1 а + б + ab ab +
2 (a + b) ∗ c ∗ + abc ab + c ∗
3 a ∗ (b + c) ∗ a + bc abc + ∗
4 а / б + с / д + / ab / cd ab / cd / +
5 (a + b) ∗ (c + d) ∗ + 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, пожалуйста, нажмите здесь .