Операции со строками в ОПЗ (помощь в обучении)

[Tema]

Добрый день.

Пишу программу, часть которой занимается обработкой числовых выражений("2-3*(6+6/2)" etc.) и подсчетом сего выражения.
Для решения здачи парсинга строки выбрал метод перевода в Обратную Польскую Запись с последующим подсчетом. Благо информации по этому достаточно, вопросов нет.(known issue: не поддерживаю унарные операции)
Но, теперь надо бы добавить возможность работы со строками в таком же формате: "abc+cba+2*(ab+c)".
Насколько я понимаю, есть смысл реализовывать логику только для двух операций: умножение и сложение. При этом есть ряд ограничений: при умножении один из множителей должен быть числом, к примеру.

Хочу показать свой класс, который занимается работой с ОПЗ: перегон в ОПЗ и подсчет.
Как бы лучше добавить туда поддержку операций со строками? отдельным методом или попробовать сделать общий метод подсчета с ветвями в зависимости от того какие операнды? Общий метод можно будет подробить на методы(например вынести отдельно два метода для умножения и сложения, т.к. они будут отличаться для чисел и строк). Можно даже сделать абстрактный класс, затем наследовать от него мой и еще один для строковых выражений, оставить метод парсинга одинаковый, а метод подсчета сделать виртуальным и переопределить его в каждом "ребёнке".

Что я думаю по этому поводу: нет смысла особо делить, т.к. прийдется пихать проверку: есть ли буквы в выражении и потом что-то делать. При этом для умножения прийдется еще раз искать какой из множителей число. ИМХО, лучше сделать общий метод и уже в каждой ветке операции решать что делать.

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

cpp - http://pastebin.com/wYvYHqyi
h - http://pastebin.com/0xsMi07a

Спасибо

[Bizdelnick]

Извиняюсь, вникать в код времени нет, но делать вот так:

Код: Выделить всё

using namespace std;

в заголовке точно не стоит. И вообще какие бы то ни было using в заголовок вставлять не надо. А то потом эффект может оказаться не слабее, чем от

Код: Выделить всё

#define true false

[Hephaestus]

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

Что я думаю по этому поводу: нет смысла особо делить, т.к. прийдется пихать проверку: есть ли буквы в выражении и потом что-то делать. При этом для умножения прийдется еще раз искать какой из множителей число. ИМХО, лучше сделать общий метод и уже в каждой ветке операции решать что делать.

Вижу здесь проблему в том, что для строки и числа разный набор доступных операций. Поэтому общим методом, по-моему будет неудобно.
А кстати, что должно получиться при "вычислении" буквенного выражения?
И вообще неясна конечная задача. Как это должно работать?

P.S. В код не вникал.

[Tema]

Bizdelnick,
Спасибо, уяснил.

Hephaestus,
Целиком программа является мини-спредшит обработчиком чтоли. Принимает на вход матрицу из значений(в том числе формуы, в том числе со ссылками на другие ячейки).
Тот кусок, что я привел - это всего лишь часть, в которой реализовано приведение формулы "1+2-3" к "0".
Со стороками, как я понимаю, это "2*abc" = "abcabc", "abc+ccc" = "abcccc". Можно конечно поизвращяться, и к операции "-" прикрутить логику replace, но я решил пока ограничиться + и *.

Этот класс используется так:
1. в другом классе создаем ссылку на объект этого класса. "Другой" класс - это Парсер, который из "=A1-B2*(3+4)-2" сделает "1-2*(3+4)-2".
2. По ссылке вызываем метод performCalculation() котому аргументом передаем строку вида "1-2*(3+4)-2".
3. performCalculation() должен запустить две основных метода: parseFormula() - кторый на вход получает строку формата как описал выше, и вернуть ссылку на вектор строк, в котором будет содержаться это же выражение, но в обратной польской записи, типа ["1","2","3","*","+", "4".....] (это не точный перевод).
4. то, что возвращает parseFormula() передаем второму ключевому методу: evaluateFormula(), который из вектора строк посчитает результат и вернет его. Это в свою очередь получит другой класс.

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

Спасибо.

PS:
Перечитывал про логику операторова и пришла еще такая мысль в голову: можно сделать класс операнда формулы, вместо того, чтобы хранить операнд в строке. Тогда можно будет описать математические операторы так, как захочу. Норм идея?

[NickLion]

1. Зачем писать такое: vector<string> * ReversePolandNotation::parseFormula(string * input)
Почему не передавать input как ссылку (даже константную, см. 2)?
Зачем возвращать указатель на новый объект? Вы используете C++ стандарта С++11 или выше, так что у std::vector есть конструктор перемещения и лишнего копирования не будет. Если хочется явно, то лучше использовать умные указатели. У Вас происходит утечка памяти создаётся вектор строк, передаётся в другую функцию, там используется и не уничтожается.

