数据结构大作业.doc

. . . .

电子与信息工程学院

数据结构大作业

系 别：电子与信息工程学院
班 级：
姓 名：
学 号：
指导教师：

数据结构实验报告
一、 实验目的
表达式求值。
一个算术表达式是由操作数、运算符和界限符组成。假设操作数是正整数，运算符只含加减乘除四种运算符，界限符有左右括号和表达式起始、完毕符“＃〞。要求从键盘读入一个合法的算术表达式，输出正确的结果，并显示输入序列。
二、数据结构设计
任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来存放表达式的操作数和运算符。栈是限定于紧仅在表尾进展插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设栈顶指针指示栈顶元素在顺序栈中的位置，栈底为栈底指针，在顺序栈中，它始终指向栈底，即栈顶指针=栈底指针可作为栈空的标记，每当插入新的栈顶元素时，栈顶指针增1，删除栈顶元素时，栈底指针减1。
三、总体设计
1.首先置操作数栈为空栈，表达式起始符〞#〞为运算符栈的栈底元素；
2.依次读入表达式，假设是操作符即进栈，假设是运算符那么和栈的栈顶运算符比拟优先权后作相应的操作，直至整个表达式求值完毕〔即栈的栈顶元素和当前读入的字符均为〞#〞〕。
四、主要界面
主界面

输入3+5#后：

输入〔3+2〕*〔4+1〕/2后：
五、心得体会
通过设计表达式求值这个程序，我学到了很多知识，对堆栈的应用更加熟练，也对程序设计有了新的看法。虽然设计过程当中遇到了很多困难，但我通过查资料，请教同学都一一成功的解决了，最总完成了他的设计，我感觉通过他我学到了很多。
六、附录源程序：
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <conio.h>
#define MAX 10 //定义堆栈最大容量
void push_opnd(char);//操作数堆栈入栈操作
float pop_opnd(); //操作数堆栈出栈操作
void push_optr(char);//操作符堆栈入栈操作
char pop_optr(); //操作符堆栈出栈操作
char relation(char,char);//比拟两个操作符的优先级
float operate(float,char,float);//运算
float opnd[MAX]; //操作数堆栈
char optr[MAX]; //操作符堆栈
int topd=0; //栈顶指针初始化
int top=0;
char symb[30]; //表达式字符串
int main()
{int i=0;
char sy;
float a,b;
printf("本程序实现表达式求值的操作。可以进展加减乘除运算。\n");
printf("这是堆栈应用的一个例子\n");
//----------------------------------------------------
printf("请输入表达式(以#完毕):\n例如: 3*(3+2)/5#\n");
push_optr('#');
gets(symb); //输入表达式，以#为完毕符
while((symb[i]!='#')||(optr[top]!='#'))
{if((symb[i]!='+')&&(symb[i]!='-')&&(symb[i]!='*')&&(symb[i]!='/')
&&(symb[i]!='(')&&(symb[i]!=')')&&(symb[i]!='#')&&(symb[i]!=' '))
{push_opnd(symb[i]);i++;} //如果当前字符不是操作符，那么入操作数栈，字符串指针加一
else switch(relation(optr[top],symb[i])) //假设是操作符，比拟其和操作符栈的栈顶元素的优先级
{case '<':push_optr(symb[i]);i++;break; //假设栈顶元素优先级低，那么当前字符入栈，指针加一
case '=':sy=pop_optr();i++; break; //假设优先级相等，必为两个配对的括号，退栈，指针加一
case '>':sy=pop_optr();b=pop_opnd(); //假设优先级高，那么栈顶元素退栈，进展运算
a=pop_opnd();
topd=topd+1;
opnd[topd]=operate(a,sy,b); //把运算结果入栈
break;
case ' ':printf("语法错误!\n");exit(0);
}
}
printf("运算结果=%1.2f\n",opnd[topd]);
printf("程序完毕，按任意键退出!\n");
getch();
}
void push_opnd(char ch)
{int ch_i;
ch_i=ch-'0'; //把字符换算成数字，并入操作数栈
topd++;
opnd[topd]=ch_i;
}
float pop_opnd()
{//操作数栈出栈
topd=topd-1;
return opnd[topd+1];
}
void push_optr(char ch)
{//操作符入栈
top++;
optr[top]=ch;
}
char pop_optr()
{//操作数出栈
top--;
return optr[top+1];
}
char relation(char sym1,char sym2)
{//比拟两个操作符的优先级
int i;
char chl[2];
int ind[2];
char re[7][7]={'>','>','<','<','<','>','>',
'>','>','<','<','<','>','>',
'>','>','>','>','<','>','>',
'>','>','>','>','<','>','>',
'<','<','<','<','<','=',' ',
'>','>','>','>',' ','>','>',
'<','<','<','<','<',' ','='};
chl[0]=sym1;
chl[1]=sym2;
for(i=0;i<=1;i++)
{switch(chl[i])
{case '+':ind[i]=0;break;
case '-':ind[i]=1;break;
case '*':ind[i]=2;break;
case '/':ind[i]=3;break;
case '(':ind[i]=4;break;
case ')':ind[i]=5;break;
case '#':ind[i]=6;break;
default:printf("Error!\n");return('0');
}
}
return(re[ind[0]][ind[1]]);
}
float operate(float a,char sym,float b)
{//进展运算
float re;
switch(sym)
{case '+':re=a+b;break;
case '-':re=a-b;break;
case '*':re=a*b;break;
case '/':re=a/b;break;
default:printf("Error!\n");return(0);
}
return re;
}
6 / 6