VPF::Синтаксический разбор и упрощение полинома

neutrino

Дата 5.5.2009, 16:40 (ссылка)

(нет голосов)

Загрузка ...

Gothic soul

Профиль
Группа: Модератор
Сообщений: 3041
Регистрация: 25.3.2002
Где: Верхняя Галилея, Кармиэль

Репутация: нет
Всего: 62

Приветствую!

Требуется написать программу, которая будет получать выражение с одними только иксами. Возможные операции: суммирование, умножение и вычитание. Требуется найти коэффициенты полинома тождевственного этому выражению. Например:
ввод: ((((x + x) + (x * x)) - ((x * x) * x)) * x)
вывод: -1 1 2 0 0

так как ((((x + x) + (x * x)) - ((x * x) * x)) * x) = -x^4 + x^3 + 2x^2

Какой алгоритм решает эту задачу?

--------------------

The truth comes from within ...

Покойся с миром, Vit

dereyly

Дата 5.5.2009, 20:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 217
Регистрация: 16.6.2006

Репутация: 1
Всего: 4

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

maxdiver

Дата 5.5.2009, 21:46 (ссылка)

(голосов:2)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

Я делал так.
Полином:

Код

typedef map<int,int> polynom;

где polynom[i] - это коэффициент при x^i.
Тогда операция сложения выглядит так:

Код

polynom operator+ (polynom a, polynom b) {
   polynom res;
   for (polynom::iterator i=a.begin(); i!=a.end(); ++i)
      res[i->first] += i->second;
   for (polynom::iterator i=b.begin(); i!=b.end(); ++i)
      res[i->first] += i->second;
   return res;
}

Ну и минус по аналогии, с умножением примерно так же, как бы столбиком перемножаем.

Всё, теперь у нас всё готово, и теперь надо просто распарсить и посчитать значение выражения. Обратная польская нотация (парсер со стеком) сделает это на ура, строчек в 20. Иксы в выражении мы рассматриваем как polynom, у которого [0]=1.

Void

Дата 5.5.2009, 22:44 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 3
Всего: 173

Цитата(dereyly @ 5.5.2009, 22:53

)

Можно много проще.
n -> n * x ^ 0
x -> 1 * x ^ 1
И выполняем операции в соответствии с правилами действий над многочленами.
Вот, накидал на Хаскеле без парсера:

Код


module Poly (Coeff, Exponent, Polynomial, makePoly) where

import Data.List (intersperse)
import Data.IntMap hiding (map, null, filter)
import qualified Data.IntMap as IntMap

type Coeff = Integer
type Exponent = Int

newtype Polynomial = Poly (IntMap Coeff)

-- По-хорошему здесь кольцо нужно, в Num много лишнего, в частности, 
-- зависимости от Eq и Ord, но для краткости изобретать свою иерархию не будем.
instance Num Polynomial where
    (+) (Poly x) (Poly y) = Poly $ unionWith (+) x y
    (*) (Poly x) (Poly y) =
        sum [Poly $ fromList $ [mult px py] | px <- assocs x, py <- assocs y]
            where mult (ex, px) (ey, py) = (ex + ey, px * py)
    negate (Poly x) = Poly $ IntMap.map negate x
    abs = undefined
    signum = undefined
    fromInteger n = Poly $ singleton 0 n

instance Eq Polynomial where
    (Poly x) == (Poly y) = x == y

instance Ord Polynomial where
    compare = undefined

instance Show Polynomial where
    show (Poly x) =
        if null items then "0"
        else concat $ intersperse " + " items
            where items = filter (not . null) $ map mono $ reverse $ assocs x
                    where mono (_, 0) = ""
                          mono (1, 1) = "x"
                          mono (1,-1) = "-x"
                          mono (0, p) = show p
                          mono (e, 1) = "x^" ++ show e
                          mono (e,-1) = "-x^" ++ show e
                          mono (1, p) = show p ++ "*x"
                          mono (e, p) = show p ++ "*x^" ++ show e

makePoly :: [(Exponent, Coeff)] -> Polynomial
makePoly s = sum $ map (Poly . uncurry singleton) s

Код


module Main where

import Poly

data Expr =
      X
    | Const Integer
    | Add Expr Expr
    | Sub Expr Expr
    | Mul Expr Expr

eval :: Expr -> Polynomial
eval X = makePoly [(1, 1)]
eval (Const x) = makePoly [(0, x)]
eval (Add x y) = eval x + eval y
eval (Sub x y) = eval x - eval y
eval (Mul x y) = eval x * eval y

-- ((((x + x) + (x * x)) - ((x * x) * x)) * x) = -x^4 + x^3 + 2x^2
test = (Mul (Sub (Add (Add X X) (Mul X X)) (Mul (Mul X X) X)) X)

main = print $ eval test

Добавлено через 1 минуту и 18 секунд
Пока писал, уже ответили smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »