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

Первый пошёл! А внутре у него как будто не та же самая неонка. Интересует ответ в рамках си/плюсов — промышленные компиляторы вон все на них.

http://llvm.org/docs/CodingStandards.html#do-not-use-rtti-or-exceptions

http://stackoverflow.com/a/5138926/2075370

Если размер бинарника не важен, а скорость работы упирается во что-то другое, то на все это можно забить

dynamic_cast вреден — почему?

От него волосы на ладонях растут.

Ага, понятно. То есть, архитектурной проблемы здесь нет?

(Допустим, что на производительность сейчас пофиг, да и всегда можно выкинуть dynamic_cast<> и заменить более быстрым велосипедом по типу LLVM-ного.)

Оффтоп

Зачем ты везде std::move пихаешь?

У меня указатели на узлы хранятся в std::unique_ptr<> (он по определению не копируется, только перемещается).

Там, кстати, последний коммит немного понижает количество move'ов, тоже по совету с ЛОРа (оказывается, в return-statement можно не писать move, для локальных переменных он подразумевается неявно).

То есть, архитектурной проблемы здесь нет?

Архитекурная проблема возникает, когда RTTI применяют вместо виртуального интерфейса, общего для всей иерархии классов. Если узлы дерева настолько разные, что сводить все под одну гребенку несподручно, вполне допустимо использовать каст вниз (при этом не допуская повторов кода, в особенности повторяющих свитчей по типу объекта)

В clang работа с AST организована именно так

Вреден он обычно потому что а) небыстр б) указывает на архитектурную проблему в плане отсутствия правильно спроектированного общего предка. Я навскидку не скажу как тут можно было бы правильно сделать общего предка и можно ли, но скажу что твою операцию можно реализовать другим visitor'ом - и скорее всего это будет быстрее и менее криво, возможно удобнее. Думаю понятно, что легко написать шаблон такого Visitor'а параметризируемый типом/типами нужных узлов, а самому объекту передавать лямбду которая будет обрабатывать эти узлы. Как-то так

    SelectiveVisitor<Node::AdditionSubtraction> v(
        [this](Node::AdditionSubtraction& n) {
            my_nodes.push_back(n); // добавляем в текущую ноду или что там нужно 
        }
    );

промышленные компиляторы вон все на них

Какие-какие компиляторы?

Промышленные. GCC, там, clang... Знаешь такие?

"Я вам не скажу за всю Одессу..."

Но таки да, полностью согласен. Более того, именно в задаче ТС (работа с AST для алгебраического выражения) все решается именно что правильным общим предком и банальным полиморфизмом.

GCC, там, clang

ghc, sbcl

А вообще анон в первом комменте прав насчёт pattern matching: это сильно упростит твой код. Заюзай Mach7 от трупа страуса (https://github.com/solodon4/Mach7). Зачем это нужно, можешь прочитать здесь http://www.stroustrup.com/OpenPatternMatching.pdf

В задачах вида «обойти всё и обработать» такой подход и вправду выглядит неплохо.

А если нужно реагировать не только на совпадения, но и на несовпадения, при этом ещё в каких-то комбинациях? Что-то вроде такого:

if (dynamic_cast<TypeA> (n1) && dynamic_cast<TypeB> (n2)) {
    // сделать что-нибудь с n1 и n2
} else if (dynamic_cast<TypeC> (n1) && dynamic_cast<TypeD> (n3)) {
    // сделать что-нибудь с n1 и n3
}

Или в каждом случае нужно придумывать свой подход, а общего рецепта не существует?

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

Можно было бы потыкать. Но, чувствую, долго придётся разбираться и придумывать, как бы его применить.

А если нужно реагировать не только на совпадения, но и на несовпадения, при этом ещё в каких-то комбинациях?

Так в чём проблема, visitor позволяет написать обработчики для всех типов. Разница только в том как написать более удобную обёртку.

А в каком месте тут можно заюзать полиморфизм?

Обычно выделяются свойства, по которым TypeA и TypeB в примере обрабатываются одинаково, для них пишется виртуальный метод. Как-то так.

Вообще-то в любой книжке по плюсам подробно объясняется, почему не рекомендуется использовать dynamic_cast.

На каждое заводить по методу в базовом классе?

Да.

Действий достоаточно мало на самом деле. Многое можно сгруппирвать. Многие вещи удается улучшить если ввести промежуточные типы, скажем для бинарных/унарных операций.

Я как бы эту задачу знаю (про AST для алгебры), делал так и эдак. Здесь при хорошем дизайне каст не нужен.

При плохом... ну будет убого;-)

С помощью тогоже visitor'a и двойной диспетчеризации, ты можешь решить эту задачу не дергая крестовый рантайм.

пройтись по всем потомкам узла и применить к каждому dynamic_cast<Node::AdditionSubtraction*>()?

Тормозить будет так, как будто программа написана на питоне. Проще сразу взять питон.

кидайте помидоры

Ок, посмотрел код - доопределять интерфейс класса в каждом наследнике, это очень хреновая идея, просто жесть. Не удивительно что у тебя везде лезет dynamic_cast.

В упор не вижу, как можно обойтись только общим интерфейсом, совсем без преобразований вниз. Разве что танцевать с визиторами.

при хорошем дизайне

Каковы свойства хорошего дизайна?

Как обойтись общим интерфейсом? У всех этих «дополнительных» методов разные сигнатуры.

С Node::Value::value() ещё понятно — можно заставить его возвращать какой-нибудь boost::optional или ещё как-то сигнализировать о том, что числа нет (если узел — не число). Но блин, это вправду считается лучше, чем явный даункаст?

компилятор Java не промышленный?

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

gcc твой любимый на си написан исключительно по одной причине - легаси.

прикладные программы, в т.ч. компиляторы, в 2014м году писать на C++ или Си это не то что некомильфо, это руки надо отрубать

Потому что это вырождается в задротство а не решение задачи. Типа вот, вместо того чтобы думать об алгоритме парсера или кодогенератора или чего там, начинается борьба с C++, окостыливание во все поля и так далее. А потом еще гордятся - смотрите как я умело расставил костыли, вроде даже не падает.

Я, ваще-то, recursive descent и использую.

Не заметил ничего такого. За исключением того, что вот внезапно выяснилось, что dynamic_cast<> юзать нельзя (а что юзать вместо него — не очень-то и понятно).

слейся, лалка борщевая

зачем тебе вообще dynamic_cast или visitor?

enum node_type
{
  ...
};

struct node
{
  enum node_type type;
  ...
};

Потому что это реимплементация ООП-средств плюсов, т. е. велосипедизм. А визиторы придётся юзать и здесь.

нет, это не «реимплементация», во-первых. даже в т.н. книге дракона и даже в примерах на java - используется именно такой подход. во-вторых - в c++ нет ооп, а то что есть - говно которое лучше использовать по минимуму(и то, если легаси досталось - а так лучше вообще не использовать).

он уже сто раз реализован, в том числе на крестах. ни разу не видел там кастов. сходи в гугл и посмотри как пишут нормальные люди.

Потому что это реимплементация ООП-средств плюсов, т. е. велосипедизм

Да, но это быстрый велосипедизм. Qt так делает, а ты чем хуже?

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

Тред и код не читал, про RPN для оптимизации выражений уже сказали?

Нет.

http://en.wikipedia.org/wiki/Reverse_Polish_notation

Я знаю, что это. Как оно сюда относится?

В упор не вижу, как можно обойтись только общим интерфейсом, совсем без преобразований вниз. Разве что танцевать с визиторами.

Пишем в базовом классе виртуальный метод (рекурсивный), специализируем его для наследника нужным образом - профит! Дальше хороший дизайн нужен что бы большую часть программы занимала содержательная часть, а не какая то хрень типа организации рекусии для каждого из 100500 методов.

Каковы свойства хорошего дизайна?

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

И да, никто не говорит что каст юзать НЕЛЬЗЯ. Говорят что юзание каста хороший повод задуматься, м.б. ты что то делаешь не так. Это как с глобальными переменными же;-)

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

Да нету здесь уже никакой записи - ни инфиксной ни постфиксной. Есть дерево. Оптимизация будет по дереву. А ТС немного неправильно понимает слова наследование, интерфейс и проведение типов.

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

Вау. А дерево - это инфиксная или постфиксная запись?

Это я вот о чем. ТС, если твои «выражения» действительно имеют «тип» - я говорю сейчас не о типе, который ты выбрал в языке программирования для их представления, а об их «типе» в качественном смысле (это то, что определяет их поведение), и если действительно выражения одного «типа» можно приводить к другому «типу», то в поведении выражений должна быть такая возможность. Например, ExprType1 ExprType1.makeFrom(ExprType2 expr); Задумайся над этим.

Следует отличать «тип» выражения от типа представления выражения. Узел дерева это лишь представление выражения. Как, например, абстрактное значение 10 имеет представления int x=10 и Integer y=Integer(10).  Это что касается приведения типов в твоей системе.

Далее. Твой пример в начале можно расширить: преобразование выражения e1 op1 (e2 op2 e3). Правила преобразования существуют вообще отдельно от типов выражений и могут быть такими: 1) op1(е1, e2, e3) 2) (e1 op1 e2) op2 (e1 op1 e2) 3) (e1 op1 e2) op2 e3 4) и так далее...

Какие правила применимы для выражения определяется «типом» выражения. И если в первом случае «тип» сохранился, то во втором и третьем изменился. И мы конструировали новые выражения из операндов исходных выражений.

Пишем в базовом классе виртуальный метод (рекурсивный), специализируем его для наследника нужным образом - профит!

Говорю же — в упор не вижу, что можно вытащить в базовый класс. У add_child()'ов и children() сигнатуры разные, т. к. в зависимости от типа узла к каждому потомку прилагаются свои «метаданные». Методы, определённые в Node::Value, специфичны именно для чисел — неужели нужно вытащить их в Node::Base и заставить возвращать boost::optional? И так везде.

Говорят что юзание каста хороший повод задуматься, м.б. ты что то делаешь не так.

Ну так я и хочу узнать, что конкретно у меня не так (и что конкретно сделать, чтобы было «так»).

dynamic_cast вреден — почему? (комментарий)

Если есть визитор, то зачем dynamic_cast? примени визитор конкретного типа (я так понимаю - типа текущего узла ) ко всем потомкам, и получишь то что нужно, не? То что визитор это и есть двойная диспетчеризация понимание есть?

как ты все успеваешь? Ты же в mipt учишься, там же нужно ботать сутками.