具有用户定义函数的 C++ 数学解析器

Question

我想实现一个带有用户定义函数的数学解析器。有几个问题需要解决。例如，int eg(int a,int b){return a+b;} 是我要添加到解析器的函数。第一：如何把所有的函数都存储到一个容器中？ std::map<std::string,boost::any> func_map 可能是一个选择（由 func_map["eg"]=eg）。但是，在这种映射中调用函数非常困难，因为我必须使用 any_cast<T> 从boost::any.

的包装

第二：如何处理重载的函数？确实，我通过typeid的方法可以区分重载函数，但离真正的实现还差得很远

解析表达式不是什么难的技能，最难的部分已经在上面描述了。

muparserx 为这个问题提供了一个有趣的解决方案，但我正在寻找另一种方法。

我不熟悉 lambda 表达式，但它可能是一种可以接受的方式。

更新：我需要这样的东西：

int eg(int a,int b){ return a+b;}
int eg(int a,int b, string c){return a+b+c.length();}
double eh(string a){return length.size()/double(2);}
int main(){
    multimap<string,PACKED_FUNC> func_map;
    func_map.insert(make_pair("eg",pack_function<int,int>(eg));
    func_map.insert(make_pair("eg",pack_function<int,int,string>(eg));
    func_map.insert(make_pair("eh",pack_function<string>(eh));
    auto p1=make_tuple(1,2);
    int result1=apply("eg",PACK_TUPLE(p1));//result1=3
    auto p2=tuple_cat(p1,make_tuple("test"));
    int result2=apply("eg",PACK_TUPLE(p2));//result2=7
    auto p3=make_tuple("testagain");
    double result3=apply("eh",PACK_TUPLE(p3));//result3=4.5
    return 0;
}

Answer 1

How to store all the functions into a container?

要将它们存储在某个容器中，它们必须是同一类型。 std::function 包装器是一个不错的选择，因为它甚至允许您使用有状态的函数对象。由于您可能不希望所有函数都采用相同数量的参数，因此您需要 "extract" 来自静态主机类型系统的函数的数量。一个简单的解决方案是使用接受 std::vector:

的函数

// Arguments type to the function "interface"
using Arguments = std::vector<int> const &;
// the interface
using Function = std::function<int (Arguments)>;

但是您不希望您的用户编写必须手动解压缩参数的函数，因此将其自动化是明智的。

// Base case of packing a function.
// If it's taking a vector and no more
// arguments, then there's nothing left to
// pack.
template<
  std::size_t N,
  typename Fn>
Function pack(Fn && fn) {
 return
  [fn = std::forward<decltype(fn)>(fn)]
  (Arguments arguments)
  {
   if (N != arguments.size()) {
    throw
      std::string{"wrong number of arguments, expected "} +
      std::to_string(N) +
      std::string{" but got "} +
      std::to_string(arguments.size());
   }
   return fn(arguments);
  };
}

上面的代码处理了简单的情况：一个已经接受向量的函数。对于所有其他函数，它们需要被包装并打包到一个新创建的函数中。一次做这个论点使这相对容易：

// pack a function to a function that takes
// it's arguments from a vector, one argument after
// the other.
template<
  std::size_t N,
  typename Arg,
  typename... Args,
  typename Fn>
Function pack(Fn && fn) {
 return pack<N+1, Args...>(
  [fn = std::forward<decltype(fn)>(fn)]
  (Arguments arguments, Args const &... args)
  {
   return fn(
     arguments,
     arguments[N],
     args...);
  });
}

以上仅适用于已经采用向量的（特殊）函数。对于普通函数，我们需要一个函数将它们变成这样的特殊函数：

// transform a function into one that takes its
// arguments from a vector
template<
  typename... Args,
  typename Fn>
Function pack_function(Fn && fn) {
 return pack<0, Args...>(
  [fn = std::forward<decltype(fn)>(fn)]
  (Arguments arguments, Args const &... args)
  {
   return fn(args...);
  });
}

使用它，您可以将任何函数打包为相同类型：

Function fn =
  pack_function<int, int>([] (auto lhs, auto rhs) {return lhs - rhs;});

然后您可以将它们放在地图中，并使用从某些输入解析的向量来调用它们：

int main(int, char**) {
 std::map<std::string, Function> operations;
 operations ["add"] = pack_function<int, int>(add);
 operations ["sub"] = pack_function<int, int>(
   [](auto lhs, auto rhs) { return lhs - rhs;});
 operations ["sum"] = [] (auto summands) {
   int result = 0;
   for (auto e : summands) {
    result += e;
   }
   return result;
  };
 std::string line;
 while (std::getline(std::cin, line)) {
  std::istringstream command{line};
  std::string operation;
  command >> operation;
  std::vector<int> arguments {
    std::istream_iterator<int>{command},
    std::istream_iterator<int>{} };
  auto function = operations.find(operation);
  if (function != operations.end ()) {
   std::cout << line << " = ";
   try {
    std::cout << function->second(arguments);
   } catch (std::string const & error) {
    std::cout << error;
   }
   std::cout << std::endl;
  }
 }
 return 0;
}

一个live demo of the above code is here.

How to handle the overloaded function? It's true that I can distinguish the overloaded functions by the method of typeid, but it's far from a real implementation.

如您所见，如果将相关信息打包到函数中，则不需要。顺便说一句，typeid 不应该用于诊断以外的任何用途，因为它不能保证 return 具有不同类型的不同字符串。

现在，最后，要处理不仅采用不同数量的参数，而且参数类型也不同的函数，您需要将这些类型统一为一个。这通常称为 "sum type"，在 Haskell:

等语言中很容易实现

data Sum = IVal Int | SVal String
-- A value of type Sum is either an Int or a String

在 C++ 中这更难实现，但简单的草图可能如下所示：

struct Base {
  virtual ~Base() = 0;
};
inline Base::~Base() {}

template<typename Target>
struct Storage : public Base {
  Target value;
};

struct Any {
  std::unique_ptr<Base const> value;
  template<typename Target>
  Target const & as(void) const {
    return
      dynamic_cast<Storage<Target> const &>(*value).value;
   }
};

template<typename Target>
auto make_any(Target && value) {
  return Any{std::make_unique<Storage<Target>>(value)};
}

但这只是一个粗略的草图，因为 boost::any 应该非常适合这种情况。请注意，上面的 boost::any 并不完全像真正的总和类型（它们可以是任何类型，而不仅仅是给定选择中的一种），但这对您的情况无关紧要。

我希望这能让你开始:)

由于您在添加多类型支持时遇到问题，我对上面的草图进行了一些扩展并使其正常工作。不过，该代码远未准备好生产：我正在四处乱扔字符串，不要跟我谈论完美转发：D

对上述 Any class 的主要更改是使用共享指针而不是唯一指针。这只是因为它使我免于编写复制和移动构造函数以及赋值运算符。

除此之外，我添加了一个成员函数，以便能够将 Any 值打印到流中，并添加了相应的运算符：

struct Base {
  virtual ~Base() = 0;
  virtual void print_to(std::ostream &) const = 0;
};
inline Base::~Base() {}

template<typename Target>
struct Storage : public Base {
  Target value;
  Storage (Target t) // screw perfect forwarding :D
   : value(std::forward<Target>(t)) {}

  void print_to(std::ostream & stream) const {
    stream << value;
  }
};

struct Any {
  std::shared_ptr<Base const> value;

  template<typename Target>
  Target const & as(void) const {
    return
      dynamic_cast<Storage<Target> const &>(*value).value;
   }
   template<typename T>
   operator T const &(void) const {
     return as<T>();
  }
   friend std::ostream & operator<<(std::ostream& stream, Any const & thing) {
     thing.value->print_to(stream);
     return stream;
   }
};

template<typename Target>
Any make_any(Target && value) {
  return Any{std::make_shared<Storage<typename std::remove_reference<Target>::type> const>(std::forward<Target>(value))};
}

我还编写了一个小的 "parsing" 函数，它展示了如何将原始文字转换为包含（在本例中）整数、双精度或字符串值的 Any 值：

Any parse_literal(std::string const & literal) {
  try {
    std::size_t next;
    auto integer = std::stoi(literal, & next);
    if (next == literal.size()) {
      return make_any (integer);
    }
    auto floating = std::stod(literal, & next);
    if (next == literal. size()) {
      return make_any (floating);
    }
  } catch (std::invalid_argument const &) {}
  // not very sensible, string literals should better be
  // enclosed in some form of quotes, but that's the
  // job of the parser
  return make_any<std:: string> (std::string{literal});
}

std::istream & operator>>(std::istream & stream, Any & thing) {
  std::string raw;
  if (stream >> raw) {
    thing = parse_literal (raw);
  }
  return stream;
}

通过同时提供 operator>>，可以继续使用 istream_iterator 进行输入。

包装函数（或更准确地说，由它们编辑的函数 return）也进行了修改：当将一个元素从参数向量传递到下一个函数时，从 Any 到执行各自的参数类型。这也可能会失败，在这种情况下会捕获 std::bad_cast 并重新抛出一条信息性消息。最里面的函数（在 pack_function 中创建的 lambda）将其结果包装到 make_any 调用中。

add 5 4 = 9
sub 3 2 = 1
add 1 2 3 = wrong number of arguments, expected 2 but got 3
add 4 = wrong number of arguments, expected 2 but got 1
sum 1 2 3 4 = 10
sum = 0
sub 3 1.5 = argument 1 has wrong type 
addf 3 3.4 = argument 0 has wrong type 
addf 3.0 3.4 = 6.4
hi Pete = Hello Pete, how are you?

An example similar to the previous one can be found here。我需要补充一点，这个 Any 类型不支持隐式类型转换，所以当你有一个 Any 和一个 int 存储时，你不能将它传递给一个需要 [= 的函数39=]。虽然这可以实现（通过手动提供大量转换规则）。

但我也看到了您的更新，所以我使用了该代码并对 run with my presented solution:

进行了必要的修改

Any apply (multimap<string, Function> const & map, string const & name, Arguments arguments) {
 auto range = map.equal_range(name);
 for (auto function = range.first;
      function != range.second;
      ++function) {
  try {
   return (function->second)(arguments);
  } catch (string const &) {}
 }
 throw string {" no such function "};
}


int eg(int a,int b){ return a+b;}
int eg(int a,int b, string c){return a+b+c.length();}
double eh(string a){return a.size()/double(2);}
int main(){
 multimap<string, Function> func_map;
 func_map.insert(make_pair(
   "eg",pack_function<int,int>(
     static_cast<int(*)(int, int)>(&eg))));
 func_map.insert(make_pair(
   "eg",pack_function<int,int,string>(
     static_cast<int (*)(int, int, string)>(&eg))));
 func_map.insert(make_pair(
   "eh",pack_function<string>(eh)));

 // auto p1=make_tuple(1,2);
 // if you want tuples, just write a
 // function to covert them to a vector
 // of Any.
 Arguments p1 =
   {make_any (1), make_any (2)};
 int result1 =
   apply(func_map, "eg", p1).as<int>();

 vector<Any> p2{p1};
 p2.push_back(make_any<string> ("test"));
 int result2 =
   apply(func_map, "eg", p2).as<int>();


 Arguments p3 = {make_any<string>("testagain")};
 double result3 =
   apply(func_map, "eh", p3).as<double>();


 cout << result1 << endl;
 cout << result2 << endl;
 cout << result3 << endl;
 return 0;
}

它不使用元组，但您可以编写一个（模板递归）函数来访问元组的每个元素，将其包装成一个 Any 并将其打包到一个向量中。

此外，我不确定为什么在初始化结果变量时，Any 的隐式转换不起作用。

嗯，将其转换为使用 boost::any 应该不难。首先，make_any 只使用 boost::any 的构造函数：

template<typename T>
boost::any make_any(T&& value) {
  return boost::any{std::forward<T>(value)};
}

在 pack 函数中，我猜唯一需要更改的是参数向量中当前元素的正确类型的 "extraction"。目前这就像 arguments.at(N) 一样简单，依赖于到所需类型的隐式转换。由于 boost::any 不支持隐式转换，您需要使用 boost::any_cast 来获取基础值：

template<
  std::size_t N,
  typename Arg,
  typename... Args,
  typename Fn>
Function pack(Fn && fn) {
 return pack<N+1, Args...>(
  [fn = std::forward<decltype(fn)>(fn)]
  (Arguments arguments, Args const &... args)
  {
   try {
    return fn(
      arguments,
      boost::any_cast<Arg>(arguments.at(N)),
      args...);
   } catch (boost::bad_any_cast const &) { // throws different type of exception
    throw std::string{"argument "} + std::to_string (N) +
      std::string{" has wrong type "};
   }
  });
}

当然，如果您像您提供的示例中那样使用它，您还需要使用 boost::any_cast 来访问结果值。

这应该（理论上）这样做，最终你需要在 boost::any_cast 调用的模板参数中添加一些 std::remove_reference "magic"，但我怀疑这是必要的. （typename std::remove_reference<T>::type 而不仅仅是 T）

虽然我目前无法测试以上任何一项。

具有用户定义函数的 C++ 数学解析器

C++ Math Parser with user-defined function

c++

parsing

function-pointers