Цитата(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 секунд
Пока писал, уже ответили  |