用两种方式实现表达式自动计算.docx
《用两种方式实现表达式自动计算.docx》由会员分享，可在线阅读，更多相关《用两种方式实现表达式自动计算.docx（28页珍藏版）》请在冰点文库上搜索。
用两种方式实现表达式自动计算
数据结构（双语）
——项目文档报告
专业：
网络工程
班级：
一班
指导教师：
吴亚峰
姓名：
陈金广
学号：
200801040102
一、设计思想……………………………………………………….03
二、算法流程图…………………………………………………….03
三、源代码………………………………………………………….06
四、运行结果……………………………………………………….18
五、遇到的问题及解决…………………………………………….19
六、心得体会……………………………………………………….20
一、设计思想
程序代码是用两种算法实现中缀表达式转后缀表达式，并计算出表达式的值。
第一种算法是给出一个中缀表达式，编译运行后输出后缀表达式，并计算出后缀表达式的值。
首先，先创建两个数组，一个用于存储输入的中缀表达式，并以“#”结束，一个用于输出后缀表达式。
创建一个操作符栈，初始化并写好出栈入栈函数，用操作符栈存储操作符。
对中缀表达式进行遍历时，遇到数值就直接输入要输出后缀表达式的数组，遇到操作符时，首先对操作符的优先级进行设置,“*”，“/”，“%”的优先级设置为最高，“+”“-”的优先级低于前三个符号，“#”的优先级设置为最低。
对操作符栈进行操作时首先将“#”放入栈顶。
判断栈顶操作符与当前操作符优先级的大小，若当前操作符优先级大的话直接入栈，若当前操作符小于或者等于栈顶运算福的话栈顶操作符出栈，并输入后缀表达式所在的数组，当前操作符再入栈。
遇到“（”时，此时认为“（”的优先级为最高，直接入栈，但是当它入栈后优先级变为最小，当栈顶为“（”时操作符可以直接入栈，其他操作符直接入栈直至遇到“）”时，与“（”配对，括号之间的所有的操作符全部出栈并输入后缀表达式。
继续遍历中缀表达式。
当遍历到“#”时认为遍历中缀表达式结束。
此时操作符栈所有操作符出栈并输入后缀表达式，打印后缀表达式。
得到后缀表达式后，声明并初始化数值栈，写出入栈出栈函数，对后缀表达式进行遍历，遇到数值直接入栈，每遇到操作符，从数值栈栈顶取两个数进行运算，将运算结果入数值栈，继续遍历后缀表达式直至表达式结束，得到的结果就是后缀表达式的计算值。
第二种算法不将中缀表达式转换为后缀表达式，而是直接对中缀表达式进行操作，开始声明并初始化栈，一个操作符栈，一个数值栈。
直接对中缀表达式进行遍历，同时也要声明操作符的优先级，“*”，“/”，“%”的优先级设置为2，“+”“-”的优先级设置为1，然后开始遍历中缀表达式，遇到字符时首先判断字符类型，也就是sort的值，当sort为1时表示读到的是操作符，入操作符栈，当sort为2时读到的是数，入数栈。
遇到数值直接入数值栈，遇到“（”时，设置其优先级为零，但是直接入栈，不用比较优先级大小，直至遇到“）”时才出操作符栈。
操作符入栈时要进行优先级的比较，若大于栈顶操作符的优先级直接入栈，否则操作符栈的栈顶操作符先出栈，当前操作符再入栈，每当有操作符出栈时，都要从数值栈栈顶出来两个数进行运算，运算结果再压入数值栈中，直至表达式遍历结束。
结束时看数栈和操作符栈是否为空，不为空的话操作符栈元素出栈，从数栈栈顶取两个元素进行计算，计算结果再次压入数栈，如此循环直至操作符栈为空，计算结果压入数栈中，得到的结果就是中缀表达式的值。
得到的结果是double类型数据。
调用sprintf函数，此函数用于将各种类型的数据转化为字符串并将其输出。
2、算法流程图
图1为扫描并存储中缀表达式，遍历中缀表达死读到数字或者小数点时直接要输出后缀表达式的数组，读到操作符时入操作符栈，入栈前先跟操作符栈顶操作符进行优先级比较，
优先级大直接入栈，否则栈顶操作符出栈输入后缀表达式所在数组，当前操作符再入栈，直至读到'#'为止。
图2为计算后缀表达式，此时遍历后缀表达式，读到数直接入数栈，每读到运算符就从数栈出来两个数进行计算，计算结果压入数栈，直至遍历结束。
计算结果就是表达式的值。
图3为算法二的流程图，不用将中缀表达式转化成后缀表达式，而是直接进行处理，遇到数入数栈s1，遇到操作符先进行优先级比较，若栈顶运算符优先级大于或者等于当前运算符，栈顶运算符出栈并从数栈s1取两个数进行计算，计算结果入数值栈，当前运算符再入栈。
如此循环直至遍历表达式结束。
图1中缀转后缀算法流程图
图2后缀表达式计算算法流程图
图3直接处理中缀表达式算法流程图
三、源代码
下面给出的是用中缀表达式转后缀表达式再计算结果算法实现的程序的源代码：
#include
#defineStackSize100
typedefstruct/*定义数值栈*/
{
doubledata[StackSize];
inttop;
}StackD;
voidDsInit（StackD*s）/*初始化数值栈,由指针s指出*/
s->top=-1;/*栈顶为空*/
}
intDpush（StackD*s,doublee）/*进栈*/
if（s->top{s->top=s->top+1;/*若栈不满，则将e进栈*/s->data[s->top]=e;/*栈顶元素变为e*/return1;}else/*若栈判定为满，返回0*/{return0;}}doubleDpop（StackD*s）/*出栈*/{doublee;if（-1==s->top）/*判定栈顶是否为空，若栈顶为空，返回1*/{return1;}else{e=s->data[s->top];/*若栈顶不为空，将栈顶元素e出栈*/（s->top）--;returne;}}typedefcharElemType;/*定义字符栈*/typedefstruct{ElemTypedata[StackSize];inttop;}StackR;voidInitStack（StackR*s）/*初始化字符栈，由指针s指出*/{s->top=-1;/*栈顶为空*/}intRpush（StackR*s,ElemTypee）/*进栈*/{if（s->top{s->top=s->top+1;/*若栈不满，将e进展*/s->data[s->top]=e;/*栈顶元素变为e*/return1;}else{return0;/*若栈判定为满，返回0*/}}ElemTypeRpop（StackR*s）/*出栈*/{ElemTypee;if（-1==s->top）/*判定栈顶是否为空，若栈顶为空，返回1*/{return1;}else{e=s->data[s->top];/*若栈顶不为空，将栈顶元素e出栈*/（s->top）--;returne;}}intGetTop（StackRs,ElemType*e）/*取栈顶元素*/{if（0==s.top）/*若栈顶元素为空，返回0*/{*e=s.data[s.top];return0;}else{*e=s.data[s.top];/*指针e指向栈顶元素*/return1;}}intCalcare（intmode,charoper）/*比较优先级*/{/*返回操作符oper代表优先级得整数值，mode为1，表示oper是栈顶操作符，否则是当前操作符*/inttmp;/*定义一个临时变量tmp*/switch（oper）{case'#':tmp=0;break;case'（':tmp=（mode?1:6）;break;case'+':case'-':tmp=（mode?3:2）;break;case'*':case'%':case'/':tmp=（mode?5:4）;break;case'）':tmp=（mode?7:1）;break;}returntmp;/*将所得的tmp返回*/}charPrecede（charw,charch）/*判定操作符栈的栈顶操作符w,与当前操作符ch之间的优先关系*/{intgrade;/*取得栈顶操作符与当前操作符得优先级*/grade=Calcare（1,w）-Calcare（0,ch）;/*计算取得操作符与当前操作符的差值*/if（grade>0）return'>';else{if（grade==0）/*说明取得操作符和当前操作符相等*/return'=';elsereturn'<';}}voidchange（charE[],charA[]）/*中缀变后缀的实现函数E为原来的前缀表达式A为要转化成的后缀表达式*/{StackRS2;/*声明一个字符栈S2*/inti=0;/*i作为扫描数组E的指针*/intj=0;/*j用来指示数组A中待写入字符的位置*/charch=E[i];/*E中第一个字符送给ch*/charw='\0';InitStack（&S2）;/*初始化字符栈S2*/Rpush（&S2,'#'）;/*先把#压入栈内*/while（ch!='#'）/*当ch取得的元素不是#*/{if（ch>='0'&&ch<='9'||ch=='.'）/*若取得的元素为0到9或者是小数点*/{while（ch>='0'&&ch<='9'||ch=='.'）{A[j]=ch;/*将获得的元素赋予A数组*/j++;i++;ch=E[i];}A[j]='';j++;/*给A中的每个操作数后附加一个空格*/}if（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='（'||ch=='）'||ch=='#'）{GetTop（S2,&w）;/*取S2的栈顶元素*/while（Precede（w,ch）=='>'）/*栈顶操作符w比取得的操作符ch的优先级大*/{A[j]=w;/*将w赋予数组A*/j=j+1;Rpop（&S2）;/*将栈顶操作符w出栈*/GetTop（S2,&w）;/*取得的操作符入栈*/}if（Precede（w,ch）=='<'）/*栈顶操作符w比取得的操作符ch的优先级小*/Rpush（&S2,ch）;/*取得的操作符直接入栈*/else{if（Precede（w,ch）=='='&&w!='#'）/*栈顶操作符w与取得的操作符ch的优先级相等*/{Rpop（&S2）;/*将栈顶操作符w出栈*/GetTop（S2,&w）;/*观察栈顶操作符*/}}}if（E[i]!='#'）/*若取得的字符不是#i加1*/i++;ch=E[i];/*将从E数组取出的元素赋予ch*/}while（w!='#'）/*取得的操作符不是#*/{A[j]=w;/*将操作符赋予A数组*/j++;Rpop（&S2）;/*S2栈顶元素出栈*/GetTop（S2,&w）;/**/}A[j]='#';A[++j]='\0';}doubleCalc（chararr[]）/*计算后缀表达式的值*/{StackDs;/*声明一个数值栈s*/inti=0;charch;doublex=0,d=1.0;DsInit（&s）;/*初始化数值栈s*/ch=arr[i];while（ch!='#'）{switch（ch）/*switch语句用于读取字符串中的数值部分*/{case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':case'.':while（ch!=''）/*取得的字符不为空*/{if（'0'<=ch&&ch<='9'）{while（'0'<=ch&&ch<='9'）/*每读到一个整数部分就*10*/{x=x*10+（ch-'0'）;i=i+1;ch=arr[i];}}else{if（ch=='.'）{ch=arr[++i];while（'0'<=ch&&ch<='9'）/*每读到一个小数部分就/10*/{d=d*10;x=x+（ch-'0'）/d;ch=arr[++i];/*读取数组中下一个元素*/}}}}break;case'+':/*若取得的字符为+从数值栈取两个元素进行+运算*/x=Dpop（&s）+Dpop（&s）;break;case'-':/*若取得的字符为-从数值栈取两个元素进行-运算*/x=Dpop（&s）;x=Dpop（&s）-x;break;case'*':/*若取得的字符为*从数值栈取两个元素进行*运算*/x=Dpop（&s）*Dpop（&s）;break;case'/':x=Dpop（&s）;x=Dpop（&s）/x;break;case'%':x=Dpop（&s）;x=（double）（（int）Dpop（&s）%（int）x）;break;}Dpush（&s,x）;/*将x中压入数值栈*/x=0;/*将x置零*/i=i+1;ch=arr[i];/*取数组中下一个元素赋予ch*/d=1.0;}returnDpop（&s）;}voidmain（）/*主函数*/{charE[100];/*声明一个长度为100的数组E*/charA[100];/*声明一个长度为100的数组A*/printf（"Pleaseinputtheinfixexpresswitha'#'intheend:"）;gets（E）;/*获取E数组中的表达式*/change（E,A）;/*调用中缀表达式转后缀表达式的函数*/printf（"Thesurffixexpressis:%s\n",A）;/*输出后缀表达式*/printf（"Theresultis:%s=%f\n",E,Calc（A））;/*调用计算后缀表达式的函数并将值输出*/getchar（）;}下面给出的是用中缀表达式直接进行入栈计算算法实现的程序的源代码：#include#include#includetypedefstruct/*声明操作符结构体*/{charop;/*声明操作符类型*/charlevel;/*声明操作符优先级*/}opNode;typedefunion{opNodeopNode;/*声明操作符*/doublevalue;/*声明value数值为double型*/}Node;typedefstruct/*声明栈的结构体*/{charleixing;/*声明一个字符型sort*/Node*a[100];/*指定数组大小为100*/inttop;/*声明栈顶*/}Stack;Stack*init_sta（）/*初始化栈*/{inti;Stack*s=（Stack*）malloc（sizeof（Stack））;/*分配一个类型为Stack的结点变量的空间，空间大小为sizeof（Stack）,并将首地址放入指针变量s中*/s->top=0;for（i=0;i<100;i++）/*遍历栈全为空则栈为空*/s->a[i]=NULL;returns;}char*substr（char*s,intn1,intn2）/*截取子串函数*/{char*ss=（char*）malloc（sizeof（char）*（n2-n1+2））;/*分配空间，空间大小为n2-n1+2,并将首地址放入指针变量ss中*/inti,j=0;for（i=n1;i{ss[j++]=s[i];}ss[j]='\0';/*字符串后面加上'0'*/returnss;}intempty（Stack*ss）/*判空函数*/{returnss->top;/*返回栈顶元素*/}Node*Top（Stack*ss）/*观察栈顶函数*/{if（ss->top<=0）/*若栈顶为空，返回0*/{return0;}else/*若栈顶不为空，返回栈顶元素*/{returnss->a[ss->top-1];}}Node*Pop（Stack*ss）/*出栈函数*/{if（ss->top<=0）/*栈顶为空，返回0*/{return0;}else/*否则，栈顶元素出栈*/{ss->top--;returnss->a[ss->top];}}voidPush（Stack*p,Node*n）/*进栈函数*/{Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间，空间大小为sizeof（Node）,并将首地址放入指针变量temp中*/if（p->top>=100）/*判定栈是否已满*/{printf（"Error!TheStackisfull!\n"）;free（temp）;}else{if（p->leixing==1）/*sort为1，指向的为操作符栈，表明temp为操作符*/{temp->opNode.level=n->opNode.level;temp->opNode.op=n->opNode.op;}else/*sort为2指向的是数值栈，表明temp为数值*/temp->value=n->value;p->a[p->top]=temp;p->top=p->top+1;}}doublecalc（charop,doublem,doublen）/*每出栈一个操作符，就进行一次运算*/{switch（op）{case'+':returnn+m;case'-':returnn-m;case'*':returnn*m;case'/':returnn/m;case'%':return（int）n%（int）m;/*计算结束后，返回计算结果*/}return0;}voidmath（char*exp）/*处理函数*/{Node*top;/*声明栈顶*/Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量temp中*/Node*tempn=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量tempn中*/Node*tempm;/*声明一个tempm结点指针*/charc;char*temps="";unsignedintindex=0,tempindex;/*声明一个索引和一个临时索引*/doublea,b;Stack*s1=init_sta（）;/*初始化栈s1*/Stack*s2=init_sta（）;/*初始化栈s2*/s1->leixing=2;/*s1的类型为2，栈为数值栈*/s2->leixing=1;/*s2的类型为1，栈为操作符栈*/while（index{c=exp[index];if（c>='0'&&c<='9'||c=='.'）/*读取表达式中的各个数值*/{tempindex=index+1;while（tempindex='0'&&exp[tempindex]<='9'||exp[tempindex]=='.'））{tempindex++;/*当一个数没有读完，索引后移，直至整个数读完*/}if（tempindex==strlen（exp）-1）/*当临时索引到达表达式的尾部时，直接截取*/{temps=substr（exp,index,index+1）;}else{temps=substr（exp,index,tempindex）;}index=tempindex;/*索引指向临时索引所在位置*/temp->value=atof（temps）;/*将截取的子串转化为double类型*/Push（s1,temp）;/*将转化后的数压入数值栈*/}if（c=='+'||c=='-'）/*字符为+或者-时*/{tempn->opNode.op=c;tempn->opNode.level=1;/*设置优先级为1*/top=Top（s2）;while（empty（s2）>0&&tempn->opNode.level<=top->opNode.level）/*操作符栈不为空，并且栈顶操作符优先级高于或者等于当前操作符*/{tempm=Pop（s2）;/*操作符栈顶操作符出栈*/a=Pop（s1）->value;/*数值栈栈顶出来两个数*/b=Pop（s1）->value;temp->value=calc（tempm->opNode.op,a,b）;/*两个数进行运
s->top=s->top+1;/*若栈不满，则将e进栈*/
s->data[s->top]=e;/*栈顶元素变为e*/
return1;
else/*若栈判定为满，返回0*/
return0;
doubleDpop（StackD*s）/*出栈*/
doublee;
if（-1==s->top）/*判定栈顶是否为空，若栈顶为空，返回1*/
else
e=s->data[s->top];/*若栈顶不为空，将栈顶元素e出栈*/
（s->top）--;
returne;
typedefcharElemType;/*定义字符栈*/
typedefstruct
ElemTypedata[StackSize];
}StackR;
voidInitStack（StackR*s）/*初始化字符栈，由指针s指出*/
intRpush（StackR*s,ElemTypee）/*进栈*/
if（s->top{s->top=s->top+1;/*若栈不满，将e进展*/s->data[s->top]=e;/*栈顶元素变为e*/return1;}else{return0;/*若栈判定为满，返回0*/}}ElemTypeRpop（StackR*s）/*出栈*/{ElemTypee;if（-1==s->top）/*判定栈顶是否为空，若栈顶为空，返回1*/{return1;}else{e=s->data[s->top];/*若栈顶不为空，将栈顶元素e出栈*/（s->top）--;returne;}}intGetTop（StackRs,ElemType*e）/*取栈顶元素*/{if（0==s.top）/*若栈顶元素为空，返回0*/{*e=s.data[s.top];return0;}else{*e=s.data[s.top];/*指针e指向栈顶元素*/return1;}}intCalcare（intmode,charoper）/*比较优先级*/{/*返回操作符oper代表优先级得整数值，mode为1，表示oper是栈顶操作符，否则是当前操作符*/inttmp;/*定义一个临时变量tmp*/switch（oper）{case'#':tmp=0;break;case'（':tmp=（mode?1:6）;break;case'+':case'-':tmp=（mode?3:2）;break;case'*':case'%':case'/':tmp=（mode?5:4）;break;case'）':tmp=（mode?7:1）;break;}returntmp;/*将所得的tmp返回*/}charPrecede（charw,charch）/*判定操作符栈的栈顶操作符w,与当前操作符ch之间的优先关系*/{intgrade;/*取得栈顶操作符与当前操作符得优先级*/grade=Calcare（1,w）-Calcare（0,ch）;/*计算取得操作符与当前操作符的差值*/if（grade>0）return'>';else{if（grade==0）/*说明取得操作符和当前操作符相等*/return'=';elsereturn'<';}}voidchange（charE[],charA[]）/*中缀变后缀的实现函数E为原来的前缀表达式A为要转化成的后缀表达式*/{StackRS2;/*声明一个字符栈S2*/inti=0;/*i作为扫描数组E的指针*/intj=0;/*j用来指示数组A中待写入字符的位置*/charch=E[i];/*E中第一个字符送给ch*/charw='\0';InitStack（&S2）;/*初始化字符栈S2*/Rpush（&S2,'#'）;/*先把#压入栈内*/while（ch!='#'）/*当ch取得的元素不是#*/{if（ch>='0'&&ch<='9'||ch=='.'）/*若取得的元素为0到9或者是小数点*/{while（ch>='0'&&ch<='9'||ch=='.'）{A[j]=ch;/*将获得的元素赋予A数组*/j++;i++;ch=E[i];}A[j]='';j++;/*给A中的每个操作数后附加一个空格*/}if（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='（'||ch=='）'||ch=='#'）{GetTop（S2,&w）;/*取S2的栈顶元素*/while（Precede（w,ch）=='>'）/*栈顶操作符w比取得的操作符ch的优先级大*/{A[j]=w;/*将w赋予数组A*/j=j+1;Rpop（&S2）;/*将栈顶操作符w出栈*/GetTop（S2,&w）;/*取得的操作符入栈*/}if（Precede（w,ch）=='<'）/*栈顶操作符w比取得的操作符ch的优先级小*/Rpush（&S2,ch）;/*取得的操作符直接入栈*/else{if（Precede（w,ch）=='='&&w!='#'）/*栈顶操作符w与取得的操作符ch的优先级相等*/{Rpop（&S2）;/*将栈顶操作符w出栈*/GetTop（S2,&w）;/*观察栈顶操作符*/}}}if（E[i]!='#'）/*若取得的字符不是#i加1*/i++;ch=E[i];/*将从E数组取出的元素赋予ch*/}while（w!='#'）/*取得的操作符不是#*/{A[j]=w;/*将操作符赋予A数组*/j++;Rpop（&S2）;/*S2栈顶元素出栈*/GetTop（S2,&w）;/**/}A[j]='#';A[++j]='\0';}doubleCalc（chararr[]）/*计算后缀表达式的值*/{StackDs;/*声明一个数值栈s*/inti=0;charch;doublex=0,d=1.0;DsInit（&s）;/*初始化数值栈s*/ch=arr[i];while（ch!='#'）{switch（ch）/*switch语句用于读取字符串中的数值部分*/{case'0':case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':case'.':while（ch!=''）/*取得的字符不为空*/{if（'0'<=ch&&ch<='9'）{while（'0'<=ch&&ch<='9'）/*每读到一个整数部分就*10*/{x=x*10+（ch-'0'）;i=i+1;ch=arr[i];}}else{if（ch=='.'）{ch=arr[++i];while（'0'<=ch&&ch<='9'）/*每读到一个小数部分就/10*/{d=d*10;x=x+（ch-'0'）/d;ch=arr[++i];/*读取数组中下一个元素*/}}}}break;case'+':/*若取得的字符为+从数值栈取两个元素进行+运算*/x=Dpop（&s）+Dpop（&s）;break;case'-':/*若取得的字符为-从数值栈取两个元素进行-运算*/x=Dpop（&s）;x=Dpop（&s）-x;break;case'*':/*若取得的字符为*从数值栈取两个元素进行*运算*/x=Dpop（&s）*Dpop（&s）;break;case'/':x=Dpop（&s）;x=Dpop（&s）/x;break;case'%':x=Dpop（&s）;x=（double）（（int）Dpop（&s）%（int）x）;break;}Dpush（&s,x）;/*将x中压入数值栈*/x=0;/*将x置零*/i=i+1;ch=arr[i];/*取数组中下一个元素赋予ch*/d=1.0;}returnDpop（&s）;}voidmain（）/*主函数*/{charE[100];/*声明一个长度为100的数组E*/charA[100];/*声明一个长度为100的数组A*/printf（"Pleaseinputtheinfixexpresswitha'#'intheend:"）;gets（E）;/*获取E数组中的表达式*/change（E,A）;/*调用中缀表达式转后缀表达式的函数*/printf（"Thesurffixexpressis:%s\n",A）;/*输出后缀表达式*/printf（"Theresultis:%s=%f\n",E,Calc（A））;/*调用计算后缀表达式的函数并将值输出*/getchar（）;}下面给出的是用中缀表达式直接进行入栈计算算法实现的程序的源代码：#include#include#includetypedefstruct/*声明操作符结构体*/{charop;/*声明操作符类型*/charlevel;/*声明操作符优先级*/}opNode;typedefunion{opNodeopNode;/*声明操作符*/doublevalue;/*声明value数值为double型*/}Node;typedefstruct/*声明栈的结构体*/{charleixing;/*声明一个字符型sort*/Node*a[100];/*指定数组大小为100*/inttop;/*声明栈顶*/}Stack;Stack*init_sta（）/*初始化栈*/{inti;Stack*s=（Stack*）malloc（sizeof（Stack））;/*分配一个类型为Stack的结点变量的空间，空间大小为sizeof（Stack）,并将首地址放入指针变量s中*/s->top=0;for（i=0;i<100;i++）/*遍历栈全为空则栈为空*/s->a[i]=NULL;returns;}char*substr（char*s,intn1,intn2）/*截取子串函数*/{char*ss=（char*）malloc（sizeof（char）*（n2-n1+2））;/*分配空间，空间大小为n2-n1+2,并将首地址放入指针变量ss中*/inti,j=0;for（i=n1;i{ss[j++]=s[i];}ss[j]='\0';/*字符串后面加上'0'*/returnss;}intempty（Stack*ss）/*判空函数*/{returnss->top;/*返回栈顶元素*/}Node*Top（Stack*ss）/*观察栈顶函数*/{if（ss->top<=0）/*若栈顶为空，返回0*/{return0;}else/*若栈顶不为空，返回栈顶元素*/{returnss->a[ss->top-1];}}Node*Pop（Stack*ss）/*出栈函数*/{if（ss->top<=0）/*栈顶为空，返回0*/{return0;}else/*否则，栈顶元素出栈*/{ss->top--;returnss->a[ss->top];}}voidPush（Stack*p,Node*n）/*进栈函数*/{Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间，空间大小为sizeof（Node）,并将首地址放入指针变量temp中*/if（p->top>=100）/*判定栈是否已满*/{printf（"Error!TheStackisfull!\n"）;free（temp）;}else{if（p->leixing==1）/*sort为1，指向的为操作符栈，表明temp为操作符*/{temp->opNode.level=n->opNode.level;temp->opNode.op=n->opNode.op;}else/*sort为2指向的是数值栈，表明temp为数值*/temp->value=n->value;p->a[p->top]=temp;p->top=p->top+1;}}doublecalc（charop,doublem,doublen）/*每出栈一个操作符，就进行一次运算*/{switch（op）{case'+':returnn+m;case'-':returnn-m;case'*':returnn*m;case'/':returnn/m;case'%':return（int）n%（int）m;/*计算结束后，返回计算结果*/}return0;}voidmath（char*exp）/*处理函数*/{Node*top;/*声明栈顶*/Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量temp中*/Node*tempn=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量tempn中*/Node*tempm;/*声明一个tempm结点指针*/charc;char*temps="";unsignedintindex=0,tempindex;/*声明一个索引和一个临时索引*/doublea,b;Stack*s1=init_sta（）;/*初始化栈s1*/Stack*s2=init_sta（）;/*初始化栈s2*/s1->leixing=2;/*s1的类型为2，栈为数值栈*/s2->leixing=1;/*s2的类型为1，栈为操作符栈*/while（index{c=exp[index];if（c>='0'&&c<='9'||c=='.'）/*读取表达式中的各个数值*/{tempindex=index+1;while（tempindex='0'&&exp[tempindex]<='9'||exp[tempindex]=='.'））{tempindex++;/*当一个数没有读完，索引后移，直至整个数读完*/}if（tempindex==strlen（exp）-1）/*当临时索引到达表达式的尾部时，直接截取*/{temps=substr（exp,index,index+1）;}else{temps=substr（exp,index,tempindex）;}index=tempindex;/*索引指向临时索引所在位置*/temp->value=atof（temps）;/*将截取的子串转化为double类型*/Push（s1,temp）;/*将转化后的数压入数值栈*/}if（c=='+'||c=='-'）/*字符为+或者-时*/{tempn->opNode.op=c;tempn->opNode.level=1;/*设置优先级为1*/top=Top（s2）;while（empty（s2）>0&&tempn->opNode.level<=top->opNode.level）/*操作符栈不为空，并且栈顶操作符优先级高于或者等于当前操作符*/{tempm=Pop（s2）;/*操作符栈顶操作符出栈*/a=Pop（s1）->value;/*数值栈栈顶出来两个数*/b=Pop（s1）->value;temp->value=calc（tempm->opNode.op,a,b）;/*两个数进行运
s->top=s->top+1;/*若栈不满，将e进展*/
return0;/*若栈判定为满，返回0*/
ElemTypeRpop（StackR*s）/*出栈*/
ElemTypee;
intGetTop（StackRs,ElemType*e）/*取栈顶元素*/
if（0==s.top）/*若栈顶元素为空，返回0*/
*e=s.data[s.top];
*e=s.data[s.top];/*指针e指向栈顶元素*/
intCalcare（intmode,charoper）/*比较优先级*/
{/*返回操作符oper代表优先级得整数值，mode为1，表示oper是栈顶操作符，否则是当前操作符*/
inttmp;/*定义一个临时变量tmp*/
switch（oper）
case'#':
tmp=0;break;
case'（':
tmp=（mode?
1:
6）;break;
case'+':
case'-':
3:
2）;break;
case'*':
case'%':
case'/':
5:
4）;break;
case'）':
7:
1）;break;
returntmp;/*将所得的tmp返回*/
charPrecede（charw,charch）/*判定操作符栈的栈顶操作符w,与当前操作符ch之间的优先关系*/
intgrade;/*取得栈顶操作符与当前操作符得优先级*/
grade=Calcare（1,w）-Calcare（0,ch）;/*计算取得操作符与当前操作符的差值*/
if（grade>0）
return'>';
if（grade==0）/*说明取得操作符和当前操作符相等*/
return'=';
return'<';
voidchange（charE[],charA[]）/*中缀变后缀的实现函数E为原来的前缀表达式A为要转化成的后缀表达式*/
StackRS2;/*声明一个字符栈S2*/
inti=0;/*i作为扫描数组E的指针*/
intj=0;/*j用来指示数组A中待写入字符的位置*/
charch=E[i];/*E中第一个字符送给ch*/
charw='\0';
InitStack（&S2）;/*初始化字符栈S2*/
Rpush（&S2,'#'）;/*先把#压入栈内*/
while（ch!
='#'）/*当ch取得的元素不是#*/
if（ch>='0'&&ch<='9'||ch=='.'）/*若取得的元素为0到9或者是小数点*/
while（ch>='0'&&ch<='9'||ch=='.'）
A[j]=ch;/*将获得的元素赋予A数组*/
j++;
i++;
ch=E[i];
A[j]='';
j++;/*给A中的每个操作数后附加一个空格*/
if（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='%'||ch=='（'||ch=='）'||ch=='#'）
GetTop（S2,&w）;/*取S2的栈顶元素*/
while（Precede（w,ch）=='>'）/*栈顶操作符w比取得的操作符ch的优先级大*/
A[j]=w;/*将w赋予数组A*/
j=j+1;
Rpop（&S2）;/*将栈顶操作符w出栈*/
GetTop（S2,&w）;/*取得的操作符入栈*/
if（Precede（w,ch）=='<'）/*栈顶操作符w比取得的操作符ch的优先级小*/
Rpush（&S2,ch）;/*取得的操作符直接入栈*/
if（Precede（w,ch）=='='&&w!
='#'）/*栈顶操作符w与取得的操作符ch的优先级相等*/
GetTop（S2,&w）;/*观察栈顶操作符*/
if（E[i]!
='#'）/*若取得的字符不是#i加1*/
ch=E[i];/*将从E数组取出的元素赋予ch*/
while（w!
='#'）/*取得的操作符不是#*/
A[j]=w;/*将操作符赋予A数组*/
Rpop（&S2）;/*S2栈顶元素出栈*/
GetTop（S2,&w）;/**/
A[j]='#';
A[++j]='\0';
doubleCalc（chararr[]）/*计算后缀表达式的值*/
StackDs;/*声明一个数值栈s*/
inti=0;
charch;
doublex=0,d=1.0;
DsInit（&s）;/*初始化数值栈s*/
ch=arr[i];
='#'）
switch（ch）/*switch语句用于读取字符串中的数值部分*/
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9':
case'.':
=''）/*取得的字符不为空*/
if（'0'<=ch&&ch<='9'）
while（'0'<=ch&&ch<='9'）/*每读到一个整数部分就*10*/
x=x*10+（ch-'0'）;
i=i+1;
if（ch=='.'）
ch=arr[++i];
while（'0'<=ch&&ch<='9'）/*每读到一个小数部分就/10*/
d=d*10;
x=x+（ch-'0'）/d;
ch=arr[++i];/*读取数组中下一个元素*/
break;
/*若取得的字符为+从数值栈取两个元素进行+运算*/
x=Dpop（&s）+Dpop（&s）;
/*若取得的字符为-从数值栈取两个元素进行-运算*/
x=Dpop（&s）;
x=Dpop（&s）-x;
/*若取得的字符为*从数值栈取两个元素进行*运算*/
x=Dpop（&s）*Dpop（&s）;
x=Dpop（&s）/x;
x=（double）（（int）Dpop（&s）%（int）x）;
Dpush（&s,x）;/*将x中压入数值栈*/
x=0;/*将x置零*/
ch=arr[i];/*取数组中下一个元素赋予ch*/
d=1.0;
returnDpop（&s）;
voidmain（）/*主函数*/
charE[100];/*声明一个长度为100的数组E*/
charA[100];/*声明一个长度为100的数组A*/
printf（"Pleaseinputtheinfixexpresswitha'#'intheend:
"）;
gets（E）;/*获取E数组中的表达式*/
change（E,A）;/*调用中缀表达式转后缀表达式的函数*/
printf（"Thesurffixexpressis:
%s\n",A）;/*输出后缀表达式*/
printf（"Theresultis:
%s=%f\n",E,Calc（A））;/*调用计算后缀表达式的函数并将值输出*/
getchar（）;
下面给出的是用中缀表达式直接进行入栈计算算法实现的程序的源代码：
typedefstruct/*声明操作符结构体*/
charop;/*声明操作符类型*/
charlevel;/*声明操作符优先级*/
}opNode;
typedefunion
opNodeopNode;/*声明操作符*/
doublevalue;/*声明value数值为double型*/
}Node;
typedefstruct/*声明栈的结构体*/
charleixing;/*声明一个字符型sort*/
Node*a[100];/*指定数组大小为100*/
inttop;/*声明栈顶*/
}Stack;
Stack*init_sta（）/*初始化栈*/
inti;
Stack*s=（Stack*）malloc（sizeof（Stack））;/*分配一个类型为Stack的结点变量的空间，空间大小为sizeof（Stack）,并将首地址放入指针变量s中*/
s->top=0;
for（i=0;i<100;i++）/*遍历栈全为空则栈为空*/
s->a[i]=NULL;
returns;
char*substr（char*s,intn1,intn2）/*截取子串函数*/
char*ss=（char*）malloc（sizeof（char）*（n2-n1+2））;/*分配空间，空间大小为n2-n1+2,并将首地址放入指针变量ss中*/
inti,j=0;
for（i=n1;i{ss[j++]=s[i];}ss[j]='\0';/*字符串后面加上'0'*/returnss;}intempty（Stack*ss）/*判空函数*/{returnss->top;/*返回栈顶元素*/}Node*Top（Stack*ss）/*观察栈顶函数*/{if（ss->top<=0）/*若栈顶为空，返回0*/{return0;}else/*若栈顶不为空，返回栈顶元素*/{returnss->a[ss->top-1];}}Node*Pop（Stack*ss）/*出栈函数*/{if（ss->top<=0）/*栈顶为空，返回0*/{return0;}else/*否则，栈顶元素出栈*/{ss->top--;returnss->a[ss->top];}}voidPush（Stack*p,Node*n）/*进栈函数*/{Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间，空间大小为sizeof（Node）,并将首地址放入指针变量temp中*/if（p->top>=100）/*判定栈是否已满*/{printf（"Error!TheStackisfull!\n"）;free（temp）;}else{if（p->leixing==1）/*sort为1，指向的为操作符栈，表明temp为操作符*/{temp->opNode.level=n->opNode.level;temp->opNode.op=n->opNode.op;}else/*sort为2指向的是数值栈，表明temp为数值*/temp->value=n->value;p->a[p->top]=temp;p->top=p->top+1;}}doublecalc（charop,doublem,doublen）/*每出栈一个操作符，就进行一次运算*/{switch（op）{case'+':returnn+m;case'-':returnn-m;case'*':returnn*m;case'/':returnn/m;case'%':return（int）n%（int）m;/*计算结束后，返回计算结果*/}return0;}voidmath（char*exp）/*处理函数*/{Node*top;/*声明栈顶*/Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量temp中*/Node*tempn=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量tempn中*/Node*tempm;/*声明一个tempm结点指针*/charc;char*temps="";unsignedintindex=0,tempindex;/*声明一个索引和一个临时索引*/doublea,b;Stack*s1=init_sta（）;/*初始化栈s1*/Stack*s2=init_sta（）;/*初始化栈s2*/s1->leixing=2;/*s1的类型为2，栈为数值栈*/s2->leixing=1;/*s2的类型为1，栈为操作符栈*/while（index{c=exp[index];if（c>='0'&&c<='9'||c=='.'）/*读取表达式中的各个数值*/{tempindex=index+1;while（tempindex='0'&&exp[tempindex]<='9'||exp[tempindex]=='.'））{tempindex++;/*当一个数没有读完，索引后移，直至整个数读完*/}if（tempindex==strlen（exp）-1）/*当临时索引到达表达式的尾部时，直接截取*/{temps=substr（exp,index,index+1）;}else{temps=substr（exp,index,tempindex）;}index=tempindex;/*索引指向临时索引所在位置*/temp->value=atof（temps）;/*将截取的子串转化为double类型*/Push（s1,temp）;/*将转化后的数压入数值栈*/}if（c=='+'||c=='-'）/*字符为+或者-时*/{tempn->opNode.op=c;tempn->opNode.level=1;/*设置优先级为1*/top=Top（s2）;while（empty（s2）>0&&tempn->opNode.level<=top->opNode.level）/*操作符栈不为空，并且栈顶操作符优先级高于或者等于当前操作符*/{tempm=Pop（s2）;/*操作符栈顶操作符出栈*/a=Pop（s1）->value;/*数值栈栈顶出来两个数*/b=Pop（s1）->value;temp->value=calc（tempm->opNode.op,a,b）;/*两个数进行运
ss[j++]=s[i];
ss[j]='\0';/*字符串后面加上'0'*/
returnss;
intempty（Stack*ss）/*判空函数*/
returnss->top;/*返回栈顶元素*/
Node*Top（Stack*ss）/*观察栈顶函数*/
if（ss->top<=0）/*若栈顶为空，返回0*/
else/*若栈顶不为空，返回栈顶元素*/
returnss->a[ss->top-1];
Node*Pop（Stack*ss）/*出栈函数*/
if（ss->top<=0）/*栈顶为空，返回0*/
else/*否则，栈顶元素出栈*/
ss->top--;
returnss->a[ss->top];
voidPush（Stack*p,Node*n）/*进栈函数*/
Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间，空间大小为sizeof（Node）,并将首地址放入指针变量temp中*/
if（p->top>=100）/*判定栈是否已满*/
printf（"Error!
TheStackisfull!
\n"）;
free（temp）;
if（p->leixing==1）/*sort为1，指向的为操作符栈，表明temp为操作符*/
temp->opNode.level=n->opNode.level;
temp->opNode.op=n->opNode.op;
else/*sort为2指向的是数值栈，表明temp为数值*/
temp->value=n->value;
p->a[p->top]=temp;
p->top=p->top+1;
doublecalc（charop,doublem,doublen）/*每出栈一个操作符，就进行一次运算*/
switch（op）
returnn+m;
returnn-m;
returnn*m;
returnn/m;
return（int）n%（int）m;/*计算结束后，返回计算结果*/
voidmath（char*exp）/*处理函数*/
Node*top;/*声明栈顶*/
Node*temp=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量temp中*/
Node*tempn=（Node*）malloc（sizeof（Node））;/*分配空间,并将首地址放入指针变量tempn中*/
Node*tempm;/*声明一个tempm结点指针*/
charc;
char*temps="";
unsignedintindex=0,tempindex;/*声明一个索引和一个临时索引*/
doublea,b;
Stack*s1=init_sta（）;/*初始化栈s1*/
Stack*s2=init_sta（）;/*初始化栈s2*/
s1->leixing=2;/*s1的类型为2，栈为数值栈*/
s2->leixing=1;/*s2的类型为1，栈为操作符栈*/
while（index{c=exp[index];if（c>='0'&&c<='9'||c=='.'）/*读取表达式中的各个数值*/{tempindex=index+1;while（tempindex='0'&&exp[tempindex]<='9'||exp[tempindex]=='.'））{tempindex++;/*当一个数没有读完，索引后移，直至整个数读完*/}if（tempindex==strlen（exp）-1）/*当临时索引到达表达式的尾部时，直接截取*/{temps=substr（exp,index,index+1）;}else{temps=substr（exp,index,tempindex）;}index=tempindex;/*索引指向临时索引所在位置*/temp->value=atof（temps）;/*将截取的子串转化为double类型*/Push（s1,temp）;/*将转化后的数压入数值栈*/}if（c=='+'||c=='-'）/*字符为+或者-时*/{tempn->opNode.op=c;tempn->opNode.level=1;/*设置优先级为1*/top=Top（s2）;while（empty（s2）>0&&tempn->opNode.level<=top->opNode.level）/*操作符栈不为空，并且栈顶操作符优先级高于或者等于当前操作符*/{tempm=Pop（s2）;/*操作符栈顶操作符出栈*/a=Pop（s1）->value;/*数值栈栈顶出来两个数*/b=Pop（s1）->value;temp->value=calc（tempm->opNode.op,a,b）;/*两个数进行运
c=exp[index];
if（c>='0'&&c<='9'||c=='.'）/*读取表达式中的各个数值*/
tempindex=index+1;
while（tempindex='0'&&exp[tempindex]<='9'||exp[tempindex]=='.'））
tempindex++;/*当一个数没有读完，索引后移，直至整个数读完*/
if（tempindex==strlen（exp）-1）/*当临时索引到达表达式的尾部时，直接截取*/
temps=substr（exp,index,index+1）;
temps=substr（exp,index,tempindex）;
index=tempindex;/*索引指向临时索引所在位置*/
temp->value=atof（temps）;/*将截取的子串转化为double类型*/
Push（s1,temp）;/*将转化后的数压入数值栈*/
if（c=='+'||c=='-'）/*字符为+或者-时*/
tempn->opNode.op=c;
tempn->opNode.level=1;/*设置优先级为1*/
top=Top（s2）;
while（empty（s2）>0&&tempn->opNode.level<=top->opNode.level）/*操作符栈不为空，并且栈顶操作符优先级高于或者等于当前操作符*/
tempm=Pop（s2）;/*操作符栈顶操作符出栈*/
a=Pop（s1）->value;/*数值栈栈顶出来两个数*/
b=Pop（s1）->value;
temp->value=calc（tempm->opNode.op,a,b）;/*两个数进行运
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2
升级会员 