C++: раскрыть скобки, ДНФ ?

[Win32nipuh]

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

(a+b)*c -> a*c + b*c

[Isaev]

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

(a+b)*c -> a*c + b*c

Строишь дерево разбора
Потом опускаешь операции с большим приоритетом вниз.

Code: Select all

         *                 +
      +     c   ->     *       *
    a   b            a   c   b   c

Сворачиваешь дерево обратно в строку.
Для построения дерева нужен алгоритм Дейкстры.

[Win32nipuh]

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

(a+b)*c -> a*c + b*c

Строишь дерево разбора
Потом опускаешь операции с большим приоритетом вниз.

Code: Select all

         *                 +
      +     c   ->     *       *
    a   b            a   c   b   c

Сворачиваешь дерево обратно в строку.
Для построения дерева нужен алгоритм Дейкстры.

Для построения или свертки? Что-то вспоминается, но смутно
Построить дерево не проблема, а вот алгоритм свертки?

[Big Cheese]

Построить дерево не проблема, а вот алгоритм свертки?

Обойти полученное дерево слева направо?

[Win32nipuh]

Построить дерево не проблема, а вот алгоритм свертки?

Обойти полученное дерево слева направо?

Обход дерева не проблема, как это сделать:
"Потом опускаешь операции с большим приоритетом вниз. " -?

[Big Cheese]

Навскидку, что пришло в голову:

рекурсивно обходить дерево по следующей схеме:
- функция обхода возвращает список "слагаемых"
- зашли в узел, если leaf - вернуть значение ("а")
иначе - получить списки для левого и правого поддеревьев (ну, типа рекурсия )

если node == '+' - добавить "правый" вектор в конец левого, вернуть полученный список

если node == '*' - "перемножить" вектора, вернуть произведение (L:"a,b", R:"c, d" = OUT: "ac, ad, bc, bd")

... результат рута распечатать через знак "+"

[A. Fig Lee]

1)Накапливаем в баффере input пoка не попалась скобка
2)Попалась скобка - зовем сами себя
3)Внутри скобки в рекурсивной функции опьять накапливаем баффер пока не попалась скобка - любая:
-) если закрывающая - читаем следующий опратор и операнд, апплаим их к сиквенси и результат
выплевываем наверх, где будет тоже самое
-) если открывающая скобка - зовем сами себя и результат етой функции запихаваем в тот же
накопительный баффер, пока закрывающая не придет.
В качестве баффера годится ФИФО.

[Isaev]

Построить дерево не проблема, а вот алгоритм свертки?

Обойти полученное дерево слева направо?

Обход дерева не проблема, как это сделать:
"Потом опускаешь операции с большим приоритетом вниз. " -?

Приоритеты операций:
цифра/буква - 3, "+" - 1, "*" - 2;

Рекурсивно, все операции производятся над поддеревьями:

Code: Select all

if leaf return;
else
{
  if( priority of current node > piority of left node )
  {
     rebuild tree like this:
         *                 + 
      +     c   ->     *       * 
    a   b            a   c   b   c      
  }
  if( priority of current node > piority of right node )
  {
    same as above, node "c" and "+" поменяны местами.
  }
  if( both left and right nodes have smaller priority )
  {
    rebuild them both.
  }
  go down from left to right;
}

Свернуть дерево обратно в строку - простой обход дерева:

Code: Select all

print( left subtree );
print( operation in current node );
print( rihgt subtree );

Даже скобки расставлять не надо, так как дерево "отсортировано" по приоритетам операций.

[Win32nipuh]

Построить дерево не проблема, а вот алгоритм свертки?

Обойти полученное дерево слева направо?

Обход дерева не проблема, как это сделать:
"Потом опускаешь операции с большим приоритетом вниз. " -?

Приоритеты операций:
цифра/буква - 3, "+" - 1, "*" - 2;

Рекурсивно, все операции производятся над поддеревьями:

Code: Select all

if leaf return;
else
{
  if( priority of current node > piority of left node )
  {
     rebuild tree like this:
         *                 + 
      +     c   ->     *       * 
    a   b            a   c   b   c      
  }
  if( priority of current node > piority of right node )
  {
    same as above, node "c" and "+" поменяны местами.
  }
  if( both left and right nodes have smaller priority )
  {
    rebuild them both.
  }
  go down from left to right;
}

Свернуть дерево обратно в строку - простой обход дерева:

Code: Select all

print( left subtree );
print( operation in current node );
print( rihgt subtree );

Даже скобки расставлять не надо, так как дерево "отсортировано" по приоритетам операций.

Идея понятна, уточнение:

при перестройке начинаем обход с корня, т.е. приблизительно так:

Regresion(pRootNode);

void Regresion(CNode* pRootNode)
{
//processing as above described
Regresion(pRootNode->GetLeftNode());
Regresion(pRootNode->GetRightNode());
}

[Isaev]

Идея понятна, уточнение:
при перестройке начинаем обход с корня, т.е. приблизительно так:

Regresion(pRootNode);

void Regresion(CNode* pRootNode)
{
//processing as above described
Regresion(pRootNode->GetLeftNode());
Regresion(pRootNode->GetRightNode());
}

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

Code: Select all

printf( left_subtree );
printf( left_subtree );
printf( operation );

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

[Win32nipuh]

Идея понятна, уточнение:
при перестройке начинаем обход с корня, т.е. приблизительно так:

Regresion(pRootNode);

void Regresion(CNode* pRootNode)
{
//processing as above described
Regresion(pRootNode->GetLeftNode());
Regresion(pRootNode->GetRightNode());
}

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

Code: Select all

printf( left_subtree );
printf( left_subtree );
printf( operation );

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

Спасибо, uuid, Ваша предыдущая посдказка помогла, правда, сначала сбило с толку то, что перестраивать оба поддерева нужно, я так и начал честно реализовывать, три варианта. Но, оказадось, что достаточно двух первых веток, третья укладывается в первые.Т.е. когда * в вершине, а в двух чилдах +.
Отлично строится ДНФ, то, что надо.

[Isaev]

Спасибо, uuid, Ваша предыдущая посдказка помогла, правда, сначала сбило с толку то, что перестраивать оба поддерева нужно, я так и начал честно реализовывать, три варианта. Но, оказадось, что достаточно двух первых веток, третья укладывается в первые.Т.е. когда * в вершине, а в двух чилдах +.
Отлично строится ДНФ, то, что надо.

Это не влияет. Оно бы работало и с третьим выриантом, и, скорее всего, дерево было бы более сбалансированным.