| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > анализ выражения |
| Автор: Hidrag 6.3.2008, 17:43 |
| Задача такая нужно проанализировать выражение и удалить в нем лишние скобки, например: c=(a+b)+d должно получиться: с=a+b+d то есть нужно убрать скобки которые не влияют на результат. Выражение всегда правильное, то есть не будет такого что есть открывающая скобка и нет закрывающей. Из операций есть только + и * Язык программирования, не важен, главное алгоритм анализа. Я, конечно, буду сам пытаться написать парсер, но почему то кажется что задача обычная и наверняка есть и кто нибудь знает простое решение. С виду кажется вообще просто, но вдруг выражение будет: с=(a*b+c)*d здесь уже скобки должны остаться... |
| Автор: maxim1000 6.3.2008, 18:28 |
| в принципе, можно просто пробовать убрать каждую пару скобок и сравнивать выражения на эквивалентность (в данном случае - на порядок выполнения операций) правда, создаётся ощущение, что это окольный путь... |
| Автор: Hidrag 6.3.2008, 21:18 |
| не так все просто оказывается.... |
| Автор: Akina 6.3.2008, 22:04 | ||
На порядок выполнения - нельзя. Он может измениться. А вот деревья, построенные в обратно-польской нотации, окажутся эквивалентными. |
| Автор: maxdiver 6.3.2008, 23:45 |
| Нужно построить дерево разбора этого выражения, но так, чтобы в нём остались скобки (как особый элемент с одним дочерним элементом). Лишними окажутся скобки, дочерние элементу '+', дочерние '-' (но здесь уже в вычитаемом надо поменять знаки), а также скобки, дочерние скобкам. Вроде так все лишние скобки уберутся. Ещё есть идея построить обычное дерево разбора, а потом по нему построить выражение. В результате лишних скобок тоже не должно получаться. |
| Автор: Akina 7.3.2008, 09:29 | ||
Но это действие может изменить выражение. A+(B+C) превратится в B+C+A. Без скобок, но не то... |
| Автор: Serkys 7.3.2008, 09:41 | ||
А вот Hidrag надо уточнить условие, допустимы ли такие вещи. |
| Автор: Akina 7.3.2008, 09:56 | ||
Поскольку надо не получить конечное выражение, а только найти лишние скобки, с выражением можно делать что угодно - это очевидно. Просто после прямого-обратного преобразований выражение может измениться так, что понять, какие же скобки оказались лишними, тоже станет задачей нетривиальной... |
| Автор: maxim1000 7.3.2008, 11:07 | ||
если я правильно понял, то, думаю, скобки в данном случае не будут убраны: a*(b*c) |
| Автор: HistoryEarth 7.3.2008, 11:09 |
| Вылядит это так, что достаточно искать и убирать конструкции типа ")+" и "+(". Предварительно считая вложенность и пр. |
| Автор: Hidrag 7.3.2008, 11:46 |
| Serkys, Допустимы! Выражения сами по себе не очень сложные, поэтому от перестановки членов выражения ничего не меняется. А что за прямое-обратное преобразование? |
| Автор: Serkys 7.3.2008, 12:13 | ||
Имеется в виду построение дерева выражения и последующее составление нового выражения на основе этого дерева. |
| Автор: maxdiver 7.3.2008, 19:47 | ||||
Да, точно, как раз сейчас хотел об этом написать  Если у скобки дочерним элементом является константа или переменная, то она, разумеется, тоже лишняя. Вот теперь вроде всё |
| Автор: Void 7.3.2008, 20:58 | ||
Я недавно описывал алгоритм восстановления выражения по дереву с минимально необходимым числом скобок. Когда-то писал на OCaml для простенького интерпретатора.
|
