《2022年北工大数据结构第二次上机中缀转后缀实验报告.docx》由会员分享，可在线阅读，更多相关《2022年北工大数据结构第二次上机中缀转后缀实验报告.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京工业高校2021- 2021学年 第 学期信息学部 电脑学院课程名称：数据结构与算法报告性质： 作业报告 试验报告学号：任课老师：学分：苏 航课程性质 ：学时：学科基础必修课56班级：成果：小组成员：老师评语：2021 年3 月31 日学习文档 仅供参考报告题目：输入中缀表达式，输出后缀表达式，并对表达式求值A. 分析中缀表达式的运算次序受运算符优先级和括号的影响；因此，将中缀表达式转换成等价的后缀表达式的关键在于如何恰当的去掉中缀表达式中的括号，然后在必要时根据先乘除后加减的优先规章调换运算符的先后次序；在去括号的过程中用栈来储存有关的元素；基本思路：从左至右次序扫描中缀表达式，用栈来存
2、放表达式中的操作数， 开括号，以及在这个开括号后面的其他临时不能确定运算次序的内容；（1） 当输入的是操作数时，直接输出到后缀表达式（2） 当遇到开括号时，将其入栈（3） 当输入遇到闭括号时，先判定栈是否为空，假设为空，就表示括号不匹配，应作为错误反常处理，清栈退出；假设非空，就把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中；由于后缀表达式不需要括号，因此弹出的括号不放到输出序列中，假设没有遇到开括号，说明括号不匹配，做反常处理，清栈退出；（4） 当输入为运算符时四就运算 + - * / 之一时：a. 循环，当栈非空 &栈顶不是开括号 &栈顶运算符的优先级不低
3、于输入的运算符的优先级时，反复操作将栈顶元素弹出，放到后缀表 达式中；b. 将输入的运算符压入栈中；（5） 最终，当中缀表达式的符号全部扫描完毕时，假设栈内仍有元素，就将其全部依次弹出，放在后缀表达式序列的尾部；假设在弹出的元素中遇到开括号，就说明括号不匹配，做反常处理，清栈退出；B. 实现#include #include #include #includeusing namespace std; #define N 1000char infixN; /中缀表达式未别离，都在一个字符串里char expressionN10;/ 储存预处理过的表达式，也就是每个元素都别离过的表达式char s
4、uffixN10;/ 储存后缀表达式的操作数intcount;/表达式中元素的个数一个完整到数字可能不止一位数或者符号int suffixLength;/后缀表达式的长度int levelchar a switchacase #:return 0; case +:case -:return 1; case *:case /:return 2;case :return 3; default:break;return -1;int isDigitalchar xifx=0&x=A&x=a&x=z| x=. return 1;return 0;int isNumberchar *str int i;
5、 fori=0;stri;i+ifisDigitalstri=0return 0;return 1;/*预 处理 中缀 表达 式， 把连续 的字符 别 离成 不同 的元 素， 用字 符串 数组expression储存，便利后面的运算，由于这里考虑了运算数可能不全是个位数比方：12+3在处理成后缀表达式时，是 123+，简洁产生歧义 1+23 . 12+3 */ void pretreatmentchar *strint i,j,numberFlag; char temp3; char number10; count=0; numberFlag=0;forj=0,i=0;stri;i+ ifis
6、Digitalstri=0ifnumberFlag=1 numberj=0;strcpyexpressioncount+,number; j=0;numberFlag=0;ifstri.= temp0=stri;temp1=0; strcpyexpressioncount+,temp;else numberFlag=1; numberj+=stri;puts别离后的表达式为 ; fori=0;icount;i+printf%s ,expressioni;puts;puts;/*中缀表达式 转 后缀表达式遍历字符串，对于 stristri是运算数或者是字母代替的运算变量输出；stri是符号，有两
7、种情形(1) ，是右括号，栈顶元素输出，直到与stri匹配的左括号出栈左括号不用输出打印(2) ，是运算符，判定 stri与栈顶元素的优先级， stri优先级 不高于 栈顶符号，就栈顶元素输出，直到栈空或者 栈顶符号优先级低于 stri*/ void infix_to_suffixchar strN10memsetsuffix,0,sizeofsuffix; suffixLength=0;stack st; int i=0;char Mark2=#;st.pushMark; doifisNumberstri=1/运算数直接储存到后缀表达式中strcpysuffixsuffixLength+,s
8、tri;else ifstri0=/是 左括号，直接入栈st.pushstri;else ifstri0=/是 右括号，栈顶出栈，直到与其匹配的左括号出栈while strcmpst.top,.=0 char temp10; strcpytemp,st.top;strcpysuffixsuffixLength+,temp; st.pop;st.pop;else if strcmpst.top,=0 /是 运算符，且栈顶是左括号， 就该运算符直接入栈st.pushstri;else /是 运算符，且栈顶元素优先级不小于运算符，就栈顶元素始终/出栈，直到 栈空 或者 遇到一个优先级低于该运算符的元
9、素while .st.empty char temp10; strcpytemp,st.top;if levelstri0 leveltemp0 break;strcpysuffixsuffixLength+,temp; st.pop;st.pushstri;i+;whilestri0.=0;while strcmpst.top,#.=0 /将栈取空终止char temp10; strcpytemp,st.top; strcpysuffixsuffixLength+,temp; st.pop;puts后缀表达式为： ; fori=0;isuffixLength;i+printf%s,suffi
10、xi;puts;puts;/*运算后缀表达式的值*/ char ktN10;int stackTop;void getResultchar strN10 stackTop=0;/* 这里要留意，内存的安排方案导致 i的位置就在 temp9 旁边，然后 strcpy函数直接拷贝内存的话，在 temp 越界情形下会掩盖 i的值*/ int i;char temp10; fori=0;isuffixLength;i+ifisNumberstri=1 strcpyktstackTop+,stri;else char a10,b10; double na,nb,nc;strcpya,ktstackTop
11、-1; na = atofa;stackTop-;strcpyb,ktstackTop-1; nb = atofb;stackTop-;ifstri0=+nc=nb+na;else ifstri0=-nc=nb-na; else ifstri0=*nc=nb*na; else ifstri0=/nc=nb/na;sprintftemp,%lf,nc; strcpyktstackTop+,temp;putsnThe result is : %fn; printf%sn,ktstackTop-1;int mainprintfPlease input calculate Expression :n;
12、 char tempN;whilegetsinfix strcpytemp,infix; pretreatment strcattemp, ; infix_to_suffixexpression; getResultsuffix;return 0;C. 总结试验需要细心细心再细心；原来以为程序运行不会出问题，输入的简洁表达式都可以转换并运算正确，结果 遇到稍复杂一点的就不行了，比方表达式中有两对括号运算后在进行加减运算， 总是转换不正确，求到的值也不对；后来发觉是当不是栈非空&栈顶不是开括号&栈顶运算符的优先级不低于输入的运算符的优先级时，应将运算符压入栈 中，不要输出，解决这个问题以后，程序就可以完善运行了；