c - 如何从字符串中解析公式？

Question

例如，我有字符串 ((data1 + data2) ^ data3)/data4 我希望我的小程序获取该字符串并执行如下操作:

int main(int argc, char **argv) {

    double data1 = 1.0;
    double data2 = 2.0;
    double data3 = 3.0;
    double data4 = 4.0;

    double result = parse_formula("((data1 + data2) ^ data3) / data4");

    printf("Result is %d\n", result);
    return 0;
}

标准库中有这样的解析器吗？如果没有，我自己如何制作这样的解析器？

Answer 1

标准库中没有现成的用于解析表达式的东西，没有。然而，自己构建一个解析器/评估器是一个很好的练习。我不想破坏乐趣，但这里有一些想法:

这个想法是首先将输入字符串解析为某种表示表达式的数据结构(通常是某种树结构)，然后使用一些给定的变量绑定(bind)“评估”该数据结构。

数据结构可能是tagged union ，像这样:

enum ValueType {
 ConstantValue, VariableValue, Addition, Division
};

struct Value {
  enum ValueType type;

  /* The 'representation' of the value. */
  union {
     int constantValue;
     const char *variableValue;
     struct {
       struct Value *summand1;
       struct Value *summand2;
     } additionValue;
     struct {
       struct Value *dividend;
       struct Value *divisor;
     } divisionValue;
  } repr;
};

对于解析部分，我建议阅读“递归下降”解析器，该区域非常容易理解和手动编写。目标是定义一个函数

Value *parse( const char *s );

返回给定字符串的表示形式。

评估部分非常简单，适合递归。目标是定义一个函数

int eval( const Value *v, ??? bindings );

...其中 ??? 是适合保存变量绑定(bind)的某种类型(例如，字符串到 int 映射)。根据给定值的“类型”，它将执行算术运算，例如:

int eval( const Value *v, ??? bindings ) {
  switch ( v->type ) {
    case ConstantValue:
      return v->repr.constantValue;
    case Addition:
      return eval( v->repr.additionValue.summand1 ) + eval( v->repr.additionValue.summand2 );
    ...