2. Удаление первого символа в строке не лучший вариант для работы со строками, так как стандартно копирует всю строку со смещением на 1. Вы используете только текущий символ, почему не итерировать при помощи того же for (auto c : input) ?

3. evaluateFormula(vector<string> * formula)
Аналогично 1.

4. Постоянное вычисление getPriority без побочных эффектов с одним и тем же аргументом — лишнее. Не смертельно, функция простая, но всё же лучше вынести в переменную, будет ясно видно, что это значение не меняется и легче читать.

[Hephaestus]

Со стороками, как я понимаю, это "2*abc" = "abcabc", "abc+ccc" = "abcccc"

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

Если в код сразу не вникли, значит я написал кривовато

Да я и не пытался. Мне важнее было уяснить идею, а не реализацию.

Перечитывал про логику операторова и пришла еще такая мысль в голову: можно сделать класс операнда формулы, вместо того, чтобы хранить операнд в строке.

Хотел посоветовать нечто подобное.
Например, общий класс "операнд". Дочерние от него "операнд-строка" и "операнд-число".
Для общего класса метод проверки типа, для дочерних - методы - допустимые операции.
Тогда все необходимые проверки будут внутри класса. А исходное выражение будет состоять из нескольких экземпляров класса.
Казалось бы, всё красиво, но всё равно в итоге приходим к парсингу строки. Поэтому сомневаюсь, что такое решение имеет смысл.
Впрочем, никто не запрещает обдумать и попробовать.

[Tema]

NickLion,
Огромное спасибо за ревью. Согласен по всем пунктам кроме 4-го. Я не понял, что Вы там имеете в виду. Как от метода к переменной уйти?..
За утечку памяти обидно, про конструктор перемещения не знал. Я в принципе пока еще плохо ориентируюсь, что стоит на стеке создавать, а что в куче. Исходя из знаний и опыта на текущий момент, то, что мало "весит" и часто используется. или от него требуется быть доступным быстро - это на стеке создаем, все остальное в куче. Про то, что строку лучше передвать ссылкой, я сегодня вычитал, как раз вот буду менять. Про удаление символа из строки, я тоже не в курсе был, спасибо. Очень практичные замечания!

Hephaestus,
Я согласен, что будет немного топортно. С другой стороны, тип операнда можно определять в методе parseFormula(), когда преобразовываем из обычной строки в ОПЗ строку. Там и без того идет проверка на тип. Можно сразу же в зависимости от типа создавать указатель на абстрактный класс и присваивать ему указатель на объект дочернего класса. Все это сложить в вектор ссылок абстрактного класса. Получится своего рода имплементация factory design pattern или не получится, но можно привести.

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

Код: Выделить всё

vector<shared_ptr<Operand>> rnpVector;
if (isalpha(character))
{
    rnpVector.push_back(make_shared<StringOperand>(character))
}
else {
    rnpVector.push_back(make_shared<DigitOperand>(character))
}

Не знаю, Вы об этом же говорили или нет. Но как мне кажется, в моих мыслях, дальше будет гораздо проще работать с таким вектором.

Спасибо!

[Hephaestus]

Не знаю, Вы об этом же говорили или нет.

Не совсем. Я говорил о реализации класса в рамках ООП со всеми вытекающими.
Но как я уже сказал, это только на первый взгляд удачно, а на самом деле излишне.

В Си я только ещё разбираюсь, а в плюсах почти совсем не разбираюсь, но насколько мне известно, вектор в плюсах соответствует массивам в Си.
Это решение уже больше подходит.
Но я бы использовал массив элементов такого типа, который в Си называется "структура", а в Pascal называется "запись".
Как это в плюсах - увы, не в курсе.

[NickLion]

Hephaestus
Так там и есть массив объектов. Объект — экземпляр класса, а класс — это структура + методы. К тому же в C++ нет разницы между структурой и классом, кроме модификатора доступа по умолчанию.

BOSS
В 4 пункте я про это говорил:

Код: Выделить всё

if (getPriority(input->at(0)) >= 2)
...
while ((signs->size() != 0) && (getPriority(signs->top()) >= getPriority(input->at(0))))
...
else if (getPriority(input->at(0)) == 1)
...
else if (getPriority(input->at(0)) == 0)

