|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : Andrei Protasovitski 2:5020/400 17 Apr 2004 12:39:30
To : Sergey Ermakov
Subject : Re: Парсинг "формулы"
--------------------------------------------------------------------------------
Доброго здоровья!
Sergey Ermakov wrote:
> SE>> (a + b) * (c + d)
> SE>> Требуется получить:
> SE>> a * c + a * d + b * c + b * d
> SE>> В общем случае может быть и такое:
> SE>> a + b * (c + d) + (e + f) * g + h
> BZ> я бы лично сам написал. работы где-то на полдня. сначала строим
> BZ> синтаксическое дерево, а затем обходим его
> Что такое "синтаксическое дерево"?.. Я так понимаю, членим формулу, заводя на
> "ветви" скобки?..
Hет. Берем пример (a+b)*(c+d)+(e+f)*h и строим дерево так:
+
/ \
* ----*
/ \ |\
+ + + h
/| / \ / \
a b c d e f
Т.е. в узлах операции, в листьях переменные.
Hо как мне кажется, это чересчур громоздко для твоей задачи. Если тебе
надо только раскрыть скобки и привести подобные (т.е. a*b + b*a = 2*a*b)
в выражении, содержащем только операции умножения и сложения (помним,
что вычитание есть сложение с числом умноженным на -1), то я бы строил
дерево несколько проще: в узлах было бы только умножение. Тогда алгоритм
рекурсивной функции для парсинга выражения с любой вложенностью скобок
упрощенно выглядел бы так:
my sub removalOfBrackets {
1. Обрабатываем входное выражение: убираем все пробелы, проверяем
корректность формулы (чтобы исключить неправильную расстановку скобок и
т.п.) и полагаем, что это есть сумма нескольких слагаемых. Выражения
типа (a+b*(c+d)+e)*(f+h) считаем выражением, содержащим одно слагаемое.
my $result = '';
2. Поочередно выделяем каждое слагаемое (скажем, в массив @item). Этот
шаг один из самых сложных.
3. Если слагаемых больше одного, то для каждого из них вызываем
removalOfBrackets:
$result=join("+",removalOfBrackets($item[0]),removalOfBrackets($item[1]),...remo
valOfBrackets($item[$#item]));
return $result;
Конец процедуры.
4. Если слагаемое одно, разбиваем его на множители (@multiplier). Тоже
не самое простое.
5. Если множитель один, возвращаем его:
$result=multiplier[0];
return $result;
Конец процедуры.
6. Поочередно перемножаем множители, начиная с конца, примерно так:
$multiplier[$#multiplier-1]=multiplication(removalOfBrackets($multiplier[$#multi
plier]),removalOfBrackets($multiplier[$#multiplier]));
$multiplier[$#multiplier] = undef;
где multiplication выполняет умножение многочлена на многочлен, приводит
подобные. Поскольку removalOfBrackets возвращает сумму, в multiplication
не будет вызова removalOfBrackets. Думаю, написать multiplication не
составит особого труда. Можно сделать multiplication для перемножения
нескольких многочленов.
7. Возвращаем результат умножения:
$result=$multiplier[0];
return $result;
Конец процедуры.
}
Для выделения множителей и слагаемых можно написать отдельную процедуру,
которая выделяет элементы в зависимости от знака операции.
Итак, для парсинга выражения надо четыре процедуры:
isCorrectExpr - проверка корректности выражения;
multiplication - перемножение многочленов;
separation - отделение слагаемых, множителей;
removalOfBrackets - основная процедура раскрытия скобок.
Можно, также, придумать процедуры для приведения одночленов и
многочленов к каноническому виду, чтобы упростить приведение подобных.
Для multiplication можно предусмотреть только приведение подобных для
одного аргумента.
А вообще, лучше об этом спрашивать в RU.ALGORITHMS: там точно знают и,
возможно, предложат готовое решение на Perl'е.
З.Ы. Дайте знать, если в предложенной схеме есть неточности.
--
Andrei Protasovitski mailto:andrei()siliconmaterials.com
JS "KamSil" http://www.siliconmaterials.com/
137, Brestskaya str., ICQ: 75725244
225710, Pinsk, Belarus
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5.3
* Origin: JS KamSil (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
