一个博客

随便写写

0%

算式的链表实现

发表于 更新于

既然链表已经写好了，那就需要使用一下。从以前开始我就有一个想法，把数学的算式用一个结构保存下来，并且能够对它进行一些操作，有点像以前写的什么中缀表达式后缀表达式的，但是不局限于求值，或许还能有其他的用处。

首先分析一下算式的结构，我们可以很明显的发现算式是一个链式的结构，所以可以用链表模拟。一个算式里面每一个值之间的连接方式无疑就是加减乘除，但是这4种运算符有两种优先级，乘除优先于加减，然后减可以当作加上它的相反数，除可以变成乘上负一次方或者乘上一个分数，所以实际需要考虑的就是加和乘。

因为计算优先级的问题，如果在一个链表里面同时包含加和乘，那会让计算变得很复杂所以我的想法是加法和乘法分别用两个链表来表示，例如$1\times 2+3\times 4$，我们可以写成3个链表，第一个链表只保存加法运算，有两个项，两个项分别是一个链表，只保存乘法运算。

数学对象的实现

因为以后是想写成像Markdown或者latex那样的数学公式的，所以除了基本运算以外，后面还会有分数和次方之类的东西，所以我们先为数学对象定义一个基类，它的成员变量暂时为一个函数指针output，即输出这个数学对象，往后不管是常数还是根号，都继承自这个基类，代码如下：

1
2
3
4
5
6
typedef struct _MathObject _MathObject;
typedef _MathObject* MathObject;
struct _MathObject
{
    void (*output) (MathObject obj);
};

嗯……写得够丑了但是感觉这样MathObject更常用，然后再举例常数怎么写，代码如下：

1
2
3
4
5
typedef struct
{
    _MathObject m;
    int value;
} ConstValue;

第一个变量为_MathObject即为继承自_MathObject，value的类型其实应该用double，但是这里为了方便，还是用了int，然后我们需要从输入的字符串中构建数学对象，然后这个应该是叫什么工厂函数吧，用一个函数来调用其他的对象的构造函数，现在因为只有常数一个类型，所以肯定是调用常数的构造函数，

1
2
3
4
char *MathObjectBuildFromstr(MathObject *obj, char *str)
{
    return ConstValueBuildFromstr(obj, str);
}

返回值为处理了数学对象之后的字符串，我想象中的构建流程是：一开始对字符串调用算式的构造函数，算式的构造函数再对字符串的每个项调用项的构造函数，项再对字符串调用数学对象的构造函数，每个构造函数都会返回它们处理过之后的字符串，直到字符串处理完。

常数构造函数的操作就是从字符串当前位置读取数字，直到遇到一个非数字字符时返回，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char *ConstValueBuildFromstr(MathObject *obj, char *str)
{
    char *p = str;
    int value = 0;
    ConstValue c;
    while(*p)
    {
        if(!isdigit(*p))
        {
            break;
            
        }
        value = 10 * value -'0' + *p;
        p++;
    }
    c.m.output = ConstValueOutput;
    c.value = value;
    *obj = (MathObject)malloc(sizeof(ConstValue));
    memcpy(*obj, &c, sizeof(ConstValue));
    return p;
}

输出函数过于简单，就不贴代码了。

算式的形式

前面也说了，算式和项都是链表的形式，所以这里稍微懒一下：

1
2
typedef LinkList Suanshi;
typedef LinkList Team;

创建函数

创建函数方面，因为项会有正负号，所以在创建一个TeamInfo，来保存符号，并且在创建的时候指定符号，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct
{
    char operate;
} TeamInfo;

void TeamCreate(Suanshi *t, char opt)
{
    LinkListCreate(t, sizeof(MathObject));
    TeamInfo I;
    I.operate = opt;
    LinkListSetHeaderInfo(*t, &I, sizeof(I));
}

算式的创建函数比较简单，就是设置size为sizeof(Team)就行了，没有什么好说的。记得再为获取Team的符号写个函数，这里不贴代码了。

构造函数

前面也说了，我们要解析字符串，构造算式的时候构造项，然后在构造项的时候再构造数学对象，主要是靠数学对象的构造函数来处理字符串，

算式的构造函数

首先从构造算式开始，算式的构造函数只需要调用项的构造函数来构造项，并且按照顺序保存项，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SuanshiBuildFromstr(Suanshi s, char *str)
{
    char *p = str;
    Team t;
    TeamCreate(&t, *p == '-' ? '-' : 0);
    p = TeamBuildFromstr(t, p);
    LinkListInsertTail(s, &t);
    while(*p)
    {
        if(isblank(*p))
        {
            p++;
            continue;
        }
        TeamCreate(&t, *p);
        p++;
        p = TeamBuildFromstr(t, p);
        LinkListInsertTail(s, &t);
    }
}

首先第一个项前面只需要判段是不是负号，如果不是那就不需要符号。往后就是一直构建项，记得剔除空白字符，这里假设项和项之间是直接连接（起码我想不出还会有什么其他情况），所以就不判断p的是不是正负号，直接以当前的p作为符号。

项的构造函数

项的构造是调用数学对象的构造函数，按照顺序构造数学对象，并且保存。依然要注意剔除空白字符，当遇到正负号时就说明当前项构造完了，就应该返回去算式构造函数，构造下一个项，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
char *TeamBuildFromstr(Team t, char *str)
{
    char *p = str;
    MathObject obj;
    while(*p)
    {
        if(isblank(*p))
        {
            p++;
            continue;
        }
        if(*p == '+'||*p == '-')
        {
            break;
        }
        if(*p == '*')
        {
            p++;
        }
        p = MathObjectBuildFromstr(&obj, p);
        LinkListInsertTail(t, &obj);
    }
    return p;
}

输出函数

既然构造也是链式的，那输出也应该是链式的，按照构造的顺序来输出，首先是算式的输出函数依次调用每个项的输出函数，然后在每个项再调用数学对象的输出函数。

算式的输出函数

算式的输出比较简单，为了方便看，在最后用一个puts(“”)来换行，注意我们的节点保存的是指向每个项的指针的指针，所以输出的时候记得转换一下类型，代码如下：

1
2
3
4
5
6
7
8
void SuanshiOutput(Suanshi s)
{
    LinkListFor(p,LinkListGetFront(s))
    {
        TeamOutput(*(Team*)NodeGetData(p));
    }
    puts("");
}

项的输出函数

项的输出要注意的就是，项的最前面是正负号，不是乘号，所以第一个数学对象单独输出，并输出符号，然后在后面每一个数学对象前面加上乘号，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void TeamOutput(Team t)
{
    Node *p = LinkListGetFront(t);
    MathObject obj = *(MathObject*)NodeGetData(p);
    putchar(TeamGetOperate(t));
    obj->output(obj);
    LinkListFor(q, LinkListGetFront(p))
    {
        printf("*");
        obj = *(MathObject*)NodeGetData(q);
        obj->output(obj);
    }
}

实际使用测试

现在算式的大概形式已经完成了，现在来用一段简单的代码来测试一下：

1
2
3
4
5
6
7
8
9
10
#include "Suanshi.h"
int main()
{
    Suanshi s;
    char str[] = "1*2+3*4";
    SuanshiCreate(&s);
    SuanshiBuildFromstr(s,str);
    SuanshiOutput(s);
    return 0;
}

这里不出意外，输出会和我们的str一样，但是这个是已经被我们结构化保存在算式和项里面了，可以很方便的进行操作。

结束

到这里大概框架已经完成了，之后可以考虑一下增加更多的数学对象，还有解析和输出Markdown的数学公式，这估计会是个大工程，所以本文就先到此结束。