Способ написания арифметического выражения известен как нотация . Арифметическое выражение может быть записано в трех разных, но эквивалентных обозначениях, т. Е. Без изменения сущности или вывода выражения. Эти обозначения —
- Инфиксная нотация
- Префикс (польский)
- Postfix (обратная польская) нотация
Эти обозначения называются как они используют оператор в выражении. Мы узнаем то же самое здесь, в этой главе.
Инфиксная нотация
Мы пишем выражение в инфиксной нотации, например, a — b + c, где операторы используются в- между операндами. Нам, людям, легко читать, писать и говорить в инфиксной записи, но то же самое не подходит для вычислительных устройств. Алгоритм обработки инфиксной записи может быть сложным и дорогостоящим с точки зрения затрат времени и пространства.
Префиксная нотация
В этой записи оператор перед префиксом операнда, т. Е. Оператор записывается перед операндами. Например, + ab . Это эквивалентно его инфиксной записи a + b . Префиксная нотация также известна как польская нотация .
Постфиксная запись
Этот стиль обозначения известен как обратная польская запись. В этом стиле обозначений оператор добавляется после операнда, т. Е. Оператор записывается после операнда. Например, ab & plus; , Это эквивалентно его инфиксной записи 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, пожалуйста, нажмите здесь .