PreFix, InFix, PostFix и их вычисление

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

Infix

Это всем привычная нам форма записи математического выражения. Например:

a+b-c*d+(k-i)/n^2

это самое обычное InFixное выражение.

Ну что про него можно скзать? То, что вычисляется оно начиная с скобок. Сначала мы считаем выражения в скобках, а затем уже то, что вне. К томуже у нас главенствуют сначала степени, затем умножения и деления, и уже после этого мы вычисляем сложения и вычитания.
Название InFix такая запись получила из-за того, что знаки (Fix), которые обозначают действия с переменными содержатся внутри выражений, между переменными (In). Еслы мы пишем a*b, то мы имеем ввиду, что нужно взять число слева от *, и умножить его на число справа от *.
Ну в целом всё. Дальше будет чуть сложнее понять.

Prefix

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

Вот простой пример:

+ab

Обозначает, что мы возьмём действие »+» и применим его на переменные «a» и «b». Также можно записать и другие знаки. Например *cd или /kn.

Ну а как записывать более сложные случаи? Тут всё зависит от порядка следования знаков. Знаки набирают главенство слева направо.

Вот пример:

*+ab-cd

можно понимать так: Берём знак «*», ищем для него левый член: +ab, и правый член: -сd
+ab это a+b, а -cd это с-d.
Значит будет (a+b)*(c-d)

Вот ещё пример:

-*a+bc/de

Расшифруем:
Слева от - будет «*». Значит посмотрим, что нужно для «*». Слева от «*» стоит «a», а справа от «*» стоит »+». Для »+» слева стоит «b», а справа «c».
На данный момент получили a*(b+c) - Теперь глянем, что нужно справа от »-». Нужно »/». Слева для »/» стоит «d», а справа «e». Значит получим:

a*(b+c) - d/e

Postfix

Это полный аналог для PreFix, но знаки действий ставятся наоборот, после операндов, с которыми действовать. Пример:

ab-cd+^ (знак "^" - возведение в степень)

Читаем так: берём «а» и «b». Ставим между ними знак »-». Берём «с» и «d», ставим между ними знак »+». Берём (a-b) и (c-d), ставим между ними знак «^». Получаем »(a-b)^(c+d)».

Вот ещё пример (без объяснения. Попробуйте понять сами):
Infix:

c*(a+B)*(d-f/e)

PostFix:

caB+*dfe/-*

Для InFix'ной и PostFix'ной записей характерно то, что не нужно в выражениях писать скобки. Так как главенство одних частей выражения над другими зависит от их расположения в строке.

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

В процессе перевода используется бинарное дерево. Такое дерево организуется при помощи двухсвязных списков.
Вот пример построения бинарного дерева:

        *
       / \
     /     \
    -       :
   / \     / \
  a   +   e   -
     / \     / \
    c   d   f   g

Тут зашифровано выражение:

(a-(c+d))*(e/(f-g))

Описание модуля

Модуль позволяет создавать такие деревья из строки с выражением в формате InFix, PostFix или PreFix, а так же позволяет из бинарного дерева делать наоборот строки с выражениями в любом из этих трёх форматов.

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

(a-(c+d))*(e/(f-g))

и мы зададим числовые значения для переменных a, b, c, d, e, f и g, то эта функция подставит эти значения, и вычислит значение выражения.

На базе этого модуля можно написать программу - калькулятор, способную анализировать математические выражения.
При преобразовании в InFix'ный формат, или из InFix'ного формата модуль учитывает (и добавляет, где нужно) все скобки.

Скачать fixexpr.rar

 
pascal/prefix_infix_postfix.txt · Последние изменения: 2006/05/29 14:21 (внешнее изменение)
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki