Не знаю, как надо решать такую вот задачу.

Есть дерево, которое представляет из себя <Expression>. <Expression> состоит из набора <Value> и <Expression> в произвольном порядке (но должно быть как минимум два дочерних элемента). <Value> — примитивное значение. <Expression> имеет признак {Operation}. Результатом применения {Operation} над <Expression> является, по сути, <Value>. Требуется вычислить <Value> для некоего <Expression>.

Пример

[+         // Начало <Expression> с {Operation} '+' 
  1,       // Вот это и есть <Value>
  [*
    2, 
    3, 
    [+
      4,
      5,
    ],
    6,
  ],
  7,
]

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

У меня получился такой способ:
Имеется стек, элементом которого может быть либо <Value>, либо <Null>.
Идём по элементам:

• Если <Value>, вставляем его в стек.
  
• Если <Expression>, вставляем в стек <Null> и начинаем обход дочерних элементов этого <Expression>.
  
• По достижении конца <Expression>, поднимаемся по стеку до ближайшего <Null>, вычисляя новое <Value>, соответствующее данному <Expression>. Вычислив, убираем из стека <Null>, поставленный для данного <Expression>, и вставляем вычисленный <Value>. Переходим к следующему элементу.

То есть, применительно к примеру:

1. Push <Null> // Корневое <Expression> с операцией '+'
   
2. Push '1'
   
3. Push <Null> // <Expression> с операцией '*'
   
4. Push '2'
   
5. Push '3'
   
6. Push <Null> // <Expression> с операцией '+'
   
7. Push '4'
   
8. Push '5'
   
9. Pop '5' // <Value> в последнем <Expression> закончились, вычисляем его…
   
10. Pop '4'
    
11. Pop <Null> // Заменяем маркер <Null> на значение <Expression>
    
12. Push '9' (4 + 5)
    
13. Push '6'
    
14. Pop '6'
    
15. Pop '9'
    
16. Pop '3'
    
17. Pop '4'
    
18. Pop <Null>
    
19. Push '324' (2 * 3 * 9 * 6)
    
20. Push '7'
    
21. Pop '7'
    
22. Pop '324'
    
23. Pop '1'
    
24. Pop <Null>
    
25. Push '332' (1 + 324 + 7)

В итоге в стеке только один элемент с результатом.

Насколько это нормальный "по науке" способ? Как надо по-правильному? Есть ли более "быстрые" или более "экономные" подходы?

У меня способ вызывает подозрение тем, что

1. необходимо знать, что "<Expression> начался" и "<Expression> закончился". Обход сделан через Visitor и его интерфейс получается не классический:
   

   interface IVisitor
   {
     void VisitValue(Value value);
     void VisitExpression(Expression expression);
   }

   
   а специфический:
   

   interface IVisitor
   {
     void VisitValue(Value value);
   
     void VisitBeginExpression(Expression expression);
     void VisitEndExpression(Expression expression);
   }

   
   что, конечно, ни суть, ни механизм паттерна не меняет, но именно что "вызывает подозрение"
   
2. приходится использовать специальные значения (<Null>) в стеке.

Можно ли (алгоритмически) избавиться от указанных недостатков?

Здравствуйте, _FRED_, Вы писали:

_FR>Не знаю, как надо решать такую вот задачу.

_FR>Есть дерево, которое представляет из себя <Expression>. <Expression> состоит из набора <Value> и <Expression> в произвольном порядке (но должно быть как минимум два дочерних элемента). <Value> — примитивное значение. <Expression> имеет признак {Operation}. Результатом применения {Operation} над <Expression> является, по сути, <Value>. Требуется вычислить <Value> для некоего <Expression>.


_FR>Можно ли (алгоритмически) избавиться от указанных недостатков?

Я бы отдельно описал грамматику, а отдельно — эвалютор:

-- алгебраическая структура:
-- Выражение - это либо значение типа Int, либо сумма списка Выражений, либо произведение списка Выражений
data Expr = Value Int | Add [Expr] | Mult [Expr]

-- ну и теперь эвалютор тривиально реализуется паттерн матчингом
eval :: Expr -> Int
eval (Value n) = n
eval (Add es)  = foldr (+) 0 $ map eval es
eval (Mult es) = foldr (*) 1 $ map eval es

(haskell)

Здравствуйте, deniok, Вы писали:

D>Я бы отдельно описал грамматику, а отдельно — эвалютор:
D>[haskell]

Так вот "в чём сила, брат" Но нету, к сожелению, у меня такого средства для решения, как паттерн-матчинг

D>eval (Add es)  = foldr (+) 0 $ map eval es
D>eval (Mult es) = foldr (*) 1 $ map eval es

А если операция xor, то каковым должно быть начальное значение, которое '0' для сложения и '1' для умножения?

Здравствуйте, _FRED_, Вы писали:

_FR>А если операция xor, то каковым должно быть начальное значение, которое '0' для сложения и '1' для умножения?

Для этих целей есть foldr1:

data Expr = Value Int | Add [Expr] | Mult [Expr] | Xor [Expr]

eval (Value n) = n
eval (Add es)  = foldr (+) 0 $ map eval es
eval (Mult es) = foldr (*) 1 $ map eval es
eval (Xor es)  = foldr1 xor  $ map eval es

И вообще foldr здесь для демонстрации единообразия. Более компактно было бы использовать

eval (Add es)  = sum     $ map eval es
eval (Mult es) = product $ map eval es

Здравствуйте, deniok, Вы писали:

D>И вообще foldr здесь для демонстрации единообразия. Более компактно было бы использовать

D>eval (Add es)  = sum     $ map eval es
D>eval (Mult es) = product $ map eval es

D>

А sum, product, map — это методы, уже реализованные в стандартной библиотеке\компиляторе?

Здравствуйте, _FRED_, Вы писали:

_FR>А sum, product, map — это методы, уже реализованные в стандартной библиотеке\компиляторе?

Да, из стандартной библиотеки Prelude. Как и foldr, foldr1. Но идеальный вариант, который бы фэйлился на пустых списках

eval (Value n) = n
eval (Add es)  = foldr1 (+) $ map eval es
eval (Mult es) = foldr1 (*) $ map eval es
eval (Xor es)  = foldr1 xor $ map eval es

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

Здравствуйте, deniok, Вы писали:

Ну и вынося избыточное дублирование в отдельную evalOper :: (Int -> Int -> Int) -> [Expr] -> Int, получим

eval (Value n) = n
eval (Add es)  = evalOper (+) es
eval (Mult es) = evalOper (*) es
eval (Xor es)  = evalOper xor es

evalOper op = foldr1 op . map eval

Здравствуйте, deniok, Вы писали:

D>В реальности, конечно, для более сложных грамматик и/или вменяемой обработки неправильного ввода стоит парсерами пользоваться.

Данные у меня описаны в xml и всё, что нужно (например, наличие как минимум двух дочерних элементов у узла) проверяется схемой. Так что парсер с проверками есть. Стоит задача построить дерево объектов, соответствующее описанию.

Сложность в том, что для создания объекта-узла необходимо уже иметь созданными все дочернии объекты-узлы. То есть нельзя, например, добавить в узел сначала "пустой" дочерний узел, а потом, по мере прочтения, заполнять этот "пустой" дочерний узел данными. Это я и назвал "обойти от детей к родителям".

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, deniok, Вы писали:

D>>В реальности, конечно, для более сложных грамматик и/или вменяемой обработки неправильного ввода стоит парсерами пользоваться.

_FR>Данные у меня описаны в xml и всё, что нужно (например, наличие как минимум двух дочерних элементов у узла) проверяется схемой. Так что парсер с проверками есть. Стоит задача построить дерево объектов, соответствующее описанию.

_FR>Сложность в том, что для создания объекта-узла необходимо уже иметь созданными все дочернии объекты-узлы. То есть нельзя, например, добавить в узел сначала "пустой" дочерний узел, а потом, по мере прочтения, заполнять этот "пустой" дочерний узел данными. Это я и назвал "обойти от детей к родителям".

Ну, в ленивом и декларативном Хаскелле всё просто. Достаточно добавить указание генерить автоматические производные инстансы класса типов Read (аналог десереализации):

data Expr = Value Int | Add [Expr] | Mult [Expr] | Xor [Expr] deriving Read

и строковой поток ввода разбирается однозначно:

*Main> eval $ read "Add [Value 1, Value 2, Mult [Value 3, Value 4], Value 5]"
20

Если хочется использовать вместо конструкторов данных Add, Mult, Value другие символы, то ручками пишется тривиальный пользовательский instance Read

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, deniok, Вы писали:

D>>Я бы отдельно описал грамматику, а отдельно — эвалютор:
D>>[haskell]

_FR>Так вот "в чём сила, брат" Но нету, к сожелению, у меня такого средства для решения, как паттерн-матчинг

Когда нет паттерн-матчинга, обходятся виртуальной функцией.

/*interface*/ class Node
{
public:
    virtual int evaluate() const = 0;
};

class Value : public Node
{
private:
    int value_;
public:
    /*override*/ int evaluate() const { return value_; }
};

/*abstract*/ class Expression : public Node
{
private:
    typedef std::vector<boost::shared_ptr<Node> > Operands;
    Operands operands_;
    virtual int op(int x, int y) const = 0;
public:
    /*override*/ int evaluate() const
    {
        assert(!operands_.empty());
        int result = *operands_[0];
        for (Operands::const_iterator i = operands_.begin() + 1, e = operands_.end(); i != e; ++i)
        {
            result = op(result, **i);
        }
        return result;
    }
};

class Add : public Expression
{
private:
    /*override*/ int op(int x, int y) const { return x + y; }
};

class Mul : public Expression
{
private:
    /*override*/ int op(int x, int y) const { return x * y; }
};

Здравствуйте, _FRED_, Вы писали:

_FR>А если операция xor, то каковым должно быть начальное значение, которое '0' для сложения и '1' для умножения?

Поскольку xor есть, в сущности, сложение по модулю 2, то и нейтральный элемент для него — 0. Это верно как для логического, так и для побитового xor.

Аналогично, or ведёт себя как +, а and — как *. Если and побитовый, то в качестве нейтрального элемента нужно брать побитовую единицу — привет Basic’у, где истина имела значение -1.

Здравствуйте, Centaur, Вы писали:

C>/*abstract*/ class Expression : public Node
C>{
C>private:
C>    typedef std::vector<boost::shared_ptr<Node> > Operands;
C>    Operands operands_;
C>    virtual int op(int x, int y) const = 0;
C>public:
C>    /*override*/ int evaluate() const
C>    {
        // ...
C>    }
C>};

А как будет заполняться вектор "operands_"? Мой вопрос заключается в том, что все значения для "operands_" надо передать в конструктор класса Expression и больше не менять, то есть перед созданием каждого объекта-узла необходимо предварительно обойти всех его детей.

Здравствуйте, deniok, Вы писали:

_FR>>А если операция xor, то каковым должно быть начальное значение, которое '0' для сложения и '1' для умножения?

D>Для этих целей есть foldr1:

А для xor, как и для or, и для +, нейтральным элементом является нуль (ну или False).

Здравствуйте, _FRED_, Вы писали:

_FR>Данные у меня описаны в xml и всё, что нужно (например, наличие как минимум двух дочерних элементов у узла) проверяется схемой. Так что парсер с проверками есть. Стоит задача построить дерево объектов, соответствующее описанию.

_FR>Сложность в том, что для создания объекта-узла необходимо уже иметь созданными все дочернии объекты-узлы. То есть нельзя, например, добавить в узел сначала "пустой" дочерний узел, а потом, по мере прочтения, заполнять этот "пустой" дочерний узел данными. Это я и назвал "обойти от детей к родителям".

То есть, ты хочешь на SAX-парсере сделать fold дерева.
Вот смотри, как выглядит ситуация в каждый момент времени

root
  |
  +- node1
  |    |
  |    +- node11 <- этот узел будет редуцирован чуть позже
  |    |    +- REDUCED <- эти узлы были полностью прочитаны и тут же редуцированы
  |    |    +- REDUCED
  |    |    |
  |    |    +- node11n <- этот узел только что прочитан и сейчас мы его редуцируем
  |    |    |
 ...  ...  ... <- а это мы ещё не прочитали из строки

То есть, как ты совершенно справедливо заметил, частично редуцированное дерево — это пара из стека (прочитанных и частично редуцированных элементов) и очереди (непрочитанных лексем).

Вот, а что касается ООП-специфичных приёмов (паттерн Посетитель и т.п.), тут нужно смотреть, насколько ты хочешь всё обобщать. Можно отделаться полиморфизмом на уровне виртуальных методов у каждого узла стека, а не рожать мультиметоды Посетителя.

Кстати, а почему бы тебе не взять DOM-парсер? Жизненная необходимость, принципы или экономия на спичках не позволяют?

Здравствуйте, Кодт, Вы писали:

К>это пара из стека (прочитанных и частично редуцированных элементов) и очереди (непрочитанных лексем).

То есть, если я правильно понял, ничего лучшего придумывать и не надо?

К>Кстати, а почему бы тебе не взять DOM-парсер? Жизненная необходимость, принципы или экономия на спичках не позволяют?

Ситуация такая: есть некое дерево, которое может быть и DOM-Document-ом, и AST, и набором окон приложения (MDIParent->Childs[]->Controls[]), то есть всё, что угодно. Над элементом этого дерева можно совершать такие примитивные операции, как получение следующего\предыдущего элемента (next-,previous- sibling) и первого\последнего дочернего элемента (first-, last- child). В общем виде входные данные можно описать так:

interface INode
{
  INode Parent { get; }

  INode NextSibling { get; }
  INode PreviousSibling { get; }

  INode FirstChild { get; }
  INode LastChild { get; }
}

Так же, есть некая система immutable-типов, с помощью которой можно описать любое дерево. В упрощённом виде такая:

class Leaf // Простой элемент, не имеющий дочерних.
{
}

class Node // Составной элемент
{
  public Node(Node[] nodes, Leaf[] leaves) { 
    Nodes = new ReadOnlyCollection<Node>(nodes);
    Leaves = new ReadOnlyCollection<Leaf>(leaves); 
  }

  public ReadOnlyCollection<Node> Nodes { get; private set; }
  public ReadOnlyCollection<Leaf> Leaves { get; private set; }
}

То есть для создания объекта-узла уже надо иметь созданными всех его детей. Делать эту систему не-immutable я не хочу, но внести какие-то изменения в неё, при необходимости, могу.

Требуется создать "модель" произвольного дерева (INode) в терминах Node.

Способ реализации — виртуальный метод\посититель не так принципиален, конечно же. Интересно, как нужно обойти INode, что бы оптимально решить задачу.

Здравствуйте, _FRED_, Вы писали:

К>>Кстати, а почему бы тебе не взять DOM-парсер? Жизненная необходимость, принципы или экономия на спичках не позволяют?

_FR>Ситуация такая: есть некое дерево, которое может быть и DOM-Document-ом, и AST, и набором окон приложения (MDIParent->Childs[]->Controls[]), то есть всё, что угодно.

"Есть дерево" означает, что оно уже развёрнуто где-то в памяти?

_FR> Над элементом этого дерева можно совершать такие примитивные операции, как получение следующего\предыдущего элемента (next-,previous- sibling) и первого\последнего дочернего элемента (first-, last- child).

_FR>Требуется создать "модель" произвольного дерева (INode) в терминах Node.

Ага, вот что тебе захотелось.

_FR>Способ реализации — виртуальный метод\посититель не так принципиален, конечно же. Интересно, как нужно обойти INode, что бы оптимально решить задачу.

Казалось бы, всё просто. Делается рекурсивный обход исходного дерева. Это даже не fold, а map. (Хотя и на fold здесь спокойно обобщить).

-- конструирование отображённого узла
makeDstNode :: {-сам узел-} SrcNode -> {-отображённые поддеревья-} [DstNode] -> {-результат-} DstNode

-- доступ к поддеревьям
enumChildren :: SrcNode -> [SrcNode]

-- функция отображения выглядит так
mapTree :: SrcNode -> DstNode
mapTree node = makeDstNode node (map makeTree (enumChildren node))

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

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

Здравствуйте, Кодт, Вы писали:


_FR>>Требуется создать "модель" произвольного дерева (INode) в терминах Node.

К>Ага, вот что тебе захотелось.

Вот что выходит в в Squiggol-стиле (на линзах и бананах):

-- Рекурсивный тип данных rose tree с дополнительным типовым параметром b для Node
-- (чтобы, например, тип операций хранить)

--data Tree a b = Leaf a | Node b [Tree a b]

-- функтор, описывающий его рекурсивную структуру
data T a b t = Leaf a | Node b [t] deriving Show

instance Functor (T a b) where
 fmap g (Leaf x)  = Leaf x
 fmap g (Node b xs) = Node b (map g xs)

-- Выразим тип, как неподвижную точку функтора
type Tree a b = Rec (T a b)

Теперь осталось только писать нужные алгебры под катаморфизм (aka Визиторы) и коалгебры под анаморфизм (aka Билдеры). Например, эвалюторы:

-- типы операций
data Op = AddOp | MultOp -- можно добавлять операции сюда и в алгебры
-- T-алгебра для эвалютора арифметики: 
phiT :: T Int Op Int -> Int
phiT (Leaf x)    = id x
phiT (Node AddOp xs)  = sum xs
phiT (Node MultOp xs) = product xs
-- Применяя катаморфизм к алгебре получим эвалютор 
evalT = cata phiT

проверяем:

*Bis> evalT (In (Node AddOp [In (Leaf 1),(In (Node MultOp [In (Leaf 2),In (Leaf 3)])),In (Leaf 4),In (Leaf 5)]))
16
*Bis> evalT (In (Node MultOp [In (Leaf 1),(In (Node AddOp [In (Leaf 2),In (Leaf 3)])),In (Leaf 4),In (Leaf 5)]))
100

Можно эвалютор сделать и на стеках:

--  T-алгебра типа 
phiT' :: T Int Op ([Int] -> [Int]) -> ([Int] -> [Int])
phiT' (Leaf x)         = (x :) -- push
phiT' (Node AddOp xs)  = (sum     (foldr (.) id xs $ []) :) -- локальные стеки
phiT' (Node MultOp xs) = (product (foldr (.) id xs $ []) :) -- локальные стеки
-- дает стековый эвалютор
evalT' = cata phiT'

проверяем:

*Bis> evalT' (In (Node AddOp [In (Leaf 1),(In (Node MultOp [In (Leaf 2),In (Leaf 3)])),In (Leaf 4),In (Leaf 5)])) []
[16]
*Bis> evalT' (In (Node MultOp [In (Leaf 1),(In (Node AddOp [In (Leaf 2),In (Leaf 3)])),In (Leaf 4),In (Leaf 5)])) []
[100]

Здравствуйте, deniok, Вы писали:

_FR>>>Требуется создать "модель" произвольного дерева (INode) в терминах Node.
К>>Ага, вот что тебе захотелось.
D>Вот что выходит в в Squiggol-стиле (на линзах и бананах):

Ну понятно, что Хаскель творит чудеса.
Я немножко другое имел в виду: реализовать можно на любом языке (например, на C#, раз _FRED_ прототипирует на нём) — просто Хаскель удобен для прототипирования идей.
А идея состоит в том, что есть очевидный наивный алгоритм, который можно трансформировать, если наивность не вписывается в память или в многопоточность. Но если вписывается — то и городить огород незачем

Здравствуйте, Кодт, Вы писали:

К>-- конструирование отображённого узла
К>makeDstNode :: {-сам узел-} SrcNode -> {-отображённые поддеревья-} [DstNode] -> {-результат-} DstNode

К>-- доступ к поддеревьям
К>enumChildren :: SrcNode -> [SrcNode]

К>-- функция отображения выглядит так
К>mapTree :: SrcNode -> DstNode
К>mapTree node = makeDstNode node (map makeTree (enumChildren node))

Пытаюсь разобраться, не получается и не вижу, где не прав:

1. второй параметр makeDstNode (map makeTree (enumChildren node)) должен иметь тип [DstNode]
   
2. => map должен получать параметр, имеющий тип [SrcNode]
   
3. => makeTree получает [SrcNode] (результат enumChildren) и возвращает [SrcNode] — что же эта функция должна делать?

Здравствуйте, _FRED_, Вы писали:

К>>mapTree :: SrcNode -> DstNode
К>>mapTree node = makeDstNode node (map makeTree (enumChildren node))

_FR>Пытаюсь разобраться, не получается и не вижу, где не прав:
_FR>

=> makeTree получает [SrcNode] (результат enumChildren) и возвращает [SrcNode] — что же эта функция должна делать?

Ага, makeTree — это функция, создавающая экземпляр DstNode по SrcNode? Но как, например, она дожна выглядеть? Ведь создать экземпляр DstNode можно только из дочерних [ DstNode]?