Во всех случаях значение getPriority(input->at(0)) будет одним и тем же, поэтому вычислять его каждый раз заново — излишне. В данном случае это совсем не смертельно, более того, на высоких уровнях оптимизации компилятор скорее всего развернёт getPriority как inline функцию и сократит вычисления. Но лучше всё же написать так:

Код: Выделить всё

const int priority = getPriority(input->at(0));
if (priority >= 2)
...
while ((signs->size() != 0) && (getPriority(signs->top()) >= priority))
...
else if (priority == 1)
...
else if (priority == 0)

Как мне кажется, такое проще потом читать (меньше скобок, ясно, что приоритет текущего символа и он не меняется). К тому же, const int даже для не очень продвинутого компилятора означает оптимизируй меня как хочешь :-) Т.е. скорее всего эта переменная даже храниться в памяти не будет. И чуть не забыл, лучше заиметь такую привычку на будущее, когда будут аналогичные повторные вызовы метода, уже автоматически создаёшь переменную и меньше нагрузки во время выполнения.

И ещё насчёт 4 пункта, если не ясно что такое функция без побочных эффектов — это такая функция, значение которой зависит лишь от её параметров. Соответственно, с побочными эффектами — значение функции с одними и теми же параметрами может отличаться (например, на её выполнение влияет текущее время (time(0)), ввод пользователя (scanf("%d", &n); cin >> n), внутреннее состояние/статическая переменная (rand())).

[NickLion]

Я в принципе пока еще плохо ориентируюсь, что стоит на стеке создавать, а что в куче. Исходя из знаний и опыта на текущий момент, то, что мало "весит" и часто используется. или от него требуется быть доступным быстро - это на стеке создаем, все остальное в куче.

Для начала такой подход сойдёт Но помните, что подвох с std::vector, std::string, и другими, в том, что в стеке хранится только сам оболочка (указатели на данные, размер и т.п.), а не данные, данные уже хранятся в куче. Например, для G++ 5.2 и 64-х битной программы в стеке std::string будет занимать 8 байт, а std::vector<int> — 24 байта. Всё остальное (данные) — в куче. Естественно, для другого компилятора, другой платформы значение может отличаться, но суть остаётся — это не так много байт данных.

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

[Tema]

NickLion,

Огромное спасибо за развернутый ответ. Исправил всё, кроме пункта 4. Ядумаю, что мы непраивльно друг друга поняли.
Несмотря на то, что там постоянно берется приоритет нулевого символа, у меня он каждый проход по циклу меняется т.к. я урезал строку слева на 1 символ после каждого прохода по лупу(я уже не помню, почему такое извращение мне в голове осело ). То есть, переменную либо прийдется назначать каждый раз при проходе цикла(но тогда она не может быть const) либо оставить всё как есть. // Если я все верно понял из того, что Вы описали.

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

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

Спасибо еще раз всем за помощь!

[NickLion]

BOSS
Её нужно объявлять внутри цикла и тогда ничто не будет мешать ей быть const: внутри одной итерации она не меняется, а на следующей итерации не считается, так как область действия закончилась, переменная уничтожена и создана заново.

[Tema]

BOSS
Её нужно объявлять внутри цикла и тогда ничто не будет мешать ей быть const: внутри одной итерации она не меняется, а на следующей итерации не считается, так как область действия закончилась, переменная уничтожена и создана заново.

Опять недостаток знаний, я думал область видимости - это функция, не значл, что цикл - это отдельная область видимости.
Спасибо еще раз!

[Tema]

Доброго вечера!

Пробовал реализовать кастомные Операнды с помощью отдельных классов(абстрактный+два ребенка для int и string), натолкнулся на кучу преград, не буду сейчас вдаваться в подробности, но суть в том, что решил пойти немного иначе.
Воспользовался шаблонами классов.
Вот код: http://pastebin.com/PrqAmtnu
visual studio собрал на легке, а g++(5.2) ругается на перегрузку операторов:
строка 40 и 47

Код: Выделить всё

Operand<T> operator*(Operand<T> const &b) const

и

Код: Выделить всё

Operand<std::string> operator*(Operand<std::string> const &b) const

пытался выгуглить причину. Судя по всему, компилятор подразумевает, что если T == std::string - то будет двойное определение для этого оператора.
Вопрос: как можно обыграть эту ситуацию?
Проблема в том, что я должен описать для специализированного темплейта(string), что делать если будем умножать на число. Но ведь может быть не только "sting * int", но и "int * string". Именно поэтому я добавил в основной темплейт перегрузку для оператора * если вторым аргументом будет string.

И еще + перегружал потому, что если будет "int + string" то надо, чтобы вернуло не int(это будет T в описания темплейта) ,а string.

