中缀表达式转化成后缀表达式及求值

贵州财经学院实验报告专业：软件工程姓名：学号：实验名称：后缀表达式求值指导老师：实验三中缀表达式转换成后缀表达式，然后按后缀表达式计算实验[实验目的]对中缀表达式转换成后缀表达式，然后按后缀表达式计算进行分析与设计，并上机运行。使学生能通该实验理解对一个简单表达式的编译实现过程。[实验要求]要求对中缀表达式转换成后缀表达式，然后按后缀表达式计算作设计性实验，并上机运行，写出实验报告。[实验时数]2学时[实验内容]中缀表达式转换成后缀表达式，然后按后缀表达式计算，例如：5+(4+2)/2-3*2。[实验环境]WindowsXP、VC++6.0[算法描述及实验步骤]定义个两个栈，一个用于存储字符集合，一个用于存储浮点数集合；定义栈的操作函数及比较运算符优先级的函数；定义将中缀表达式转换为后缀表达式的函数；最后，计算后缀表达式的值。[实验结果][实验总结]通过此次实验，我将栈的基本运算运用到中缀表达式转换到到后缀表达式，并对其后缀表达式求值的算法中，充分利用了栈“先进后出”的基本特点，达到了实验要求的结果。对我进一步的学习相关的专业课程，起到了促进作用。[附录]#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX100typedefstruct/*定义一个用于存储字符集合的栈*/{charelements[MAX];inttop;}STACK_char;typedefstruct/*定义一个用于存储浮点数集合的栈*/{doubleelements[MAX];inttop;}STACK_num;/*以下定义操作函数*/voidMakeNull_char(STACK_char*S){(*S).top=MAX;}charTop_char(STACK_char*S){return(*S).elements[(*S).top];}charPopAddTop_char(STACK_char*S){(*S).top=(*S).top+1;return(*S).elements[(*S).top-1];}voidPush_char(charx,STACK_char*S){(*S).top=(*S).top-1;(*S).elements[(*S).top]=x;}voidMakeNull_num(STACK_num*S){(*S).top=MAX;}doubleTop_num(STACK_num*S){return(*S).elements[(*S).top];}doublePopAddTop_num(STACK_num*S){(*S).top=(*S).top+1;return(*S).elements[(*S).top-1];}voidPush_num(doublex,STACK_num*S){(*S).top=(*S).top-1;(*S).elements[(*S).top]=x;}intcompare(charx,chary){/*此函数比较运算符优先级*/if((x=='*'||x=='/'||x=='%')&&(y=='+'||y=='-'))return1;elsereturn0;}voidchange(char*a,char*b){/*此函数将中缀表达式转换为后缀表达式*/charnum[12]="0123456789.";charc[2],d[2];/*定义两个字符串，用于下面字符串比较*/STACK_charS;inti,k;MakeNull_char(&S);Push_char('#',&S);k=0;for(i=0;i<strlen(a);i++){c[0]=a[i];c[1]='\0';d[0]=a[i+1];d[1]='\0';if(a[i]=='')/*输入过程遇空格跳过*/continue;elseif(strstr(num,c))/*比较字符串以确定当前字符是否为数字*/{b[k]=a[i];k++;if(i==strlen(a)-1){b[k]='';k++;}elseif(strstr(num,d)==NULL)/*运算符后加空格*/{b[k]='';k++;}}else{if(a[i]!=')'){if(a[i]=='(')/*遇‘(’压入栈*/Push_char(a[i],&S);elseif(compare(a[i],Top_char(&S))||Top_char(&S)=='#')/*优先级高于栈顶元素压入栈*/Push_char(a[i],&S);else{while(compare(a[i],Top_char(&S))==0&&Top_char(&S)!='#'&&Top_char(&S)!='(')/*优先级低于栈顶元素直接输出*/{b[k]=PopAddTop_char(&S);k++;b[k]='';k++;}Push_char(a[i],&S);}}else{while(Top_char(&S)!='(')/*遇‘)’向前查找第一个‘(’并输出其间运算符*/{b[k]=PopAddTop_char(&S);k++;b[k]='';k++;}PopAddTop_char(&S);}}}while(Top_char(&S)!='#')/*依次输出剩余运算符*/{b[k]=PopAddTop_char(&S);k++;b[k]='';k++;}b[k-1]='\0';/*字符串后加‘\0’结束*/}doublecompute(char*b)/*计算后缀表达式的值*/{doubleresult;doubleinteger=0,decimal=0;/*定义变量，表示整数、小数部分*/doublem=1;doublet=0.1;doubletop,second;STACK_numL;inti;i=0;MakeNull_num(&L);while(b[i]!='\0'){while(b[i]!=''&&b[i]!='.'&&b[i]!='+'&&b[i]!='-'&&b[i]!='*'&&b[i]!='/'&&b[i]!='+'&&b[i]!='%')/*对整数部分进行运算*/{integer=integer*m+b[i]-48;m*=10;i++;}if(b[i]=='.')/*对小数部分进行运算*/{i++;while(b[i+1]!=''&&b[i+1]!='\0'){i++;decimal+=(b[i]-48)*t;t*=0.1;}decimal+=(b[i]-48)*t;t*=0.1;i++;}integer+=decimal;if(b[i]==''&&b[i-1]!='+'&&b[i-1]!='-'&&b[i-1]!='*'&&b[i-1]!='/'&&b[i-1]!='+'&&b[i-1]!='%')/*将一个完整操作数进行压栈*/{Push_num(integer,&L);m=1;t=0.1;integer=0;decimal=0;}switch(b[i])/*对不同运算符进行分别处理*/{case'+':top=PopAddTop_num(&L);second=Top_num(&L);result=top+second;PopAddTop_num(&L);Push_num(result,&L);break;case'-':top=PopAddTop_num(&L);second=Top_num(&L);result=second-top;PopAddTop_num(&L);Push_num(result,&L);break;case'*':top=PopAddTop_num(&L);second=Top_num(&L);result=top*second;PopAddTop_num(&L);Push_num(result,&L);break;case'/':top=PopAddTop_num(&L);second=Top_num(&L);result=second/top;PopAddTop_num(&L);Push_num(result,&L);break;case'%':top=PopAddTop_num(&L);second=Top_num(&L);