语言数据结构实验报告表达式的转换参考Word

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

2、(7) 结束 4、本程序能将中缀表达式转换为后缀表达式，并且能计算表达式的值。 5、输入及输出示例： 例1: 请输入表达式 6+3* (6+5) 后缀表达式：6 3 6 5 + * + 计算结果为：39 Press any key to continue 例2： 请输入表达式 6-3* (7+1 ERROR:表达式错误 Press any key to continue 二概要设计 1. 基本操作 (1) 、 struct node 操作结果：创建结构体 (2) int Searchexpression (char stringl) 初始条件:表达式string 1已经存在。 操作结果：判断表

3、达式是否非法 (3) 、struct node Mnitialization() 操作结果：创建栈链。 (4) 、 struct node assort(struct node *s) 初始条件:stringl、string2已存在。 操作结果：将中缀表达式转换为后缀表达式并存在string2中。 如不慎侵犯了你的权奋 (5) 、 struct node *calcolate(struct node *s) 操作结果：求出表达式的值 2、模块调用图 主程序模块 创建结构体 判断表达式是否非法 将中缀表达式转换为后缀表达式 表达式求值 三详细设计 K每个模块： (1) 定义结构体 struct

4、node char data; int num; struct node *next; ; (2) 判断表达式是否非法 int Searchexpression(char stringl) int il, bl, b2; int m; m=strlen (stringl); if (stringl 0 9) printf (ERROR:表达式缺操作数！ n);return (WRONG); for (il二0;il=m;il+) if (stringl il二二() bl+; else if (stringlil=，) b2+; if(bl!=b2) printf (ERROR：缺少括号n)

5、;return(OONG) ; for (il=0;ilm;il+) if ( O二stringl il：return (WRONG) ; for(il=0;il=m;il+) if (stringlil=+ return (WRONG) ; else if (stringl il=-(stringl il+l=+ i : stringl il+l=- | | stringlil+l=, stringlil+l=, /) printf (ERROR：表达式缺操作数！ n) ; return (WRONG) ; else if (stringl(stringl il+l=+ I； stringl

6、 il+l=- | | stringlil+l=, * stringlil+l=, /) printf (ERROR:表达式缺操作数！ n);return(WRONG); else if (stringl il=,/*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(stringl); for (i=0;i=m;i+) a=stringli; i

7、f ( 0J =stringl ip-next=top; top二p; break; case : case /: string2j二;j+; if (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; case +: case ： string2j二；j+; if(top-data

8、=，j Itop-data=，j j top-data=，j Itop-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; case ): string2j=, ；j+； if (top-data=,) printf (，zinput error) :break; while(top-data!=,(，) string2j二top-data;j

9、+; 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-next; free(p); string2j=, if ; printf C后缀表达式为:”)； for(i=0;ij;i+) 辻(string2il !=,) printf(%c “, string2i); printf(n “); return top; (4) 表达式求值 struct node *calcolate(struct node *s

10、) struct node *top, *p; 如不慎侵犯了你的权益.请联系我们告知! char *q; int x, y, a; int i, n; top二s;/指向栈顶的指针 for (i=0; i=, O for(n=i;string2n= O p-next=top;top=p; i=n-l; else if(string2i=#)遇#号结束标志，输出栈中的最后计 算结果 printf C计算结果为：%dn, top-num); else 辻(string2i=， ) else y=top-num;p=top;top=top-next;free(p); x=top-num;p=top;

11、top二top-next;free(p); switch(string2il) 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 : a=x*y; p= (struct node *)nialloc(sizeof (struct node ); p-num=a

12、;p-next二top;top二p; break; case / : 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 C请输入表达式：n); gets(stringl); if(Searchex

13、pression(stringl) head二assort (top) ;/中缀转化为后缀表达式 calcolate(head); 2、完整函数 ncludestdio. h ncludemalloc h ncludestring h ncludestdlib h ttdefine MAX 60 define RIGHT 1 define WRONG 0 iidefine DEMAX 15 define NULL 0 char stringlMAX; char string2MAX; int j二0; struct node /定义结构体。 char data; int num; struct

14、 node *next; ; 判断非法表达式 int Searchexpression(char stringl ) int il, bl, b2; int m; m=strlen (stringl); 如不慎侵犯了你的权益，请联系我们告知！ 辻(stringl0O stringl09) printf (ERROR：表达式缺操作数！ n) ; return (WRONG); for(il=0;il=m;il+) if (stringlil=() bl+; else 辻(stringl il=，) b2+; if(bl!=b2) printf (ERROR：缺少括号 n) ; return (W

15、RONG) ; for(il=0;ilm;il+) 辻(0? =stringlil for(il=0;ilda ； top-num二0; top-next二NULL; return top; i struct node * assort (struct node *s)/输入字符串 struct node *p,*top; int i; top二s; int m; char a; m=strlen(stringl); for (i=0;idata=a;p-next二top; top二p; break; case : case P : string2j=, ;j+; if (top-data=,

16、 ) I ! (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; case +: case string2j=, ;j+; if (top-data=, + top-data=, - top-data=,top-data=, ) string2j=top-data;j+; top-data=a; brea

17、k; else 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-next;free (p); break; while(top-data!=, ，) string2j二top-data

18、;j+; P=top; top二top-next; free(p); string2j二; printff后缀表达式为：)； for(i=0;ij;i+) if(string2i) printf (z，%c /z, string2il); printf Cn “)； 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=, O n+) p= (struct node *

19、)malloc(sizeof(struct node ); p-num:=a; p-next=top; to p二p; i二n-1; else 辻(string2i二三半)/遇#号结束标志，输出栈中的最后计算结 printf (z/ir算结果为:%dn，z, top-num); else 辻(string2i=, ) else y二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=(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 *)mal