栈的应用：表达式求值的设计

计算后缀表达式结果，将结果输出到”output.txt”文件中。

4测试方法

设计针对程序的input.txt文件，并将运行结果与期望测试进行比较。

5 程序运行效果 5.1 基本测试：

在input文件中输入表达式如下图2： 则输出结果如下图3：

图2 图3

图4

5.2扩展测试：

在input文件中输入表达式如下图5： 则输出结果如下图6：

7

栈的应用：表达式求值的设计

图5 图6

5.3容错测试：

在input文件中输入表达式如下图7： 则输出结果如下图8：

图7 图8

6 设计心得

通过此次的课程设计，巩固和加深了我对栈、队列、字符串等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（；提高利用计

8

栈的应用：表达式求值的设计

算机分析解决综合性实际问题的基本能力。

在细节问题的分析上，较以往有了很大的提高。在寻求最优解的问题上，也能够找到多种解决方案来使自己的程序收放自如。如，在处理实数的问题上，我采用的是每取得一个字符，就立刻对此字符进行处理的方法。其实，我们可以用一个字符数组，来存储连接着的一系列数字字符，然后再通过atof函数，直接得到字符数组中所存储的数字。再如，对负数问题的处理上，我最初的想法是通过一个标志mark来记录前面的字符是否是负号（或减号），再在后面取到除符号外的数字时，选择是否添加负号。另外，与其他人不同的是，在我的课程设计中，Compare（）函数与其他有着很大的区别。通常情况下，同学们参照课本，都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号，并对两个字符进行预算之后得到数组中的位置。虽然7*7的数组所占的空间并不是非常大，但在我看来这也是一种浪费，并且空间的浪费并没有换回时间一定的节省。因此，我采用了一种常规的思路。将各种运算符按照数学逻辑上的优先顺序进行排序，并得到两个字符之间的优先级关系。这样一来，我们将不再需要那7*7的数组，且时间复杂度并不大幅增涨。

在这个课程设计中，运用到的数据结构的知识主要是栈的知识。栈在各种软件系统中，应用非常广泛。栈的的存储特性(LIFO先进后出)，使得在用栈来编程时，思路清晰明了。在使用递归算法时，栈也是一种很好的选择。

此外，这次的课程设计进一步加强了我们运用C语言进行编程，调试，处理问题的能力，加深了我们对算法及数据结构的认识。同时我也意识到，开发程序的早期计划要做的充分，以免出现程序完成后发现不足而带来的修改麻烦。虽然这只是一个小小的软件，但对我们之后的影响确实很大的。

9

栈的应用：表达式求值的设计

7 附：源程序清单 #include #include #include int PrintError = 0;

/*全局变量，0代表正常，1代表表达式出错*/

/*char类型链表式堆栈，用来存放运算符号，以及用在中缀表达式转换等时候*/ typedef struct Node *PtrToNode; typedef PtrToNode Stack; int IsEmpty(Stack S); void MakeEmpty(Stack S); void Push(char X,Stack S); char Top(Stack S); void Pop(Stack S);

typedef struct Node{ char Element; PtrToNode Next; };

/*float类型链表式堆栈，用来存放操作数*/ typedef struct FNode *Ptr_Fn; typedef Ptr_Fn FStack; int FisEmpty(FStack S);

void FPush(float X,FStack S); float FTop(FStack S); void FPop(FStack S); typedef struct FNode{ float Element;

Ptr_Fn Next; };

void ConvertToPost(FILE *In, Stack Whereat,FILE *Temp); void Reverse(Stack Rev);

void Calculate(FILE *Change, Stack Whereat,FILE *Temp); /******主函数******/ int main() {

FILE *InputFile, *OutputFile,*Temp; /*初始化变量*/

10