将中缀表达式转换为后缀表达式并计算

1、数据结构实验报告实验题目: 使用键盘输入表达式，计算表达式的值并输出；将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。实验目的：使用栈的操作编写关于数据结构的程序。实验内容：写出程序并上机调试、通过。一、需求分析1、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“请输入表达式”时输入中缀表达式。然后计算机终端输出转换后的后缀表达式及计算后的结果。2、程序执行的命令包括：（1）构造链栈；（2）输入数据；（3）判断输入的表达式是否为非法表达式；（4）将中缀表达式转换为后缀表达式；（5）计算表达式的值；（6）输出。（7）结束4、本程序能将中缀表达式转换为后缀表达式，并且能

2、计算表达式的值。5、输入及输出示例：例1：请输入表达式6+3*（6+5）后缀表达式：6 3 6 5 + * +计算结果为：39Press any key to continue 例2：请输入表达式6-3*（7+1ERROR:表达式错误Press any key to continue 二 概要设计1基本操作(1)、struct node操作结果：创建结构体(2)、int Searchexpression(char string1)初始条件：表达式string1已经存在。操作结果：判断表达式是否非法(3)、struct node *Initialization()操作结果：创建栈链。(4)、st

3、ruct node *assort(struct node *s)初始条件：string1、string2已存在。操作结果：将中缀表达式转换为后缀表达式并存在string2中。(5)、struct node *calcolate(struct node *s)操作结果：求出表达式的值2、模块调用图主程序模块创建结构体判断表达式是否非法将中缀表达式转换为后缀表达式表达式求值三 详细设计1、每个模块：(1) 定义结构体struct node char data;int num;struct node *next; (2) 判断表达式是否非法int Searchexpression(char str

4、ing1) int i1,b1,b2;int m;m=strlen(string1);if(string10<'0'|string10>'9')printf("ERROR:表达式缺操作数！n");return(WRONG);for(i1=0;i1<=m;i1+)if(string1i1='(')b1+;elseif(string1i1=')')b2+;if(b1!=b2)printf("ERROR:缺少括号n");return(WRONG);for(i1=0;i1<m

5、;i1+)if('0'<=string1i1&&string1i1<='9'&&'0'<=string1i1+1&&string1i1+1<='9') printf("ERROR:表达式缺操作符！n");return(WRONG);for(i1=0;i1<=m;i1+)if(string1i1='+'&&(string1i1+1='+'|string1i1+1='-'|s

6、tring1i1+1='*'|string1i1+1='/') printf("ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1='-'&&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/') printf("ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1

7、='*'&&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/')printf("ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1='/'&&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/&#

8、39;)printf("ERROR:表达式缺操作数！n");return(WRONG);return(RIGHT); (3)、将中缀表达式转换为后缀表达式struct node *assort(struct node *s)/输入字符串struct node *p,*top;int i;top=s;int m;char a;m=strlen(string1); for(i=0;i<=m;i+)a=string1i;if('0'<=string1i&&string1i<='9')string2j=string1

9、i;j+;elseswitch(a)case '(':p=(struct node *)malloc(sizeof(struct node);p->data=a;p->next=top;top=p;break; case '*':case '/':string2j=' 'j+;if(top->data='*')|(top->data='/')string2j=top->data;j+; /比其高，现将栈顶运算符出栈，再进栈。top->data=a;break;el

10、sep=(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+;top->data=a;break;e

11、lse 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->

12、next;free(p);break;while(top->data!='')string2j=top->data;j+;p=top;top=top->next;free(p);string2j='#'printf("后缀表达式为:");for(i=0;i<j;i+)if(string2i!=' ')printf("%c ",string2i);printf("n ");return top; (4)表达式求值struct node *calcolate(stru

13、ct node *s)struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i<=j;i+)/遍历字符串string2if(string2i>='0'&&string2i<='9')q=&string2i;a=atoi(q); for(n=i;string2n>='0'&&string2n<='9'n+)p=(struct node *)malloc(sizeof(struct n

14、ode );p->num=a;p->next=top;top=p;i=n-1;elseif(string2i='#') /遇#号结束标志，输出栈中的最后计算结果printf("计算结果为:%dn",top->num);elseif(string2i=' ')elsey=top->num;p=top;top=top->next;free(p);x=top->num;p=top;top=top->next;free(p);switch(string2i)case '+':a=x+y;p=(

15、struct node *)malloc(sizeof(struct node);p->num=a;p->next=top;top=p;break;case '-':a=x-y;p=(struct node *)malloc(sizeof(struct node );p->num=a;p->next=top;top=p;break;case '*':a=x*y;p=(struct node *)malloc(sizeof(struct node );p->num=a;p->next=top;top=p;break;case &

16、#39;/':if(y=0) printf("ERROR:除数为零!n");a=(float)x/y;p=(struct node *)malloc(sizeof(struct node );p->num=a;p->next=top;top=p;break;return 0;(5)、主函数void main()struct node *top,*head;top=Initialization();/建立一个链栈，并返回栈顶指针printf("请输入表达式：n");gets(string1);if(Searchexpression(st

17、ring1)head=assort(top);/中缀转化为后缀表达式calcolate(head);2、完整函数#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#define MAX 60#define RIGHT 1#define WRONG 0#define DEMAX 15#define NULL 0char string1MAX;char string2MAX;int j=0;struct node /定义结构体。char data;int nu

18、m;struct node *next;int Searchexpression(char string1) /判断非法表达式int i1,b1,b2;int m;m=strlen(string1);if(string10<'0'|string10>'9')printf("ERROR:表达式缺操作数！n");return(WRONG);for(i1=0;i1<=m;i1+)if(string1i1='(')b1+;elseif(string1i1=')')b2+;if(b1!=b2)print

19、f("ERROR:缺少括号n");return(WRONG);for(i1=0;i1<m;i1+)if('0'<=string1i1&&string1i1<='9'&&'0'<=string1i1+1&&string1i1+1<='9') printf("ERROR:表达式缺操作符！n");return(WRONG);for(i1=0;i1<=m;i1+)if(string1i1='+'&am

20、p;&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/') printf("ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1='-'&&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/') printf(&q

21、uot;ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1='*'&&(string1i1+1='+'|string1i1+1='-'|string1i1+1='*'|string1i1+1='/')printf("ERROR:表达式缺操作数！n");return(WRONG);elseif(string1i1='/'&&(string1i1+1='+'|string1i1+1

22、='-'|string1i1+1='*'|string1i1+1='/')printf("ERROR:表达式缺操作数！n");return(WRONG);return(RIGHT);struct node *Initialization()/初始化栈链,链栈不带头结点struct node *top;top=(struct node *)malloc(sizeof(struct node);top->data=''top->num=0;top->next=NULL;return top;str

23、uct node *assort(struct node *s)/输入字符串struct node *p,*top;int i;top=s;int m;char a;m=strlen(string1); for(i=0;i<=m;i+)a=string1i;if('0'<=string1i&&string1i<='9')string2j=string1i;j+;elseswitch(a)case '(':p=(struct node *)malloc(sizeof(struct node);p->data=

24、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;bre

25、ak;case '+':case '-':string2j=' 'j+;if(top->data='+'|top->data='-'|top->data='*'|top->data='/')string2j=top->data;j+;top->data=a;break;else p=(struct node *)malloc(sizeof(struct node);p->data=a;p->next=top;top=p;break; c

26、ase ')':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-&

27、gt;next;free(p);string2j='#'printf("后缀表达式为:");for(i=0;i<j;i+)if(string2i!=' ')printf("%c ",string2i);printf("n ");return top;struct node *calcolate(struct node *s)/计算表达式的值struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i<=j;i+)/

28、遍历字符串string2if(string2i>='0'&&string2i<='9')q=&string2i;a=atoi(q); for(n=i;string2n>='0'&&string2n<='9'n+)p=(struct node *)malloc(sizeof(struct node );p->num=a;p->next=top;top=p;i=n-1;elseif(string2i='#') /遇#号结束标志，输出栈中的最后计算结果printf("计算结果为:%dn",top->num);elseif(string2i=' ')elsey=top->num;p=top;top=top->next