偶写的一个含括弧的任意精度四则运算的详细解释

上次我写了一个含括弧的任意精度数值四则运算的程序,由于没有注释,大家理解起来感觉难度很大,很多同学都要求我加上一些注释.

为了满足大家的要求,我特地写了一份详细的报告,把程序的来龙去脉深入的剖析了一番,希望对大家的理解有所帮助~~

如果大家发现有什么问题或者是有什么好的建议,不妨和我联系,我的联系方式是:

QQ:37170732  邮箱:owenstone@sina.com.cn

含括弧的任意精度数值四则运算

一.程序功能介绍：

1．本程序主要的功能是利用链表将用户输入的任意精度中缀表达式转换成后缀表达式，为了以便于区分数据和操作符，数据间用下划线将它们区分开来，并且计算出此表达式的值。

2．需要注意的是：此程序所叙述的四则运算是狭义的，并没有显式的要求用户以中括弧“[]”或者是大括弧“{}”进行输入,因为这样会大大的加大程序的代码量，为了简便起见，同时又为了实现四则混合运算的功能，只要用户将含有中括弧或者是大括弧的地方均以小括弧表示即可。

二．程序实现简述：

一般说来，人们的对数字进行的运算操作都是习惯于中缀表达式，但是，对于计算机而言，并不能对它进行识别，它只能有效的对后缀表达式进行识别，因此，为了实现运算的功能，我们就必须要编写出一个能够将中缀表达式转换成后缀表达式的程序，并且将后缀表达式进行有效的控制，让机器能够将我们输入的字符转换成表达式最终的结果。

    基于此目的，我们首先就来实现如何将中缀表达式转换成后缀表达式。我们定义一个链表和一个堆栈，链表用于将我们转换的结果存储起来，而堆栈的作用就是对我们输入的字符进行操作，区分其优先级，让其符合后缀的特点。

    其次就是要对我们产生的含有后缀表达式的字符进行识别，将我们需要的字符转换成对应的数据类型，并最终运行出正确的结果

    最后就是将我们在程序中开辟的所有的节点空间都释放掉，做好善后的工作。

1．声明数据结构的类型：

1）.基本节点类型：

struct Node

{

  DataType info;

  PNode link;

};

2）.堆栈节点类型：

struct LinkStack

{ PNode base;

  PNode top;

};

3）.含有头尾节点指针的链表类型：

struct LinkList

{ PNode base;

  PNode top;

};

2.基本函数的申明：

1）。PLinkList Create_LinkListPointer(void) 用于创建一个含有头尾节点的链表指针，便于随时访问链表。

2）。PLinkList Create_LinkList(PLinkList pllist) 用于创建一个含有头和尾节点的链表，并将其值为NULL

3). PLinkList Create_LinkListNode(PLinkList pllist)用于方便保存后缀表达式的链表创建一个Node类型节点

4). PLinkStack Create_LinkStackPointer(void) 用于创建一个含有头尾节点的堆栈指针

5）。PLinkStack Create_LinkStack(PLinkStack plstack) 用于创建一个含有头和尾节点的堆栈，并将其值为NULL

6）。PLinkStack Create_LinkStackNode(PLinkStack plstack) 用于方便堆栈创建一个Node类型节点

7）。PLinkStack push_stack(PLinkStack plstack,DataType i) 将一个字符压入堆栈

8）。PLinkStack pop_stack_all(PLinkList pllist,PLinkStack plstack) 如果后面的优先级最低时，将堆栈中所有的字符全部出栈

9）。PLinkList print_llist(PLinkList pllist) 为了便于分析我们得到的结果，我们可以用此函数将我们保存的字符（后缀表达式）显示出来。

10）。int bracket_included(PLinkStack plstack) 判断是否有括号

11）。int islower_included(PLinkStack plstack) 判断是否有更低的优先级别，便于判断我们出栈的程度。

12）。int bracket_included_and_lower(PLinkStack plstack) 判断堆栈中是否有括弧并且里面的优先级比我们当前输入的优先级别低

13）。PLinkList push_LinkList(PLinkList pllist,DataType i) 将字符直接送入链表中

14）。PLinkList push_underline(PLinkList pllist) 加入下划线便于区分数据

15）。PLinkStack pop_stack_until_bracket(PLinkList pllist,PLinkStack plstack) 出栈，出到离堆栈栈顶最近的括弧为止

16）。PLinkStack pop_until_lower(PLinkList pllist,PLinkStack plstack) 出栈，直到出现了较低的优先级别时为止

17）。PLinkStack pop_stack_until_bracket_lower(PLinkList pllist,PLinkStack plstack) 此函数的功能用于堆栈中游括弧并且后面还有较低的优先级别的操作符时将栈出到离较低的优先级别时为止，与PLinkStack pop_stack_until_bracket(PLinkList pllist,PLinkStack plstack)和相似，有细微的差别

