Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=42056&view=findpost&p=274609 Sat, 03 Jan 2004 14:03:46 +0000 PreFix, InFix, PostFix и их вычисление https://forum.sources.ru/index.php?showtopic=42056&view=findpost&p=274609 Математики даже свои записи записать одним способом не могут. Подавай им всякие Fixы.

Для записи любого математического выражения существует три формы. Друг от друга они отличаются порядком записи переменных и знаков между ними
Рассмотрим их одно за другим.
Сначала 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'ного формата юнит учитывает (и добавляет, где нужно) все скобки.


Текст юнита и программы, демонстрирующей основные возможности юнита, и наглядно показывающей, как им пользоваться:]]> Some1 Pascal: Математика