如何从字符串解析公式? [英] How to parse a formula from a string?

问题描述

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

For example, I have string ((data1 + data2) ^ data3) / data4 and I want my little program to get this string and do something like this:

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;
}

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

Is there such a parser in the standard library? If not, how would I make such a parser myself?

推荐答案

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

There is nothing ready-made in the standard library for parsing expressions, no. However, it's a nice exercise to roll a parser/evaluator yourself. I don't want to spoil the fun, but here are some thoughts:

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

The idea is to first parse the input string into some sort of data structure which represents the expression (usually some sort of tree structure) and then 'evaluate' that data structure with some given variable bindings.

数据结构可能是一个标记联合，如下所示:

The data structure might be a tagged union, something like this:

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;
};

对于解析部分，我建议阅读递归下降"解析器，该部分很容易理解和手写.目标是定义一个函数

For the parsing part, I suggest to read up on 'recursive descent' parsers, which area quite easy to understand and write by hand. The goal is to define a function

Value *parse( const char *s );

返回给定字符串的表示.

which returns a representation for the given string.

求值部分非常简单，适合递归.目标是定义一个函数

The evaluation part is quite straightforward and lends itself to recursion. The goal is to define a function

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

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

...where ??? would be some type appropriate for holding variable bindings (e.g. a string to int mapping). Depending on the 'type' of the given value, it will perform the arithmetic operation, e.g.:

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 );
    ...

这篇关于如何从字符串解析公式?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！