18）。PLinkStack pop_one(PLinkStack plstack) 将栈顶的元素直接出栈

19）。PLinkStack pop_all(PLinkList pllist,PLinkStack plstack) 将堆栈里面的元素全部出栈，并保存到链表中去

20）。int isOperator(DataType i) 用于判断是否为运算符

21）。int isPoint_included(PNode p) 用于判断时候有小数点

22）。int Calculator_underline(PNode p) 用于计算下划线的个数，为我们后面计算数值时作铺垫。

23）。NumberType Calculator(PLinkList pllist) 用于将我们链表中含有下划线的字符转换成对应的整数，并计算出后缀表达式的数值

三．程序的具体实现过程：

1．定义100个字符数组，s[100],一个全局变量i，一个链表变量和一个堆栈变量

2．做好前期工作，创建含有指向头和尾节点的链表和堆栈，接着为他们都开辟一个头和尾节点（本程序的头节点没有存储数据）

3．输入我们想要的中缀表达式例如：1+2*（3+4），我们用数组s来保存

4．从s[0]到s[strlen(s)-1],我们每一个都进行字符的扫描，将他们送入到链表中去或者是符号堆栈中去，具体的实现过程如下：

一如果我们的第一个字符不为运算符（操作符），则直接将送入链表中

二如果我们字符是操作符，且符号栈（堆栈）为空，则我们直接将符号压入堆栈，并且判断链表的顶部是否为操作符，如果不是的，则将下划线加入到链表中来

三余下的情形为我们的字符数组中的字符是操作符，但是我们的堆栈不为空

1判断我们的字符是否为左括弧，如果是的，则直接将它压入堆栈，如果我们的堆栈顶部已经是左括弧，则我们需要将下划线加入到链表中去，便于我们区分下一个的数据

2如果我们当前的扫描字符为“+”或者是“-”，堆栈的顶部为“*”或者是“/”，并且堆栈中含有括弧，则我们需要将堆栈出栈到只剩下左括弧为止

3如果我们当前的扫描字符为“+”或者是“-”，堆栈的顶部为“*”或者是“/”，并且堆栈中不含有括弧，则我们需要将堆栈全部弹出

4如果我们当前的扫描字符为“*”或者是“/”，堆栈的顶部为“+”或者是“-”，则直接的将其压入堆栈中

5如果我们当前的扫描字符为“+”并且堆栈的字符（我说的是栈顶，下同）也为“+”则直接将其压入堆栈，同为减号也一样

6如果我们当前的扫描字符为“+”并且堆栈的字符为“-”，或者是我们当前的扫描字符为“-”并且堆栈的字符为“+”并且含有扩号，我们需要将堆栈出栈到只剩下括号为止，然后再将我们的操作符“+”或者“-”，压入堆栈中

7如果我们当前的扫描字符为“+”并且堆栈的字符为“-”，或者是我们当前的扫描字符为“-”并且堆栈的字符为“+”并且不含有扩号，我们需要将堆栈全部保存到链表中去，然后再将当前的字符“+”或者是“-”号压入堆栈

8如果我们的当前字符为“*”,并且堆栈的字符为“/”，有括弧，并且括弧后面还有较低的优先级的操作符，我们需要将堆栈出到括弧后面较低的优先级别时为止（出栈的元素我们都保存到链表中）,并将我们当前的字符压入堆栈，如果我们当前的字符为“/”或者是“*”，有括弧，并且括弧后面还有较低的优先级的操作符与上面的一样处理。

9如果我们的当前字符为“*”，并且堆栈的字符为“/”，有括弧，并且括弧后面没有较低的优先级别，我们需要将堆栈出到最后一个扩号时为止。并将我们当前的字符压入堆栈，出栈的元素我们把它保存到链表中。如果我们的当前字符为“/”，并且堆栈的字符为“*”，有括弧，并且括弧后面没有较低的优先级别，与上面的一样处理

10如果我们的当前字符为“*”，并且堆栈的字符为“/”，没有括弧，并且堆栈中有较低的优先级别，我们需要将堆栈出栈直到最低优先级别时候为止，同时象上面一样做好保存到链表中的工作。如果我们的当前字符为“/”，并且堆栈的字符为“*”，没有括弧，并且堆栈中有较低的优先级别，同上面一样的处理。

11如果我们的当前字符为“*”，并且堆栈栈顶的字符为“/”，没有括弧，并且堆栈中没有较低的优先级别时，我们将堆栈的元素全部清空，送到链表中去，并将当前的字符压入堆栈。如果我们的当前字符为“/”，并且堆栈栈顶的字符为“*”，没有括弧，并且堆栈中没有较低的优先级别时，同上面的一样处理。

