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

А>>"(a+b)*c" и "a*c + b*c" — это примеры входной и выходной строки. Т.е. на входе и выходе — строки. Хотя, понятно, что если предложишь алгоритм, возвращающий выражение в каком-то внутреннем представлении (дерево, пфз), то тоже пойдёт.

А>Про дерево или пфз — погорячился, этого недостаточно. Оно есть, но автоматически из него выражение с раскрытыми скобками не следует. Собственно, этот — шаг раскрытие скобок — как раз и интересует.

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

      α
     / \
    /   \
   β     z
  / \
 /   \
x     y

Где α и β — некие операции, а x, y, z — поддеревья (α тоже не обязано быть корнем).
При этом если приоритет у операции α выше чем у операции β, то это означает наличие скобок, а следовательно необходимость преобразования этого участка дерева. Если же приоритет α не превосходит приоритета β, то этот участок дерева можно не трогать.

Если замена нужна, и при этом операции β и α обладают свойством дистрибутивности справа, то такое дерево заменяется на

       β
      / \
     /   \
    /     \
   α       α
  / \     / \
 /   \   /   \ 
x     z y     z

Тут x, y, z всё те же поддеревья. Для которых аналогичную процедуру можно повторить рекурсивно.

Такой обмен можно не задумываясь делать для любых операций, если для них выполняется свойство дистрибутивности. Так как в ДНФ есть только три операции, то таких замен достаточно для преобразования любого выражения.

Соответственно одна итерация алгоритма может выглядеть как проход по дереву сверху вниз до первой неупорядоченной пары операций, за которым следует обмен поддеревьев и рекурсивный вызов.
А весь алгоритм будет совсем прост — делаем итерации пока есть изменения.

Если немного подумать, то оказывается, что вся схема практически аналогична алгоритму сортировки пузырьком.
Тут правда не получится из пузырьковой сортировки сделать что-то более быстрое, так как у деревьев можно обменивать только соседние уровни.
Но всё равно можно немного задуматься об оптимизации и не делать, например, итерации на полную глубину каждый раз. Или хранить выражение, возможно, не в виде дерева, а в виде DAWG, что позволит сливать одинаковые подвыражения в процесса преобразований. Впрочем для правильности алгоритма это уже не важно.

В поиске нашёл тему http://rsdn.ru/forum/cpp/463315.aspx

Автор:
Дата: 01.12.03

, но на неё не было дано нужного ответа.

Может быть, сейчас кто-нибудь напомнит алгоритм для раскрытия скобок в выражении.
Т.е. как "(a+b)*с" превратить в "a*c + b*c"? (* приоритетнее, чем +)?
Спасибо.

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

А>Может быть, сейчас кто-нибудь напомнит алгоритм для раскрытия скобок в выражении.
А>Т.е. как "(a+b)*с" превратить в "a*c + b*c"? (* приоритетнее, чем +)?
А>Спасибо.

Ну слушай. Алгоритм такой: взять то, что за скобками, его и скобки убрать, а каждое слагаемое, что было внутри скобок, умножить на этот множитель. Нам в школе рассказывали.

Если чуть серьезнее, то уточни задачу. На входе строка? Длинная? Есть ли другие операции в ней? Лобовое решение — рекурсивным спуском парсить, а при возврате из рекурсии сразу "умножать" и строить новую строку.

DM>Ну слушай. Алгоритм такой: взять то, что за скобками, его и скобки убрать, а каждое слагаемое, что было внутри скобок, умножить на этот множитель. Нам в школе рассказывали.



DM>Если чуть серьезнее, то уточни задачу. На входе строка? Длинная? Есть ли другие операции в ней?

Если из вопроса "как "(a+b)*с" превратить в "a*c + b*c"? (* приоритетнее, чем +)" не ясно, попробую уточнить.

"(a+b)*c" и "a*c + b*c" — это примеры входной и выходной строки. Т.е. на входе и выходе — строки. Хотя, понятно, что если предложишь алгоритм, возвращающий выражение в каком-то внутреннем представлении (дерево, пфз), то тоже пойдёт.

Если алгоритм принципиально зависит от длины входной строки (а также от кол-ва переменных (a,b,c в примере), кол-ва и ранга операций (в примере только + и — с разными приоритетами), глубины вложенности скобок), то желательно привести более универсальный алгоритм, т.е. не зависящий от длины входной строки (потенциально на входе сколь угодно длинная строка), кол-ва переменных и их вхождений, кол-ва и желательно ранга операций (для примера можно добавить ! — унарная операция отрицание), глубины вложенности скобок.

DM>Лобовое решение — рекурсивным спуском парсить, а при возврате из рекурсии сразу "умножать" и строить новую строку.

Ну, парсить — это понятно. А вот про "умножать при возврате из рекурсии" — можно поподробнее?

А>"(a+b)*c" и "a*c + b*c" — это примеры входной и выходной строки. Т.е. на входе и выходе — строки. Хотя, понятно, что если предложишь алгоритм, возвращающий выражение в каком-то внутреннем представлении (дерево, пфз), то тоже пойдёт.

Про дерево или пфз — погорячился, этого недостаточно. Оно есть, но автоматически из него выражение с раскрытыми скобками не следует. Собственно, этот — шаг раскрытие скобок — как раз и интересует.

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

WM>Если у тебя уже есть дерево, то преобразовать его в дерево, соответствующее выражению после раскрытия скобок, не сложно.
WM>Пусть у тебя есть такая ситуация:
WM>

WM>      α
WM>     / \
WM>    /   \
WM>   β     z
WM>  / \
WM> /   \
WM>x     y
WM>

WM>Где α и β — некие операции, а x, y, z — поддеревья (α тоже не обязано быть корнем).
WM>При этом если приоритет у операции α выше чем у операции β, то это означает наличие скобок, а следовательно необходимость преобразования этого участка дерева. Если же приоритет α не превосходит приоритета β, то этот участок дерева можно не трогать.

Почему из приоритета операции следует наличие скобок не понятно. Но ход мысли приблизительно такой. Необходимо скобки считать самой приоритетной операцией (с приоритетом 0). Вообще говоря это так и есть. С этим лоаолнением и построить дерево. А раскрывать скобки именно так как ты и сказал, только не сравнивая приоритеты операций, а по равенству приоритета операции 0.Исходное дерево строится классическим алгоритмом с еще одной операцией скобки. Только не убирая их, а оставляя как операцию.

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

B>Почему из приоритета операции следует наличие скобок не понятно.
Потому что в дереве или в префиксной записи скобки никогда не нужны. Любое выражение записывается без них. Скобки — это такой артефакт инфиксной записи, и появляются они только при нарушении порядка приоритета операций.

Разумеется, есть ещё косметические скобки, которые не влияют на смысл выражения, например, (3*4)+5 и 3*4+5. Но такие скобки исчезают опять же при переводе из инфиксной формы ещё до каких-либо преобразований выражения.

B>Но ход мысли приблизительно такой. Необходимо скобки считать самой приоритетной операцией (с приоритетом 0). Вообще говоря это так и есть.

Расскажи, пожалуйста, почему ты считаешь, что так и есть? Какой, например, из языков программирования рассматривает скобки как операцию?

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

WM>Какой, например, из языков программирования рассматривает скобки как операцию?

js

var f = function() { alert("Hi!"); return 10; };
var a = f; // function reference
var b = f(); // 10

Здравствуйте, Аноним, Вы писали:
А>Может быть, сейчас кто-нибудь напомнит алгоритм для раскрытия скобок в выражении.
А>Т.е. как "(a+b)*с" превратить в "a*c + b*c"? (* приоритетнее, чем +)?
А>Спасибо.
Думаю, проще всего построить дерево выражения — и обойти его, как при вычислении арифметического выражения, просто подобрать правильные типы данных и реализацию для + и *. Например, ввести два типа данных: строка символов (результат умножения) и вектор строк (результат сложения), при этом,
1. Значение листа x = (x) — вектор из строки в один символ.
2. Если xi и yj — произвольные строки, то (x1, x2, x3, ..., xn) + (y1, y2, y3, ..., ym) = (x1, x2, x3, ..., xn, y1, y2, y3, ..., ym).
3. Если xi и yj — произвольные строки, то (x1, x2, x3, ...) * (y1, y2, y3, ...) = (x1y1, x1y2, ..., x1ym, x2y1, x2y2 ..., x2ym, ... xny1, ... xnym).
Вычитание, группировку множителей и слагаемых — по вкусу.

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

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


WM>Расскажи, пожалуйста, почему ты считаешь, что так и есть? Какой, например, из языков программирования рассматривает скобки как операцию?
Не как опереацию, а как приоритет. И причем тут другие языки? В данной, конкретной задаче можно и оставить скобки. Кстати, когда создавал дерево в своем языке тоже оставлял скобки формулируя их как операцию с высоким приоритетом. Удалял их при формировании последовательности вычислений. Получилось компактней в рекурсии.

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

А>Может быть, сейчас кто-нибудь напомнит алгоритм для раскрытия скобок в выражении.
А>Т.е. как "(a+b)*с" превратить в "a*c + b*c"? (* приоритетнее, чем +)?

Как тут уже писали инфиксная нотация и алгоритм сортировочной станции решают твою задачу.