Lazy Оценка выражения, хранящегося в векторе

Question

Для простоты я собираюсь опорочить весь вопрос.

Я работаю над булевой арифметикой, используя только операторы OR и AND (пока).

Мои булевские выражения хранятся в векторе, чередующем переменную и оператор (что-то вроде [a, ||, b] для «a OR b»).

Я хотел бы знать, если это возможно цепь обратно мой вектор, как если бы я написал:

std::vector<xxx> v = {true, &&, (, false, ||, true,)}; 
// result = true && (false || true) = true 
bool result = vector[0] vector[1] vector[2] vector[3] vector[4] vector[5] vector[6]; 

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

Прошу прощения, если этот вопрос уже задан и ответил, я просто не знаю, какие ключевые слова использовать в моих поисках!

Спасибо заранее, даже просто подсказкой бы неплохо :)

Answer 1

Как AxelOmega сказал - вы можете использовать boost::spirit. Грамматика довольно проста:

#include <boost/spirit/include/qi.hpp> 
#include <boost/spirit/include/qi_bool.hpp> 
#include <boost/spirit/include/phoenix.hpp> 

namespace qi = boost::spirit::qi; 

template <class Iterator> 
struct bool_grammar : qi::grammar<Iterator, bool(), qi::space_type> { 
     qi::rule<Iterator, bool(), qi::space_type> rGroup, rBool, rName, rOr, rAnd; 

     bool_grammar() : bool_grammar::base_type(rOr) { 
       rGroup = '(' >> rOr >> ')'; 
       rBool = qi::bool_ | rGroup; 
       rAnd = rBool[qi::_val = qi::_1] >> 
          *('&' >> rBool[qi::_val = qi::_val && qi::_1]); 
       rOr  = rAnd[qi::_val = qi::_1] >> 
          *('|' >> rAnd[qi::_val = qi::_val || qi::_1]); 
     } 
}; 

вам также понадобится функция для вызова анализатора и проверить результаты

bool parse(const std::string& value) { 
     bool_grammar<std::string::const_iterator> g; 
     std::string::const_iterator it = value.begin(); 
     std::string::const_iterator end = value.end(); 

     bool s; 
     if (qi::phrase_parse(it, end, g, qi::space, s) == false || it != end) { 
       // error 
     } 

     return s; 
} 

и теперь просто объединить vector в единый string и использовать функцию синтаксического анализа:

parse("(true | false) & true | false") ; 

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

Answer 2

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

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

Так св двухэтапный процесс

1: Построить дерево

2: Рекурсивный оценить дерево выражения

Если вы хотите представить в виде графика, смотреть в boost::graph

Answer 3

Во-первых, вы не можете хранить сырые операторы C++ или синтаксические элементы в vector от любого типа, поэтому (, * и так далее.

Вы можете хранить их как литералы, хотя:

std::vector<std::string> expression = { "2", "+", "3" }; 

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

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

Answer 4

Вы можете использовать шаблоны выражений, чтобы сделать это. Некоторые из ваших булевых литералов должны быть похожими на bool_(true), чтобы создать пользовательский объект с соответствующими операторами, но, кроме того, он будет, как если бы вы действительно использовали C++.

Конечно, проще просто использовать лямбда или написать функцию для этого, если вам не нужно интроспекцию/изменение дерева во время выполнения или что-то в этом роде.

Answer 5

Вы можете сгенерировать файл с исходным кодом C++, скомпилировать его и запустить. Что-то вроде этого:

std::vector<xxx> v = {true, *, (, false, +, true,)}; 
std::ofstream src("temp.cpp"); 
src << 
    "#include <iostream>\n" 
    "int main() {\n" 
    "bool result = "; 
for (auto i: v) 
    src << i << ' '; 
src << 
    ";\n" 
    "std::cout << result;\n" 
    "}\n"; 
src.close(); 
system("g++ temp.cpp -o temp"); 
system("temp"); 

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