Работа с формулами.

Введение.

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

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

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

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

Если кто-то знает алгоритмы решения описанных выше задач, и хочет поделиться ими, присылайте буду весьма признателен.

Далее я буду предполагать, что язык на котором Вы собираетесь реализовывать приведенные здесь алгоритмы, позволяет работать со строками символов, а так же имеет стандартные средства для перевода строки цифр в число (для обозначения таких функций я буду использовать названия StrToInt, StrToFloat, для перевода в целое или вещественное число соответственно). Если возникнут проблемы, напишите я выложу алгоритм, осуществляющий такое преобразование. Наверх

Преобразование выражения в польскую запись.(4 операции)

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

Исходная формула Польская запись

a+b a b +

a+b*c a b c * +

(a+b)*c a b +c *

d*(a+b)*c d a b + * c *

Алгоритм прислал мне Владимир Кошелев, за что ему большое спасибо, насколько я понимаю, алгоритм обсуждался в конференции RU.ALGORITHMS. Поскольку я не силен в ФИДО (к глубокому своему сожалению), более подробно указать ничего не могу.

Данный алгоритм преобразует формулу помещенную в массив символов Eq длины n, при этом предполагается, что: 1. имена переменных начинаются с символов английского алфавита и содержат только символы и цифры, длина имени переменной произвольна. 2. в формуле используются только 4 арифметические операции: +, -, *, / 3. в формуле допустимо использование скобок вида '(',')'. В случае если алгоритм не может обработать формулу, то в качестве результата выдается "ERROR".

Алгоритм дополнительно использует две функции: 1. function Sym(a:Char):byte; - выдает 0, если аргумент цифра; 1 если аргумент символ английского алфавита; и 2 во всех остальных случаях. 2. function Prior(a:Char):byte; - выдает 0, если аргумент '('; 1 если аргумент ')', '+' или '-'; 2 если аргумент '*' или '/'; и 255 во всех остальных случаях. Так же в алгоритме используется стек, который реализован при помощи массива Stack, а номер элемента на вершине стека задается переменной Top.

Работа алгоритма достаточно тривиальна мы проходим по массиву Eq выделяя пять возможных ситуаций: 1. Символ английского алфавита, значит мы имеем переменную - считываем ее имя и помещаем в результирующую строку. 2. Цифра, значит мы имеем число - считываем его полностью и помещаем в результирующую строку. 3. Открывающаяся скобка '(' - помещаем ее на стек. 4. Закрывающаяся скобка ')' - переносим операции со стека в результирующую строку до момента пока не сняли со стека '(', открывающуюся скобку в результат не помещаем. Если открывающаяся скобка так и не встретилась, значит в исходном выражение неправильно расставлены скобки помещаем в результат "ERROR" и выходим из алгоритма. 5. Операция '+','-','*','/' - переносим в результат операции с вершины стека до тех пор пока стек не пуст и приоритет текущей операции меньше либо равен приритету операции находящейся на вершине стеке. Затем помещаем текущую операцию на стек. После окончания прохода по исходному массиву, переносим операции оставшиеся на стеке в результат. Если на стеке осталась открывающаяся скобка, значит в обрабатываемом выражении содержится ошибка, а следовательно помещаем в результат "ERROR".

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

Расширение алгоритма возможно введением обработки дополнительных функций (например синус, косинус ...). Реализация не слишком сложна, но усложняет понимание алгоритма, поэтому алгоритм обрабатывающий кроме арифметических операций также и функции представлен отдельно. Наверх

Преобразование выражения в польскую запись.

Алгоритм является усовершенствованым вариантом предыдущего, отличие заключается в возможности кроме четырех операций (+,-,*,/) обрабатывать дополнительно элементарные функции (я ввел только функции от одной переменной, так как мне сейчас интересен именно этот случай, если кто-то заинтересуется, то без особых затруднений переделает алгоритм на вариант функций многих переменных)

Чтобы определить эту возможность дополнительно введем две функции: 1. function FNToCh(FuncName:string):Char; - функция сопоставляет имени функции некоторый символ. Символы можно выберать произвольно, единственно нельзя использовать: +,-,*,/,^,?, первые пять зарезервированы дл операций сложения, вычетания, умножения, деления и возведения в степень, а последний символ функция выдает в случае когда входному параметру не соответствует ни одна из функций. 2. function ChToFN(a:Char):string; - функция обратная предыдущей.

Для примера я составил табличку определяющую работу функции FNToCh, Вы можете расширить ее введением имен дополнительных функций

FuncName FNToCh(FuncName)

+ +

- -

* *

/ /

^ ^

sin A

cos B

tg C

ctg D

arcsin E

arccos F

ln G

log H

exp I

sqr J

Так же раширена функция Prior, использовавшаяся в предыдущем алгоритме, все символы отвечающие за вновь введенные функции имеют приритет 3. Наверх

Вычисление выражения представленного в польской записи (4 операции).

Алгоритм позволяет вычислить значение выражения представленного в польской записе, при известных значениях входящих в него переменных.

В начале определим, что мы имеем в виду под польской записью, польская запись - постфиксная форма выражения. Четкого определения я нигде не нашел, формулировать самому мне немного лень, но принцип лежащий в основе понятен из примеров:

Исходная формула Польская запись

a+b a b +

a+b*c a b c * +

(a+b)*c a b +c *

123*(a+b)*c 123 a b + * c *

Я предполагаю, что элементы (переменные, числа, символы операций) в записе разделены пробелом. Так оно и есть если для перевода в польскую запись использовался предыдущий алгоритм.

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

В алгоритме используются две функции: 1. function Sym(a:Char):byte; - выдает 0, если аргумент цифра; 1 если аргумент символ английского алфавита; и 2 во всех остальных случаях. 2. function Value(a:string):real; - определяет по имени переменной ее числовое значение.

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

Преобразование выражения из польской записи в стандартную форму.

Алгоритм позволяет преобразовать выражение из польской записи в привычную нам форму. Работа алгоритма практически полностью повторяет работу "вычислителя" для польской записи, поэтому вначале рекомендую прочитать его описание, а затем вернуться сюда. Теперь отличия, во-первых элементы стека теперь не вещественные числа, а строки, во-вторых если раньше мы встретив операцию снимали со стека два числа, выполняли операцию и результат помещали на стек, то теперь мы не выполняем операцию, а создаем строку отражающую действие операции в нормальной форме. Т.е. допустим в исходной строке мы встретили знак '+', мы снимаем со стека два элемента (например 'FirstVar' и 'SecondVar') и помещаем на стек строку 'FirstVar+SecondVar'. Надеюсь все понятно, если не до конца, то посмотрите блок-схему.

Еще одно отличие от "вычислителя" заключается в том, что в данном случае мы допускаем наличие в выражении функций (одной переменной), в случае если мы встречаем имя функции, то действия практически те же, что и для операции, единственно со стека снимается один параметр. В алгоритме используется функция FNToCh описание которой дано в алгоритме преобразования выражения в польскую запись.

И напоследок: в алгоритме используется стек pSt который хранит приоритет операции соответствующий строки со стека Stack (т.е. если например Stack[1]:='23',Stack[2]:='100+x', то pSt[1]:=3, pSt[2]:=2) это необходимо чтобы правильно расставить скобки в выражениях. Наверх