数据结构课程设计_表达式求值

1、XXXXXX大学数据结构课程设计报告班级：学号：姓名： 指导老师:算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数(operand)、运算符(operator)和界限符 (delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种 运算符，界限符有左右活号和表达式起始、结束符，如：# (7+15) * (23-28/4)引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。二、程序的主要功能(1) 从键盘读入一个合法的算术表达

2、式，输出正确的结果。(2) 显示输入序列和栈的变化过程。三、程序运行平台Visual C+ 6.0 版本四、数据结构木程序的数据结构为栈。(1)运算符栈部分：struct SqStack /定义栈char *base; 栈底指针char *top; 栈顶指针 int stacksize; 栈的长度;int InitStack (SqStack &s) /建立一个空栈 Sif (!(s.base = (char *)malloc(50 * sizeof(char) exit(O);s.top=s.base;s.stacksize=50;return OK;char GetTop(SqSt

3、ack s,char &e) 运算符取栈顶元素if (s.top=s.base) 栈为空的时候返回ERRORprintf运算符栈为空!n“)；return ERROR;elsee=*(s.top-1); 栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKint PushfSqStack &s,char e) /运算符入栈if (s.top-s.base >= s.stacksize)printtf*运算符栈满!rf);s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char); /栈满的时候, 追加5个存储空

4、间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e; 把 e 入栈return OK;int PopfSqStack &s,char &e) /运算符出栈if (s.top=s.base) 栈为空栈的时候，返回ERRORprint"运算符栈为空!rf);return ERROR;elsee=*-s.top; 栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OK return OK;int StackTraverse(SqStack &s) /运算符

5、栈的遍历char *t;t=s.base ;if (s.top=s.base)printf运算符栈为空!nj; /栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printfC* %c-7t); 栈不为空的时候依次取出栈内元素t+；(2)数字栈部分：struct SqStackn 定义数栈int *base; 栈底指针int *top; 栈顶指针int stacksize; 栈的长度;int InitStackn (SqStackn &s) /建立一个空栈 Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)

6、exit(OVERFLOW); /存储分配失败s.top=s.base;s.stacksize=50;return OK;int GetTopn(SqStackn s,int &e) /数栈取栈顶元素if (s.top=s.base)printf运算数栈为空!n“); /栈为空的时候返回ERRORreturn ERROR;elsee=*(s.top-1);/栈不为空的时候，用e作返回值,返回S的栈顶元素，并返回0K return OK;int Pushn(SqStackn &s,int e) /数栈入栈if (s.top-s.base >=s.stacksize)prin