PS: а где правильнее хранить темплейты? Как я понял, проблемно их разделять на два файла(как классы), поэтому либо хранить в cpp, либо в h, либо в отдельном хедере?

Спасибо заранее.

[NickLion]

1. Шаблоны тут не дадут какой-то пользы.
2. Просто нужно сначала специализацию описать, а потом общее описание. Ну, и методы специализации, которые работают с общим классом вынести отдельно и поместить ниже. Вот так (оператор T + std::string я закомментировал, не понял что он должен делать, если нужен — вынесите по подобию).

[Tema]

Спасибо за помощь. Теперь разобрался что к чему.

По поводу пункта 1, я использовал темплейты, чтобы как-то структурировать(чтоли) код. Чтобы не описывать правила операций для строки внутри метода, который считать будет.
Вот что получилось(этот метод встроен в метод, который преобразовывает ОПЗ в результат) - метод, который производит операцию над двумя операндами:
http://pastebin.com/zpXfRxb2
Получилось конечно хуже чем я ожидал, т.к. если переменная создана внутри if (){} то ее не будет видно ниже по коду(это я уяснил из предыдущего поста о константе внутри цикла). То есть пришлось не только создавать переменные в условии, но и там же производить операции с ними. Из-за этого повысилась лохматостьвложенность.

Реализовать с классами не получилось по нескольким причинам:
1. Не получилось описать операторы в абстрактном классе. Ошибка была с тем, что оператор возвращает объект, а нельзя возвращать абстрактного класса объект. Возвращал ссылку на объект, компилятор вроде бы скушал. Но потом, при реализации не получалось и ссылку возвращать(не помню ошибку, но код есть, могу вернуться к реализации через классы, если это будет лучше).
2. Создавал умный указатель на абстрактный класс, чтобы можно было в него впихнуть и stringOperand и IntOperand. В итоге валилось на том, что у абстрактного класса не описаны операторы(из-за пункта 1).

У меня масса проблем и с реализацией и с проектированием решения.. Читаю книгу "A tour of C++", но практические проблемы, которые передо мной встают опережают прочтение о них в книгах(например только вчера прочитал, что использовать using в заголовочных файлах - это плохо. Это первый комментарий в этой теме был...).

А как бы Вы решили сию проблему, если не шаблонами? Попробовать еще один подход к реализации через классы?

Спасибо

[NickLion]

Лично я сделал бы просто класс с полем типа и значениями для каждого из типов. Вообще — это классическая реализация типа VARIANT, т.е. типа, который может хранить разные значения и производить разные операции над разными типами.

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

С виртаульными можно сделать, но как Вы сами увидели, проблема есть с ворзвращаемым значением, приходится возвращать указатель. Чтобы остались операции +-*/ можно использовать подход, т.н. pimpl — pointer to implementation, т.е. реализовать класс, который будет хранить указатель на объект (указатель на абстрактный класс), который уже непосредственно будет поддерживать операции. А обёртка будет обычным классом и всё будет хорошо. Но, как по мне, в данной задаче это немного из пушки по воробьям.

[NickLion]

Сделал на коленке пример, если хотите, могу кинуть, если интереснее самому разобраться, то не буду кидать :)

[Tema]

Сделал на коленке пример, если хотите, могу кинуть, если интереснее самому разобраться, то не буду кидать

Я еще сам попробую. Я на своём опыте могу заявить, что лучше один раз написать, чем 10 раз прочитать
А как закончу, попрошу Вас выслать, чтобы проанализировать свой вариант. Читая чужой код можно тоже много почерпнуть.
Нашел пару статей про имплементацию типа Вариант на с++, сейчас заценим-с.

Спасибо!

PS: нашел еще вот такое - http://www.boost.org/doc/libs/1_59_0/doc/html/variant.html
С одной стороны - круто научиться пользоваться чужим, ведь в реальности, чаще всего не пишешь всё сам. К тому же я читал, что вроде бы как надо иметь навыки работы с бустом(хотя это я читал такое до с++11, может уже и не везде нужно..). Попробую подключить Буст (в целях обучения) и попробую написать свой вариант.

[Tema]

Доброй ночи.

Написал класс Variant:
Variant.h
Variant.cpp

Надо добавить обработку случаев, когда приходит невалидный сетап(аля str / str), а так вроде всё ок. Места заняло гораздо меньше, чем темплейты и работает нормально.
Завтра еще на свежую голову перепроверю всё, отрефакторю если что.

Теперь хотелось бы увидеть Ваш вариант

Спасибо!

[NickLion]

boost всё равно полезен, просто многое из него попало в новый стандарт.