12如果我们的当前字符为“*”,并且堆栈的字符为“*”，有括弧，并且括弧后面还有较低的优先级的操作符，我们需要将堆栈出到括弧后面较低的优先级别时为止（出栈的元素我们都保存到链表中）,并将我们当前的字符压入堆栈，如果我们当前的字符为“*”或者是“*”，有括弧，并且括弧后面还有较低的优先级的操作符与上面的一样处理。

13如果我们的当前字符为“*”，并且堆栈的字符为“*”，有括弧，并且括弧后面没有较低的优先级别，我们需要将堆栈出到最后一个扩号时为止。并将我们当前的字符压入堆栈，出栈的元素我们把它保存到链表中。如果我们的当前字符为“*”，并且堆栈的字符为“*”，有括弧，并且括弧后面没有较低的优先级别，与上面的一样处理

14如果我们的当前字符为“*”，并且堆栈的字符为“*”，没有括弧，并且堆栈中有较低的优先级别，我们需要将堆栈出栈直到最低优先级别时候为止，同时象上面一样做好保存到链表中的工作。如果我们的当前字符为“*”，并且堆栈的字符为“*”，没有括弧，并且堆栈中有较低的优先级别，同上面一样的处理。

15如果我们的当前字符为“*”，并且堆栈栈顶的字符为“*”，没有括弧，并且堆栈中没有较低的优先级别时，我们将堆栈的元素全部清空，送到链表中去，并将当前的字符压入堆栈。如果我们的当前字符为“*”，并且堆栈栈顶的字符为“*”，没有括弧，并且堆栈中没有较低的优先级别时，同上面的一样处理

于是，我们得到了我们希望的后缀表达式。

5．我们已经将我们所需要的后缀表达式保存了链表中了，接下来我们要做的就是如何利用链表中的这个后缀表达式，并将它转换成对应的字符，并计算出它的结果。（为了方便起见，下面的我都假设我们的操作符为“+”，对结果没有影响的）

1我们定义三个用于保存数据结果的全局变量t,t1,t2，还有中间过渡阶段需要用到的变量tmark1,tmark2，其它的变量也是因程序的需要而定义的，不在这里过多的赘述。

2我们找到链表中第一个操作符前的下划线,我们用p来标识它，我们再依据链表的头指针pllist->base来查找我们的q，即查找p前的第一个下划线，我们再找到q前的第一个下划线，用temp来标识它，找到了p和q和temp 后，我们就有转换的依据了。

3我们再判断一下p和q之间是否有小数点，如果有的话，我们用变量i来标识它的个数，便于我们算它的权值，之后我们可以将字符与“0”字符作差，用递推的方式算出小数点之前的数值，我们讲它记作t1,对于小数点之后的数值，我们也可以计算出它的权值，然后算出它的数值，与t1相加。

4同理，我们可以算出temp和q之间的数值，然后就可以用t1+t2,并用t来保存数值，如果不含有小数的话，依照上面的方法，我相信你一定会解决的，就不用我多说了。之后我们用p=p->link;q前面的一个指针赋值给q,下面就具体的问题再细分。

5如果p为链表的顶部的话，就依照上面就可以解决了。如果p不为链表的顶部的话，如：p为一个操作符，我们下一个的p就为p->link，q前面的一个指针赋值给q,之后，我们可以再次找出p前面的一个下划线，即找出temp的位置，就可以算出temp和q之间的值t1,然后用t=t+t2;就可以算出它的值了

6如果p->link不为操作符的话，我们就可以再往下一直的招，直到找到p->link为操作符为止，我们可以算p前一个的p到后来的p之间的下划线的个数，如果下划线的个数为二的话，依照上面2、3的步骤，我们可以算出p前面的两个下划线之间的数值把它记为tmark1,然后我们就可以用t=t+tmark1,算出我们的新结果。同样p=p->link; q前面的一个指针赋值给q。

7如果p->link不为操作符的话，我们就可以再往下一直的招，直到找到p->link为操作符为止，我们可以算p前一个的p到后来的p之间的下划线的个数，如果下划线的个数为一的话，，我们就可以算出前一个p到后一个p的值，记为t1,然后t=t+t1, 同样p=p->link; q前面的一个指针赋值给q。

8关与其它的情形我就不一一介绍了，要知道程序的实际执行过程清参照源代码。

最后就是将数值的结果显示在屏幕上，并释放所有的节点，整个过程就到此结束。

四、程序的调试：

1．  首先，我们输入我们想要的操作数：

1+2+3+4+5+6+7+8+9：

2．  我们回车之后，程序打印出我们的后缀表达式，并计算出结果：55