《《数据结构》算术表达式求值.docx》由会员分享，可在线阅读，更多相关《《数据结构》算术表达式求值.docx（15页珍藏版）》请在三一文库上搜索。
1、二 课程设计 2算术表达式求值一、需求分析二、程序的主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码三 感想体会与总结算术表达式求值一、需求分析一个算术表达式是由操作数 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(0);s.top=s.base;s.stacksize=50; return OK;char GetTop(SqStack s,char &e)
3、/ 运算符取栈顶元素if (s.top=s.base)/栈为空的时候返回 ERRORprintf(" 运算符栈为空 !n");return ERROR;elsee=*(s.top-1); /栈不为空的时候用 e 做返回值，返回 S 的栈顶元素，并返回 OK return OK;int Push(SqStack &s,char e) / 运算符入栈if (s.top-s.base >= s.stacksize) printf(" 运算符栈满 !n");s.base=(char*)realloc (s.base,(s.stacksize+5)*
4、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=s.base) /栈为空栈的时候，返回 ERRORprintf(" 运算符栈为空 !n");return ERROR; elseOKe=*-s.top; / 栈不为空的时候用 e 做返回值，删除 S 的栈顶元
5、素，并返回 return OK;int StackTraverse(SqStack &s) / 运算符栈的遍历char *t; t=s.base ;if (s.top=s.base)printf(" 运算符栈为空 !n"); /栈为空栈的时候返回 ERROR return ERROR; while(t!=s.top)printf(" %c",*t); / 栈不为空的时候依次取出栈内元素 t+; return ERROR;2)数字栈局部：struct SqStackn / 定义数栈int*base;/栈底指针int*top;/栈顶指针intstac
6、ksize; /栈的长度;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 s,int &e) / 数栈取栈顶元素if (s.top=s.base)printf(" 运算数栈为空 !n"); / 栈为空的时候返回 ERROR return ERROR;else e=*(s.
7、top-1); / 栈不为空的时候，用 e 作返回值，返回 S 的栈顶元素，并返回 OK return OK;int Pushn(SqStackn &s,int e) / 数栈入栈if (s.top-s.base >=s.stacksize)printf("运算数栈满!n"); /栈满的时候，追加5个存储空间s.base=(int*)realloc (s.base,(s.stacksize+5)*sizeof(int) ); if(!s.base) exit (OVERFLOW);s.top=s.base+s.stacksize; / 插入元素 e 为新的栈顶
8、元素 s.stacksize+=5;*(s.top)+=e; / 栈顶指针变化return OK;int Popn(SqStackn &s,int &e) / 数栈出栈if (s.top=s.base)printf(" 运算符栈为空 !n"); /栈为空栈的视时候，返回 ERRORreturn ERROR; elseOK e=*-s.top;/栈不空的时候，那么删除 S 的栈顶元素，用 e 返回其值，并返回return OK;int StackTraversen(SqStackn &s) / 数栈遍历int *t;t=s.base ;if (s.to
9、p=s.base)printf(" 运算数栈为空 !n"); /栈为空栈的时候返回 ERROR return ERROR; while(t!=s.top)printf d",*t; /栈不为空的时候依次输出 t+；return ERROR;五、算法及时间复杂度1、算法：建立两个不同类型的空栈，先把一个妊入运算符栈。输入一个算术表达式的字符串(以结束)，从第一个字符依次向后读，把读取的数 字放入数字栈，运算符放入运算符栈。判断新读取的运算符和运算符栈顶 得运算符号的优先级，以便确定是运算还是把运算符压入运算符栈。最后 两个遇到一起那么运算结束。数字栈顶的数字就是要求
10、的结果。2、时间复杂度：0(n)数据压缩存储栈，其操作主要有：建立栈 int Push(SeqStack *S, char x)入栈 int Pop(SeqStack *S, char x)出栈。以上各操作运算的平均时间复杂度为0(n),其主要时间是消耗在输入操作。六、测试用例如下列图。运舁付悅为:A *运算数役为:2运算符役为; 崔韶娥为i2 34运算符栈为:II + * <运算数栈为:2 34运算符栈为;tt + * < -运算数栈为:2 34 6运算符栈为:运算数桂为:2 a4 G 4 理為址U 4最终结果如下列图:黒达式结果是：-66 本次运昱结東。 继续春绕呜？退由 Sw
11、feN/n七、源代码第七题算术表达式求值问题描述一个算术表达式是由操作数operand、运算符operator和界限符delimiter组成的 假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“ #如：#7+15*23-28/4#。引入表达式起始、结束符是为了方便。编程利用 算符优先法求算术表达式的值。根本要求1从键盘读入一个合法的算术表达式，输出正确的结果。2显示输入序列和栈的变化过程。*/#i nclude <stdio.h>#i nclude <stri ng.h>#include <stdlib.h>#incl
12、ude <math.h>#include <conio.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 (SqStack &s) / 建立一个空栈 Sif (!(
13、s.base = (char *)malloc(50 * sizeof(char) exit(0);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(SqStack &s,char
14、e) / 运算符入栈if (s.top-s.base >= s.stacksize) printf("运算符栈满!n");s.base=(char*)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.t
15、op=s.base)/栈为空栈的时候，返回 ERRORprintf("运算符栈为空!n");return ERROR;elsee=*-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(" %c&quo
16、t;,*t); / 栈不为空的时候依次取出栈内元素 t+; return ERROR;数字栈局部*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 s,int
17、 &e) / 数栈取栈顶元素if (s.top=s.base)printf("运算数栈为空！n"); /栈为空的时候返回ERRORreturn ERROR;elsee=*(s.top-1); /栈不为空的时候，用e作返回值，返回S的栈顶元素，并返 回 OKreturn OK;int Pushn(SqStackn &s,int e) / 数栈入栈if (s.top-s.base >=s.stacksize)printf("运算数栈满!n"); /栈满的时候，追加5个存储空间s.base=(int*)realloc (s.base,(s
18、.stacksize+5)*sizeof(int) );if(!s.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)printf(" 运算符栈为空 !n"); /栈为空栈的视时候，返回 ERRORreturn ERROR;elsee=*-s.top;栈不空的时候，那么删除S的栈顶元素，用
19、e返回其值，并返回 OKreturn OK;int StackTraversen(SqStackn &s) / 数栈遍历int *t;t=s.base ;if (s.top=s.base)printf(" 运算数栈为空 !n"); /栈为空栈的时候返回 ERRORreturn ERROR;while(t!=s.top)printf(" %d",*t); / 栈不为空的时候依次输出t+;return ERROR;/=/ 以下定义函数/= int Isoperator(char ch) / 判断是否为运算符，分别将运算符和数字进入不同的栈 switc
20、h (ch)case '+':case '-':case '*':case '/':case '(':case ')':case '#':return 1;default:return 0;int Operate(int a, char op, int b) / 运算操作 int result;switch(op)case '+':result=a+b; break;case '-': result=a-b; break;case '*'
21、;: result=a*b; break;case '/': result=a/b; break;return result;char Precede(char ch1, char ch2) / 运算符优先级的比较 char p;switch(ch1)case '+':case '-':ch2 运算符if (ch2='+'|ch2='-'|ch2=')'|ch2='#')p = '>' /ch1 运算符的优先级小于 elsep = '<'
22、break;case '/':if (ch2 = '(') p = '<' else p = '>'break;case '(':if (ch2 = ')')p = '='else if (ch2 = '#')printf(" 表达式错误 !运算符不匹配 !n") ; exit(0);elsep = '<'break ;case ')':if (ch2 = '(')printf(&q
23、uot; 表达式错误 !运算符不匹配 !n") ; exit(0); else p = '>'break ;case '#':if (ch2 = ')') printf(" 表达式错误 !运算符不匹配 !n") ; exit(0);else if (ch2 = '#') p = '='else p='<'break; return p;/=/ 以下是求值过程/=int EvaluateExpression()/参考书 p53 算法 3.4int a, b,
24、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 按任意键开始求解 :nn");/ ch=getch();printf("n 请输入表达式并以 '#'结束 :n");
25、str =(char*)malloc(50*sizeof(char);gets(str);ch=strj; /ch 是字符型的，而 e 是整型的整数 j+;GetTop(OPTR,e); /e 为栈顶元素返回值while (ch!='#' | e!='#')if (!Isoperator(ch)/遇到数字 ,转换成十进制并计算temp=ch-'0' /将字符转换为十进制数 ch=strj; j+;while(!Isoperator(ch)temp=temp*10 + ch-'0'/将逐个读入运算数的各位转化为十进制数ch=strj
26、; j+;Pushn(OPND,temp);else if (Isoperator(ch) / 判断是否是运算符 ,不是运算符那么进栈switch (Precede(e,ch)case '<' : Push(OPTR,ch); / 栈顶元素优先权低ch = strj+;printf("nn 运算符栈为： n"); /输出栈，显示栈的 变化StackTraverse(OPTR);printf("n 运算数栈为： n");StackTraversen(OPND);break;case '=' : Pop(OPTR,op)
27、; / 脱括号并接收下一字符ch = strj+ ;printf("nn 运算符栈为： n");StackTraverse(OPTR);printf("n 数栈为： n");StackTraversen(OPND);break;case '>' : Pop(OPTR,op);/弹出最上面两个，并运算，把结果进栈Popn(OPND,b);Popn(OPND,a);Pushn(OPND,Operate(a,op,b);printf("nn 运算符栈为： n");StackTraverse(OPTR);printf(&
28、quot;n 数栈为： n");StackTraversen(OPND);elseprintf(" 您的输入有问题，请检查重新输入 !");exit(0);GetTop(OPTR,e);/取出运算符栈最上面元素是否是 '#'/已输出。数字栈最上面即是最终结果 /whileGetTopn(OPND,answer); return answer;/=/ 执行局部表达式求值系统/=void ShowMenu()printf("nn");printf("printf("");printf("&qu
29、ot;);printf("");printf("void Quit(); void Manage()int answer;/ ShowMenu();answer=EvaluateExpression();printf("nn 表达式结果是 : %dn",answer); Quit();void Quit()char ch;printf(" 本次运算结束。 n");printf(" 继续本系统吗？ nn"); printf(" 继续运算请按 Y/y "); printf("n
30、退出程序请按 N/n ");printf("nn");ch=getch(); ch=toupper(ch);/将 ch 字符转换成大写字母if(ch = 'N')printf("nn 系统退出。 n"); exit(0);Manage();int main()ShowMenu();Manage();return 0;感想体会与总结好的算法+编程技巧+高效率=好的程序。1、做什么都需要耐心，做设计写程序更需要耐心。一开始的时候， 我写函数写的很快，可是等最后调试的时候发现错误很隐蔽，就很费时间 了。后来我先在纸上构思出函数的功能和
31、参数，考虑好接口之后才动手 编，这样就比较容易成功了。2、做任何事情我决定都应该有个总体规划。之后的工作按照规划逐 步展开完成。对于一个完整的程序设计，首先需要总体规划写程序的步 骤，分块写分函数写，然后写完一局部马上纠错调试。而不是像我第一个 程序，一口气写完，然后再花几倍的时间调试。一步步来，走好一步再走 下一步。写程序是这样，做工程是这样，过我们的生活更是应该这样。3、感觉一开始设计结构写函数表达的是数据结构的思想，后面的调 试那么更加表达了人的综合素质，专业知识、坚决耐心、锲而不舍，真的缺 一不可啊。4、通过这次课设，不仅仅复习了 C语言相关知识、稳固了数据结构关于栈和排序的算法等知识，更磨练了我的意志。