Вот мой наколеночный вариант.
variant.h
variant.cpp
Естественно, для привидения всего этого в нормальный вид следует добавить возможность присваивать значение (а не только инициализировать), добавить приведение типов, у Вас есть getInt, getString, в принципе можно их оставить, но я бы добавил оператор приведения типа:

Код: Выделить всё

class Variant {
...
    operator int () const;
...
};

Variant::operator int() const
{
    if (type == Type::Int)
        return ivalue;
    return 0; // or throw an exception
}

[Tema]

NickLion,

Мне понравилась идея с оператором приведения. Думаю, так будет более изящно
И еще возьму от Вас конструктор с указанием типа, думаю, так будет более понятно, что делает класс. Ну и еще уберу getType, т.к. он используется только внутри класса, незачем его в интерфейс включать(вчера прочитал про интерфейс(public) и имплементацию(private) так-то ) getInt, getString туда же. Возьму за основу идею с вашим toString, чтобы выводить результат за пределами класса.

Спасибо за помощь.

[NickLion]

BOSS
В принципе, getType имеет смысл оставить, если данный тип использовать в произвольном коде, то иногда полезно узнать, а данные какого типа хранятся в перменной.

[Tema]

nevermind

[Tema]

Добрый вечер,
Подскажите, пожалуйста, best practise с typedef и misc functions(самописные функции, которые расширяют функционал, но не имеют отношения к конкретным классам, типа isDigit из моего примера, которая работает со string, а не char).
У меня в одном из классов (в заголовочном файле) прописан typedef, но он недоступен для других классов, которые работают с объектами такого типа, но не импортируют этот заголовочный файл напрямую или через другие заголовочные файлы.

Есть идея вынести все полезняхи (typedef, утили функции по типу привычный replace для строки и тд и тп) в отдельный класс(+заголовочный файл).
Это самое правильное решение?

[Bizdelnick]

Есть идея вынести все полезняхи (typedef, утили функции по типу привычный replace для строки и тд и тп) в отдельный класс(+заголовочный файл).
Это самое правильное решение?

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

[Tema]

Есть идея вынести все полезняхи (typedef, утили функции по типу привычный replace для строки и тд и тп) в отдельный класс(+заголовочный файл).
Это самое правильное решение?

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

Все верно, незачем. Я имел в виду source файл, а сказал класс... Про неймспейсы читал буквально пару дней назад в книге.
Спасибо за совет, пойду попрактикуюсь)

[Tema]

Добрый вечер.

Настало время расширять горизонты, теперь хотелось бы прикрутить к своей программе многопоточность.
С оной имел дело в Python, но там в разы проще(внезапно), во первых там уже есть Queue, во-вторых там стандартные контейнеры thread-safe. Хотя, я читал, что в некоторой мере и в С++ стандартные контейнеры тоже тред-сейф: читать можно одновременно, но при записи запрещается чтение и запись в параллели.

Флоу программы(кратко):
1. В программе хранятся исходные данные в неком векторе(получаем из user input или файла).
2. Сейчас программа циклом проходится по вектору и по очереди обсчитывает что там написано в каждой ячейке.(а там пример типа "7+3-20")
3. После того как получен результат - помещаем его в переменную объекта, указатель на который хранится в другом векторе.

Вот два вектора:

Код: Выделить всё

typedef std::vector<std::string> StringVector;
typedef std::vector<usrlib::StringVector> StringVector2D;

typedef std::vector<std::shared_ptr<Cell>> CellVector;
typedef std::vector<usrlib::CellVector> CellVector2D;

Что думаю я: надо делать очередь. В которую запихнуть все ячейки, которые необходимо посчитать(можно даже отдельным потоком это сделать). Затем организовать несколько тредов, которые будут выгребать по одному элементу и запускать с этим аргументом функцию обработки. Затем записывать результат в переменную объекта типа Cell в векторе(typedef выше).

Подскажите, пожалуйста, как лучше сделать? вопрос не по коду, а по логике, проектированию.

Спасибо заранее!

PS: не могу определиться, что использовать лучше pthread или thread. насколько я понял, лучше разобраться с pthread, с точки зрения обучения(более низкоуровневое + более старое+кросплатформенное). Та и почему-то мне кажется(поправьте плз если ошибаюсь), что чаще всего в работе сталкиваются именно с pthread... Хотя Страуструп в книге C++ Programming Language пишет о thread. И в интервью он его расхваливал, ладно, уговорил, буду thread использовать)

PSPS: читаю книгу, теперь понимаю, что тема слишком обширна, чтобы вместить в пост на форуме. Если вопросы останутся, я отпишусь с просьбой помочь.