目录1. 课题分析 .111 设计目的 .112 主要内容 .1121 中缀表达式转换为后缀表达式 .1122 后缀表达式求值 .213 设计要求 .22.总体设计 .221 数据类型的定义 .222 主程序的流程 .33详细设计（源代码） .54调试分析 .1441 问题 1 .1442 问题 2 .1543 问题 3 .155测试结果 .156心得体会 .167参考文献 .16实用数据结构基础课程设计报告11.课题分析1 1 设计目的（1）掌握栈“后进先出”的特点。（2）掌握栈的典型应用中缀表达式转后缀表达式，并利用后缀表达式求值。（3）掌握串或者数组的相关操作。1 2 主要内容121 中缀表达式转换为后缀表达式（1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号） ，然后从中缀表达式中自左至右依次读入各个字符。（2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。（3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（4）如果读入的是开括号“（” ，则直接进栈；如果读入的是闭括号“） ”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为止。开括号“（”和闭括号“） ”均不输出到后缀表达式。（5）重复、步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（6）给后缀表达式加上0作为字符串结束标志。122 后缀表达式求值（1）定义一个 double 型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。（2）如果读入的是运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位整数值，然后将该整数值（将自动类实用数据结构基础课程设计报告2型转换为 double 型）直接进入运算数栈。（3）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元素放在运算符前面） ，并将计算结果存回运算数栈。（4）重复、步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。（5）和手工计算的结果进行比较，检验程序运行结果的正确性。假设输入中缀表达式为：（123+32）/5*2-15*18/（2+4）/15-7。转换后的后缀表达式为：123，32，+，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。后缀表达式求得的值为：52。1 3 设计要求（1）运算对象存在多位整数。（2）遇到除数为 0 的情况，应能给出相应提示，并提醒重新输入中缀表达式。（3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。（4）如果有两个同学同时完成该课题，要求分别采用顺序和链式结构实现其栈。2.总体设计2 1 数据类型的定义calcolate（）：依次扫描 string2 中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。实用数据结构基础课程设计报告32 2 主程序的流程先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点，则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“） ”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串start读入字符串 string1,i=0string1i?=0;String1i是否为数字直接存入字符串 string2 中先向 string2 中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到 string2 中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入 string2 中，直至遇到开阔号。i+String2 中存放转化好的后缀表达式z后缀表达式结果的计算 calcolate（）输出运算结果end实用数据结构基础课程设计报告4数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。3详细设计（源代码）#include#include#include#include#define MAX 60#define DEMAX 15#define NULL 0char string1MAX;char string2MAX;int j=0;struct node char data;int num;struct node *next;struct node *Initialization()/初始化栈链,链栈不带头结点struct node *top;top=(struct node *)malloc(sizeof(struct node);top-data=;top-num=0;top-next=NULL;return top;struct node *assort(struct node *s)/输入字符串struct node *p,*top;int i;top=s;int m;char a;gets(string1);实用数据结构基础课程设计报告5m=strlen(string1);for(i=0;idata=a;p-next=top;top=p;break;case *:case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，现将栈顶运算符出栈，再进栈。top-data=a;break;elsep=(struct node *)malloc(sizeof(struct node);/否，直接进栈p-data=a;p-next=top;top=p;break;case +:case -:string2j= ;j+;if(top-data=+|top-data=-|top-data=*|top-data=/)string2j=top-data;j+;实用数据结构基础课程设计报告6top-data=a;break;else p=(struct node *)malloc(sizeof(struct node);p-data=a;p-next=top;top=p;break;case ):string2j= ;j+;if(top-data=)printf(input error);break;while(top-data!=()string2j=top-data;j+;p=top;top=top-next;free(p);p=top;top=top-next;free(p);break;while(top-data!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#;printf(转化后的后缀表达式为:%sn,string2);ret