7、ttf运算数栈满!nj; /栈满的时候，追加5个存储空间s.base=(intjrealloc (s.base,(s.stacksize+5)*sizeof(int);if(ls.base) exit (OVERFLOW);s.top=s.base+s.stacksize; 插入元素e为新的栈顶元素 s.stacksize+=5;*(s.top)+=e; /栈顶指针变化return OK;int Popn(SqStackn &s,int &e) 数栈出栈if (s.top=s.base)printff-运算符栈为空An”);/栈为空栈的视时候，返回ERRORreturn ERR

8、OR;elsee=*-s.top; 栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回 0Kreturn OK;int StackTraversen(SqStackn &s) /数栈遍历int *t;t=s.base ;if (s.top=s.base)print"运算数栈为空!rT);栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printfC* %d'*t); 栈不为空的时候依次输出t+；return ERROR;五、算法及时间复杂度1、算法:建立两个不同类型的空栈，先把一个'#'压入运算符栈。输入一个算

9、术表达式的字符串(以#结束)，从第一个字符依次向后读，把读取的数 字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶 得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后 两个#遇到一起则运算结束。数字栈顶的数字就是要求的结果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x) 出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是耗费在输 入操作。六、测试用例如图所示。最终结果如图所示:表达式结果是：- 66 本次运算结東。 继续

10、本糸统吗？継续运算请按丫勺 退由程序请按N/n七、源代码y* *w*笫七题算术表达式求值问题描述一个算术念达式是山操作数(operand)x运算符(operator)和界限符(delimiter)组成的。 假设操作数是止整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如:# (7+15) * (23-28/4) #。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求(1) 从键盘读入一个合法的算术表达式，输出正确的结果。(2) 显示输入序列和栈的变化过程。* /#include <stdio.h>include &l

11、t;string.h>include <stdlib.h>include <math.h>include vconio.h#include <ctype.h>#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100/#define STACKINCREMENT 10/=/以下定义两种栈，分别存放运算符和数字/=:=:/*运算符栈部分*struct SqStack /定义栈char *base; 栈底指针 char *top; 栈顶指针 int stacksize; 栈的长度int InitStack

12、(SqStack &s) /建立一个空栈 Sif (!(s.base = (char *)malloc(50 * sizeof(char)exit(O); s.top=s.base; s.stacksize=50; return OK;char GetTop(SqStack s,char &e) 运算符取栈顶元素if (s.top=s.base) 栈为空的时候返回ERRORprintf(”运算符栈为空!n“)； return ERROR;elsee=*(s.top-1); 栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OKreturn OK;int Push(SqStac

13、k &s,char e) /运算符入栈if (s.top-s.base >= s.stacksize)printf(”运算符栈满!rf);s.base=(cha广)realloc (s.base,(s.stacksize+5)*sizeof(char); /栈满的 时候，追加5个存储空间if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=5;*(s.top)+=e; 把 e 入栈return OK;int Pop(SqStack &s,char &e) /运算符出栈if (s.top=

14、s.base) 栈为空栈的时候，返回ERROR printf(”运算符栈为空!nj;return ERROR;elseeJ-s.top; 栈不为空的时候用e做返回值，删除S的栈顶元素，并返回OKreturn OK;int StackTraverse(SqStack &s) /运算符栈的遍历char *t;t=s.base ;if (s.top=s.base)printf(”运算符栈为空!n“)； 栈为空栈的时候返回ERRORreturn ERROR;while(t!=s.top)printf(M %cTt); /栈不为空的时候依次取出栈内元素 t+；return ERROR;y/w*w

15、ww*w*w*w*w*w* 娄攵f戈*struct SqStackn 定义数栈int *base; 栈底指针int *top; 栈顶指针int stacksize; 栈的长度;int InitStackn (SqStackn &s) 建立一个空栈 Ss.base=(int*)malloc(50*sizeof(int);if(!s.base)exit(OVERFLOW); /存储分配失败 s.top=s.base;s.stacksize=50;return OK;int GetTopn(SqStackn sjnt &e) /数栈取栈顶元素if (s.top=s.base)prin

16、tf(M运算数栈为空!nj; /栈为空的时候返回ERROR return ERROR;elseeJs.top-1);/栈不为空的时候，用e作返回值，返回S的栈顶元素，并返回OKreturn OK;int Pushn(SqStackn &s,int e) /数栈入栈if (s.top-s.base >=s.stacksize)printf("运算数栈满!n"); /栈满的时候，追加5个存储空间s.base=(intjrealloc (s.base1(s.stacksize+5)*sizeof(int);if(!s.base) exit (OVERFLOW);s.

17、top=s.base+sstacksize; 插入元素e为新的栈顶元素 s.stacksize+=5;*(s.top)+=e; 栈顶指针变化return OK;int Popn(SqStackn &s,int &e) /数栈出栈if (s.top=s.base)printfC'运算符栈为空!n”);栈为空栈的视时候，返回ERRORreturn ERROR;elsee=*-s.top; 栈不空的时候，则删除S的栈顶元素，用e返回其值，并返回OKreturn OK;int StackTraversen(SqStackn &s) /数栈遍历int *t;t=s.bas

18、e ;if (s.top=s.base)printf(M运算数栈为空!nH);/栈为空栈的时候返回ERROR return ERROR;while(t!=s.top)printf(M %d；*t);/栈不为空的时候依次输出t+；return ERROR;/=/以下定义函数int lsoperator(char ch) /判断是否为运算符，分别将运算符和数字进入不同的栈 switch (ch)case V:case case case 71: case (:case y：case #:return 1;default:return 0;int Operate(int a, char op, in

19、t b) /运算操作 int result;switch(op)case V:result=a+b; break;caseresult=a-b; break;caseresult=a*b; break; case T.result=a/b; break;return result;char Precede(char ch1, char ch2) /运算符优先级的比较 char p;switch(chl)if (ch2='+'|ch2=T|ch2=T|ch2=#)p = *>'/ch1运算符的优先级小于ch2运算符elseP = <；break;case ca

20、se T:if (ch2 =()P = <； elseP =break;case f:if (ch2 = T)P =else if (ch2 = #)printf(n表达式错误!运算符不匹配!n”); exit(O);elsep = <break;case 丁:if (ch2 = t)printf(H表达式错误!运算符不匹配!n“); exit(O);elseP = >； break;case #:if (ch2 = T)printf(H表达式错误!运算符不匹配!n“); exit(O);else if (ch2 = #)P =elsePv：break;return p;/=

21、 /以下是求值过程/=：=：int EvaluateExpression()参考书 p53 算法 3.4int a, b, temp, answer;char ch,op,e;char *str;int j = 0;SqStackn OPND; /OPND 为运算数字栈SqStack OPTR; /OPTR 为运算符栈InitStack(OPTR);Push(OPTR,#); /,所以此栈底是#,因为运算符栈以#作为结束标志InitStackn(OPND);/ printf(”nn按任意键开始求解:nnH)；/ch=getch();printf(Mn请输入表达式并以#结束:n”)；str =(

22、char*)malloc(50*sizeof(char);gets(str);ch=strj; ch是字符型的，而e是整型的整数j+;GetTop(OPTR,e); /e为栈顶元素返回值while (ch!=# | e!=#)if (llsoperator(ch)遇到数字,转换成十进制并计算temp=ch-,0,; 将字符转换为十进制数 ch=strj;j+；while(!lsoperator(ch)temp=temp*10 + ch-V; /将逐个读入运算数的各位转化为十 进制数ch=strj;j+；Pushn(OPND,temp);else if (Isoperator(ch) 判断是否是

23、运算符，不是运算符则进栈switch (Precede(e,ch) case N : Push(OPTR,ch); /栈顶元素优先权低 ch = strj+;printfCn运算符栈为：rT); 输出栈，显示栈的 变化StackTraverse(OPTR); printf("n 运算数栈为：n”)； StackTraversen(OPND); break;case '=: Pop(OPTR,op); /脱括号并接收下一字符ch = strj+; printf(nn 运算符栈为:rT); StackTraverse(OPTR); print!(”n 数栈为:n°);

24、StackT raversen(OPND); break;进栈case >*: Pop(OPTR,op);弹出最上面两个，并运算，把结果Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b); printf(”nn 运算符栈为：n”)； StackTraverse(OPTR); printf(”n 数栈为:nM); StackTraversen(OPND);elseprintf(”您的输入有问题，请检查重新输入门；exit(O);GetTop(OPTR,e);取出运算符栈最上面元素是否是# /whileGetTopn(OPND,answer);已输出。数字栈最上面即是最终结果return answer;/=：= /执行部分/=： void ShowMenu()printf (nnH);printf