北工大数据结构第二次上机中缀转后缀实验报告_(2).doc
.工业大学2016- 2017学年 第 学期信息学部 计算机学院课程名称：数据结构与算法报告性质：作业报告 实验报告_：任课教师：航课程性质：学科基础必修课学分：3.5学时：56_成绩：小组成员：教师评语：2017年 3月 31日报告题目：输入中缀表达式，输出后缀表达式，并对表达式求值A 分析中缀表达式的运算顺序受运算符优先级和括号的影响。因此，将中缀表达式转换成等价的后缀表达式的关键在于如何恰当的去掉中缀表达式中的括号，然后在必要时按照先乘除后加减的优先规则调换运算符的先后次序。在去括号的过程中用栈来储存有关的元素。基本思路：从左至右顺序扫描中缀表达式，用栈来存放表达式中的操作数，开括号，以与在这个开括号后面的其他暂时不能确定计算次序的容。（1） 当输入的是操作数时，直接输出到后缀表达式（2） 当遇到开括号时，将其入栈（3） 当输入遇到闭括号时，先判断栈是否为空，若为空，则表示括号不匹配，应作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中。由于后缀表达式不需要括号，因此弹出的括号不放到输出序列中，若没有遇到开括号，说明括号不匹配，做异常处理，清栈退出。（4） 当输入为运算符时（四则运算+ - * / 之一）时：a.循环，当（栈非空&&栈顶不是开括号&&栈顶运算符的优先级不低于输入的运算符的优先级）时，反复操作将栈顶元素弹出，放到后缀表达式中。b.将输入的运算符压入栈中。（5） 最后，当中缀表达式的符号全部扫描完毕时，若栈仍有元素，则将其全部依次弹出，放在后缀表达式序列的尾部。若在弹出的元素中遇到开括号，则说明括号不匹配，做异常处理，清栈退出。B 实现#include<stdio.h>#include<string.h>#include<stdlib.h>#include<stack>using namespace std;#define N 1000char infixN; /中缀表达式（未分离，都在一个字符串里）char expressionN10;/保存预处理过的表达式，也就是每个元素都分离过的表达式char suffixN10;/保存后缀表达式的操作数int count;/表达式中元素的个数（一个完整到数字（可能不止一位数）或者符号）int suffixLength;/后缀表达式的长度int level(char a) switch(a) case '#':return 0; case '+': case '-':return 1; case '*': case '/':return 2; case '':return 3; default:break; return -1;int isDigital(char x) if( (x>='0'&&x<='9') | (x>='A'&&x<='Z') | (x>='a'&&x<='z') | (x='.') ) return 1; return 0;int isNumber(char *str) int i; for(i=0;stri;i+) if(isDigital(stri)=0)return 0; return 1;/*预处理中缀表达式，把连续的字符分离成不同的元素，用字符串数组（expression）保存，方便后面的计算，因为这里考虑了运算数可能不全是个位数比如：（12+3）在处理成后缀表达式时，是123+，容易产生歧义（1+23 ? 12+3）*/void pretreatment(char *str) int i,j,numberFlag; char temp3; char number10; count=0; numberFlag=0; for(j=0,i=0;stri;i+) if(isDigital(stri)=0) if(numberFlag=1) numberj=0; strcpy(expressioncount+,number); j=0; numberFlag=0; if(stri!=' ') temp0=stri;temp1=0; strcpy(expressioncount+,temp); else numberFlag=1; numberj+=stri; puts("分离后的表达式为"); for(i=0;i<count;i+) printf("%s ",expressioni); puts("");puts("");/*中缀表达式 转 后缀表达式遍历字符串，对于stristri是运算数（或者是字母代替的运算变量）输出；stri是符号，有两种情况(1)，是右括号，栈顶元素输出，直到与stri匹配的左括号出栈（左括号不用输出打印）(2)，是运算符，判断stri与栈顶元素的优先级，stri优先级 不高于 栈顶符号，则栈顶元素输出，直到栈空 或者 栈顶符号优先级低于stri*/void infix_to_suffix(char strN10) memset(suffix,0,sizeof(suffix); suffixLength=0; stack <char*> st; int i=0; char Mark2="#" st.push(Mark); do if(isNumber(stri)=1)/运算数直接保存到后缀表达式中 strcpy(suffixsuffixLength+,stri); else if(stri0='(') /是 左括号，直接入栈 st.push(stri); else if(stri0=')') /是 右括号，栈顶出栈，直到与其匹配的左括号出栈 while( strcmp(st.top(),"(")!=0 ) char temp10; strcpy(temp,st.top(); strcpy(suffixsuffixLength+,temp); st.pop(); st.pop(); else if( strcmp(st.top(),"(")=0 )/是 运算符，且栈顶是左括号，则该运算符直接入栈 st.push(stri); else /是 运算符，且栈顶元素优先级不小于运算符，则栈顶元素一直 /出栈，直到 栈空 或者 遇到一个优先级低于该运算符的元素 while( !st.empty() ) char temp10; strcpy(temp,st.top(); if( level(stri0) > level(temp0) ) break; strcpy(suffixsuffixLength+,temp); st.pop(); st.push(stri); i+; while(stri0!=0); while( strcmp(st.top(),"#")!=0 ) /将栈取空完毕 char temp10; strcpy(temp,st.top(); strcpy(suffixsuffixLength+,temp); st.pop(); puts("后缀表达式为："); for(i=0;i<suffixLength;i+) printf("%s",suffixi); puts(""); puts("");/*计算后缀表达式的值*/char ktN10;int stackTop;void getResult(char strN10) stackTop=0;/*这里要注意，存的分配方案导致 i 的位置就在temp9旁边，然后strcpy()函数直接拷贝存的话，在temp越界情况下会覆盖 i 的值*/ int i; char temp10; for(i=0;i<suffixLength;i+) if(isNumber(stri)=1) strcpy(ktstackTop+,stri); else char a10,b10;double na,nb,nc; strcpy(a,ktstackTop-1); na = atof(a);stackTop-;strcpy(b,ktstackTop-1); nb = atof(b);stackTop-; if(stri0='+')nc=nb+na; else if(stri0='-')nc=nb-na; else if(stri0='*')nc=nb*na; else if(stri0='/')nc=nb/na; sprintf(temp,"%lf",nc);strcpy(ktstackTop+,temp); puts("nThe result is : %fn");printf("%sn",ktstackTop-1);int main()printf("Please input calculate Expression :n"); char tempN; while(gets(infix) strcpy(temp,infix); pretreatment( strcat(temp," ") ); infix_to_suffix(expression); getResult(suffix); return 0;C 总结实验需要细心细心再细心。本来以为程序运行不会出问题，输入的简单表达式都可以转换并计算正确，结果遇到稍复杂一点的就不行了，比如表达式中有两对括号计算后在进行加减运算，总是转换不正确，求到的值也不对。后来发现是当不是（栈非空&&栈顶不是开括号&&栈顶运算符的优先级不低于输入的运算符的优先级）时，应将运算符压入栈中，不要输出，解决这个问题以后，程序就可以完美运行了。8 / 8
