栈的应用：表达式求值的设计
算机分析解决综合性实际问题的基本能力。
在细节问题的分析上，较以往有了很大的提高。在寻求最优解的问题上，也能够找到多种解决方案来使自己的程序收放自如。如，在处理实数的问题上，我采用的是每取得一个字符，就立刻对此字符进行处理的方法。其实，我们可以用一个字符数组，来存储连接着的一系列数字字符，然后再通过atof函数，直接得到字符数组中所存储的数字。再如，对负数问题的处理上，我最初的想法是通过一个标志mark来记录前面的字符是否是负号（或减号），再在后面取到除符号外的数字时，选择是否添加负号。另外，与其他人不同的是，在我的课程设计中，Compare（）函数与其他有着很大的区别。通常情况下，同学们参照课本，都会采用占用7*7=49个空间的数组来分别存储对应两个字符的优先级符号，并对两个字符进行预算之后得到数组中的位置。虽然7*7的数组所占的空间并不是非常大，但在我看来这也是一种浪费，并且空间的浪费并没有换回时间一定的节省。因此，我采用了一种常规的思路。将各种运算符按照数学逻辑上的优先顺序进行排序，并得到两个字符之间的优先级关系。这样一来，我们将不再需要那7*7的数组，且时间复杂度并不大幅增涨。
在这个课程设计中，运用到的数据结构的知识主要是栈的知识。栈在各种软件系统中，应用非常广泛。栈的的存储特性(LIFO先进后出)，使得在用栈来编程时，思路清晰明了。在使用递归算法时，栈也是一种很好的选择。
此外，这次的课程设计进一步加强了我们运用C语言进行编程，调试，处理问题的能力，加深了我们对算法及数据结构的认识。同时我也意识到，开发程序的早期计划要做的充分，以免出现程序完成后发现不足而带来的修改麻烦。虽然这只是一个小小的软件，但对我们之后的影响确实很大的。
9
栈的应用：表达式求值的设计
7 附：源程序清单 #include
/*全局变量，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
栈的应用：表达式求值的设计
Stack Whereat; char sample;
InputFile = fopen(\ /*打开文件*/ OutputFile = fopen(\
Whereat = malloc(sizeof(struct Node)); /*给 Whereat分配空间*/ Whereat->Next = NULL;
if (!InputFile || !OutputFile) { /*错误处理*/ printf(\ return(1); }
sample = getc(InputFile); while ( sample != EOF){ Temp = fopen(\ /*生成Temp文件*/ ungetc(sample,InputFile); /* put back sample字符*/ ConvertToPost(InputFile,Whereat,Temp); /*中缀变后缀*/ if (PrintError){ /*错误处理*/ fprintf(OutputFile,\ fscanf(InputFile,\ PrintError = 0;
} else if (IsEmpty(Whereat) == 1){ /*跳过在input文件中的空格*/ } else if (IsEmpty(Whereat) != 1){ Reverse(Whereat); if (Top(Whereat) == 'B'){ /*错误处理，*/ /*A表示操作数B表示运算符*/ PrintError = 1; /*后缀表达式第一个元素应是操作数而不是运算符号*/
} fclose(Temp); Temp = fopen(\ Calculate(OutputFile, Whereat,Temp); /*计算结果*/ } fclose(Temp); MakeEmpty(Whereat); /* 清空Whereat用来处理下一行*/ putc('\\n',OutputFile); /* 在输出文件中换行*/ sample = getc(InputFile);
} /* While循环结束*/
11
栈的应用：表达式求值的设计
free(Whereat); fclose(InputFile); fclose(OutputFile);
remove(\ /* 删除Temp.txt*/ return 1; }
/******检查堆栈是否为空******/ int IsEmpty(Stack S) {
return(S->Next==NULL); }
/******检查float堆栈是否为空******/ int FIsEmpty(FStack S) {
return(S->Next==NULL); }
/******弹出栈顶元素******/ void Pop(Stack S) { PtrToNode FirstCell; if (IsEmpty(S)) perror(\ else{ FirstCell = S->Next; S->Next = S->Next->Next; free(FirstCell); }
}
/******弹出float栈顶元素******/ void FPop(FStack S) {
Ptr_Fn FirstCell; if (FIsEmpty(S)) perror(\ else{ FirstCell = S->Next; S->Next = S->Next->Next; free(FirstCell);
12
栈的应用：表达式求值的设计
} }
/******将堆栈置空******/ void MakeEmpty(Stack S) {
if (S == NULL) perror(\ else while (!IsEmpty(S)) Pop(S); }
/******将float堆栈置空******/ void FMakeEmpty(FStack S) {
if (S == NULL) perror(\ else while (!IsEmpty(S)) Pop(S); }
/******元素进栈******/ void Push(char X, Stack S) {
PtrToNode TmpCell;
TmpCell = (PtrToNode)malloc(sizeof(struct Node)); if (TmpCell == NULL) perror(\ else{
TmpCell->Element = X; TmpCell->Next = S->Next; S->Next = TmpCell; } }
/******float元素进栈******/ void FPush(float X, FStack S) {
Ptr_Fn TmpCell;
TmpCell = (Ptr_Fn)malloc(sizeof(struct FNode));
13