中缀表达式求值实验报告
一、需求分析（要实现的功能描述）
1．问题描述：
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 2．实现功能：
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”。
算法运行：将输入的中缀表达式改为后缀表达式，并进行运算。 算法输出：输出后缀表达式和表达式运算结果。 3．测试数据：
（1）、1+3*4-（5/5）； 一位数运算 （2）、45-5*（1+2）/5; 多位数运算
二、概要设计
整个程序包含功能模块及模块间的调用关系
(1)、struct node 创建结构体，被主函数调用 (2)、struct node *Initialization() 创建栈链，被主函数调用
(3)、struct node *assort(struct node *s) 将中缀表达式转换为后缀表达式并存在s2中
被主函数调用
(4)、struct node *calcolate(struct node *s) 求出表达式的值，被主函数调用 (5)、void main() 主函数，调用所有函数
三、详细设计
抽象数据类型中定义的各种操作算法实现（用N-S 图描述）
四、调试分析
1．程序在调式过程中出现的问题及解决方法
一开始选用直接运算方式运用两个栈来存放数字和操作符，后来写着确实不行然后直接转用转为后缀表达式再进行计算。
在写将多位数（比如123*12）存放字符串中时，一开始我想着直接转换成数字存入数组中，但一直不成功，只能将第一个多位数转换成功；后来在和同学之间交流并且百度搜索后改为直接存入字符串中，再存入字符串过程中，我发现几个数字之间可能没法区分是前一个数字的还是后一个数字的，于是我在扫描字符串过程中在扫描到操作字符时将存入数字的那个字符串s2空出一位，用以区分前后两个数字，如12+45*，如果直接存入字符串中会是 s2：1245*+；但加空格后为s2：12（空格）45*+；这样后面运算时就好区分两多位数字。 ……… 2．心得体会
在写程序之前要选择适合自己的算法即自己熟悉的能编出的算法，这样后续的编程会简便多了。
对于一个要实现的功能，会有很多不同的算法，当你一个算法用不了时，可以换一个算法编程，目的是死的，人是活的，算法是活的，程序也是活的！
五、用户手册
该软件的操作方法简介
输入一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”，按回车结束输入。程序运行输出输出后缀表达式和表达式运算结果。
六、测试结果
根据已提供的测试数据得到什么样的结果（可以截屏） （1）、1+3*4-（5/5）；
（2）、45-5*（1+2）
/5;
七、程序清单
#include #include #include #include #define MAX 60 #define RIGHT 1 #define WRONG 0 #define DEMAX 15 #define NULL 0 char s1[MAX]; char s2[MAX]; int j=0;
struct node //定义结构体。 {
char data; int num;
struct node *next; };
struct node *Initialization()//初始化栈链, 链栈不带头结点 {
struct node *top;
top=(struct node *)malloc(sizeof(struct node)); top->data=';'; top->num=0;
top->next=NULL; return top; }
struct node *assort(struct node *s)//输入字符串 {
struct node *p,*top; int i; top=s; int m; char a;
m=strlen(s1);
for(i=0; i
a=s1[i];
if('0'
s2[j]=s1[i]; j++; } else
{
switch(a) {
case '(': {
p=(struct node *)malloc(sizeof(struct node)); p->data=a; p->next=top; top=p; break; }
case '*': case '/':
s2[j]=' '; j++;
if((top->data=='*')||(top->data=='/')) {
s2[j]=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 '-': {
s2[j]=' '; j++;
if(top->data=='+'||top->data=='-'||top->data=='*'||top->data=='/') {
s2[j]=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 ')': {
s2[j]=' '; j++;
if(top->data==';') {
printf("input error"); break; }
while(top->data!='(') {
s2[j]=top->data; j++; p=top;
top=top->next; free(p); }
p=top;
top=top->next; free(p); break; } } } }
while(top->data!=';') {
s2[j]=top->data; j++; p=top;
top=top->next; free(p); }
s2[j]=';';
printf("后缀表达式为:"); for(i=0; i
printf("%c ",s2[i]); 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
if(s2[i]>='0'&&s2[i]
q=&s2[i]; a=atoi(q);
for(n=i; s2[n]>='0'&&s2[n]num=a; p->next=top; top=p; i=n-1; }
else if(s2[i]==';') //遇；号结束标志，输出栈中的最后计算结果 printf("计算结果为:%d\n",top->num); else {
if(s2[i]==' ') {} else {
y=top->num; p=top;
top=top->next; free(p);
x=top->num; p=top;
top=top->next; free(p);
switch(s2[i]) {
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 *)malloc(sizeof(struct node )); p->num=a; p->next=top; top=p; break; }
case '/': {
a=(float)x/y;
p=(struct node *)malloc(sizeof(struct node )); p->num=a; p->next=top; top=p; break; } } } } }
return 0; }
void main() {
struct node *top,*head; top=Initialization();
printf("请输入表达式（运算符号可以为：+、-、*、/、(、) ）：\n"); gets(s1);
head=assort(top); calcolate(head);
}
中缀表达式求值实验报告
一、需求分析（要实现的功能描述）
1．问题描述：
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 2．实现功能：
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”。
算法运行：将输入的中缀表达式改为后缀表达式，并进行运算。 算法输出：输出后缀表达式和表达式运算结果。 3．测试数据：
（1）、1+3*4-（5/5）； 一位数运算 （2）、45-5*（1+2）/5; 多位数运算
二、概要设计
整个程序包含功能模块及模块间的调用关系
(1)、struct node 创建结构体，被主函数调用 (2)、struct node *Initialization() 创建栈链，被主函数调用
(3)、struct node *assort(struct node *s) 将中缀表达式转换为后缀表达式并存在s2中
被主函数调用
(4)、struct node *calcolate(struct node *s) 求出表达式的值，被主函数调用 (5)、void main() 主函数，调用所有函数
三、详细设计
抽象数据类型中定义的各种操作算法实现（用N-S 图描述）
四、调试分析
1．程序在调式过程中出现的问题及解决方法
一开始选用直接运算方式运用两个栈来存放数字和操作符，后来写着确实不行然后直接转用转为后缀表达式再进行计算。
在写将多位数（比如123*12）存放字符串中时，一开始我想着直接转换成数字存入数组中，但一直不成功，只能将第一个多位数转换成功；后来在和同学之间交流并且百度搜索后改为直接存入字符串中，再存入字符串过程中，我发现几个数字之间可能没法区分是前一个数字的还是后一个数字的，于是我在扫描字符串过程中在扫描到操作字符时将存入数字的那个字符串s2空出一位，用以区分前后两个数字，如12+45*，如果直接存入字符串中会是 s2：1245*+；但加空格后为s2：12（空格）45*+；这样后面运算时就好区分两多位数字。 ……… 2．心得体会
在写程序之前要选择适合自己的算法即自己熟悉的能编出的算法，这样后续的编程会简便多了。
对于一个要实现的功能，会有很多不同的算法，当你一个算法用不了时，可以换一个算法编程，目的是死的，人是活的，算法是活的，程序也是活的！
五、用户手册
该软件的操作方法简介
输入一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”，按回车结束输入。程序运行输出输出后缀表达式和表达式运算结果。
六、测试结果
根据已提供的测试数据得到什么样的结果（可以截屏） （1）、1+3*4-（5/5）；
（2）、45-5*（1+2）
/5;
七、程序清单
#include #include #include #include #define MAX 60 #define RIGHT 1 #define WRONG 0 #define DEMAX 15 #define NULL 0 char s1[MAX]; char s2[MAX]; int j=0;
struct node //定义结构体。 {
char data; int num;
struct node *next; };
struct node *Initialization()//初始化栈链, 链栈不带头结点 {
struct node *top;
top=(struct node *)malloc(sizeof(struct node)); top->data=';'; top->num=0;
top->next=NULL; return top; }
struct node *assort(struct node *s)//输入字符串 {
struct node *p,*top; int i; top=s; int m; char a;
m=strlen(s1);
for(i=0; i
a=s1[i];
if('0'
s2[j]=s1[i]; j++; } else
{
switch(a) {
case '(': {
p=(struct node *)malloc(sizeof(struct node)); p->data=a; p->next=top; top=p; break; }
case '*': case '/':
s2[j]=' '; j++;
if((top->data=='*')||(top->data=='/')) {
s2[j]=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 '-': {
s2[j]=' '; j++;
if(top->data=='+'||top->data=='-'||top->data=='*'||top->data=='/') {
s2[j]=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 ')': {
s2[j]=' '; j++;
if(top->data==';') {
printf("input error"); break; }
while(top->data!='(') {
s2[j]=top->data; j++; p=top;
top=top->next; free(p); }
p=top;
top=top->next; free(p); break; } } } }
while(top->data!=';') {
s2[j]=top->data; j++; p=top;
top=top->next; free(p); }
s2[j]=';';
printf("后缀表达式为:"); for(i=0; i
printf("%c ",s2[i]); 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
if(s2[i]>='0'&&s2[i]
q=&s2[i]; a=atoi(q);
for(n=i; s2[n]>='0'&&s2[n]num=a; p->next=top; top=p; i=n-1; }
else if(s2[i]==';') //遇；号结束标志，输出栈中的最后计算结果 printf("计算结果为:%d\n",top->num); else {
if(s2[i]==' ') {} else {
y=top->num; p=top;
top=top->next; free(p);
x=top->num; p=top;
top=top->next; free(p);
switch(s2[i]) {
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 *)malloc(sizeof(struct node )); p->num=a; p->next=top; top=p; break; }
case '/': {
a=(float)x/y;
p=(struct node *)malloc(sizeof(struct node )); p->num=a; p->next=top; top=p; break; } } } } }
return 0; }
void main() {
struct node *top,*head; top=Initialization();
printf("请输入表达式（运算符号可以为：+、-、*、/、(、) ）：\n"); gets(s1);
head=assort(top); calcolate(head);
}