logo资料库

算术表达式求值演示.doc

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：1.61M 资料格式：doc 举报 版权申诉
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
资料共17页，剩余部分请下载后查看
    算法设计
    1、算符的优先级比较函数Compare(char m,char n)
    算法的基本思想：
    通过已知的算符间的优先关系写出算符的优先级算法。任意两个相继出现的算符c1和c2之间的优先关系至
    c1
    c1=c2c1的优先权等于c2
    c1>c2c1的优先权高于c2
    算法步骤:
    Step1:如果输入符号为“+”或“-”
    1.1如果栈顶元素为“(”、“#”,此时栈顶符号优先级低，返回“<”
    1.2 否则，栈顶符号优先级高,返回“>”
    Step2:如果输入符号为“*”或“/”
    2.1 如果栈顶元素为“)”、“*”、“/”,此时栈顶符号优先级高，返回“>”
    2.2 否则，栈顶符号优先级低,返回“<”
    Step3: 如果输入符号为“(”, 则直接返回“<”
    Step4:如果输入符号为“)”
    4.1 如果栈顶元素为“(”,此时优先级同，返回“=”
    4.2 否则，栈顶符号优先级高,返回“>”
    Step5:输入符号为其他
    5.1 栈顶元素为“#”,此时优先级同，返回“=”
    5.2 否则，栈顶符号优先级高,返回“>”
    2、确定如何入栈函数evaluate(SqStack1 &S1,SqStack2 &S2)
    算法的基本思想：
    （1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；
    （2）依次读入表达式中每个字符，若是操作数则进运算数栈，若是运算符则和运算符栈的栈顶运算符比较优先后
    算法步骤:
    Step1:将‘#’入栈，作为低级运算符
    Step2:输入不含变量的表达式（以#结束!）
    Step3:如果c!='#'||GetTop1(S1)!='#'
    3.1如果输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数
    3.2 如果输入的是运算符
    a、遇到运算符，则将之前输入的操作数进栈
    b、比较运算符的优先级
    1)栈顶元素优先级低，则入栈且继续输入
    2)栈顶元素优先级相等，脱括号并接收下一字符
    3)栈顶元素优先级高，则退栈并将运算结果入栈
    Step4:显示表达式最终结果
    1．结构分析:
    2．算法的时空分析：
    3．用户使用说明：
    6. 结果分析
    算术表达式求值演示 目 录 第一章 概述……………………………………………………………1 第二章 系统分析………………………………………………………1 第三章 概要设计………………………………………………………2 第四章 详细设计………………………………………………………5 第五章 运行与测试……………………………………………………13 第六章 总结与心得……………………………………………………16 参考文献 ………………………………………………………………16
    第一章 概述 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程 相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课 程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业 基础课，是计算机理论和应用的核心基础课程。 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择 和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计 方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序 设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符 优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵 活运用它们，同时加深对这种结构的理解和认识。 第二章 系统分析 1． 以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的算符优 先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算 符栈、运算数栈、输入字符和主要操作的变化过程。 2． 一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象 出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行 测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的 先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个 用以寄存运算符，另一个用以寄存操作数和运算结果。 3． 演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机 语言的转化。 4． 程序执行时的命令： 本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么 特殊的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一 1
    些错误） 5. 测试数据。 第三章 概要设计 一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有 优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数 据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算 符的优先级完成表达式的求值计算。 算法设计 1、算符的优先级比较函数 Compare(char m,char n) 算法的基本思想： 通过已知的算符间的优先关系写出算符的优先级算法。任意两个相继出现的 算符 c1 和 c2 之间的优先关系至多是下面 3 种关系之一： c1c2 c1 的优先权高于 c2 算法步骤: Step1:如果输入符号为“+”或“-” 1.1 如果栈顶元素为“(”、“#”,此时栈顶符号优先级低，返回“<” 1.2 否则，栈顶符号优先级高,返回“>” Step2:如果输入符号为“*”或“/” 2.1 如果栈顶元素为“)”、“*”、“/”,此时栈顶符号优先级高，返回 “>” 2.2 否则，栈顶符号优先级低,返回“<” Step3: 如果输入符号为“(”, 则直接返回“<” Step4:如果输入符号为“)” 4.1 如果栈顶元素为“(”,此时优先级同，返回“=” 4.2 否则，栈顶符号优先级高,返回“>” Step5:输入符号为其他 5.1 栈顶元素为“#”,此时优先级同，返回“=” 5.2 否则，栈顶符号优先级高,返回“>” 2、确定如何入栈函数 evaluate(SqStack1 &S1,SqStack2 &S2) 算法的基本思想： 2
    （1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元 素； （2）依次读入表达式中每个字符，若是操作数则进运算数栈，若是运算 符则和运算符栈的栈顶运算符比较优先后作相应操作，直至整个表达式求值 完毕（即运算符的栈顶元素和当前读入的字符均为“#”）。 算法步骤: Step1:将‘#’入栈，作为低级运算符 Step2:输入不含变量的表达式（以#结束!） Step3:如果 c!='#'||GetTop1(S1)!='#' 3.1 如果输入的字符如果不是运算符号，则继续输入直到输入的是 运算符为止，将非运算符转换成浮点数 3.2 如果输入的是运算符 a、遇到运算符，则将之前输入的操作数进栈 b、比较运算符的优先级 1) 栈顶元素优先级低，则入栈且继续输入 2) 栈顶元素优先级相等，脱括号并接收下一字符 3) 栈顶元素优先级高，则退栈并将运算结果入栈 Step4:显示表达式最终结果 程序包含三个模块 (1) 主程序模块，其中主函数为 void main{ 输入表达式； 根据要求进行转换并求值； 输出结果； } (2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。 各个函数之间的调用关系 3
    主函数 数据输入 表达式求值 表达式转换 输出 输出 栈的抽象数据类型定义 ADT SqStack{ 数据对象：D={ai| ai ∈ElemSet,i=1,2,3……，n,n≥0} 数据关系：R1={| ai-1,ai ∈D,i=1,2,3,……，n} 约定其中 ai 端为栈底，an 端为栈顶。 操作集合： (1)void InitStack1(SqStack1 &S1);//声明栈建立函数 (2)void InitStack2(SqStack2 &S2);//声明栈建立函数 (3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 (4)void Push1(SqStack1 &S1,char e);//声明入栈函数 (5)void Push2(SqStack2 &S2,float e);//声明入压栈函数 (6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数 (7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数 (8)char Pop1(SqStack1 &S1);//声明出栈函数 (9)float Pop2(SqStack2 &S2);//声明出栈函数 (10)char Compare(char m,char n);//声明比较函数 (11)float Operate(float a,char rheta,float b);//声明运算函数 (12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 (13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素 }ADT SqStack 4
    第四章 详细设计 源程序 #include using namespace std; #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct //运算符栈 { char *base; char *top; int stacksize; }SqStack1; typedef struct //运算数栈 { float *base; float *top; int stacksize; }SqStack2; void InitStack1(SqStack1 &S1);//声明栈建立函数 void InitStack2(SqStack2 &S2);//声明栈建立函数 void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数 void Push1(SqStack1 &S1,char e);//声明入栈函数 void Push2(SqStack2 &S2,float e);//声明入压栈函数 char GetTop1(SqStack1 &S1);//声明取栈顶元素函数 float GetTop2(SqStack2 &S2);//声明取栈顶元素函数 char Pop1(SqStack1 &S1);//声明出栈函数 float Pop2(SqStack2 &S2);//声明出栈函数 char Compare(char m,char n);//声明比较函数 float Operate(float a,char rheta,float b);//声明运算函数 void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素 void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素 /*主函数*/ void main() 5
    SqStack1 S1;//定义运算符栈 SqStack2 S2;//定义运算数栈 //freopen("data1.in","r",stdin); //freopen("data1.out","w",stdout); InitStack1(S1);//调用栈建立函数 InitStack2(S2);//调用栈建立函数 evaluate(S1,S2);//调用确定如何入栈函数 cout<<"按任意键结束!"<=S1.stacksize)//如果栈满，追加存储空间 { S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char)); if(!S1.base) cout<<"存储分配失败！"; else { S1.top=S1.base+S1.stacksize; S1.stacksize=S1.stacksize+STACKINCREMENT; } } *S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移 } char GetTop1(SqStack1 &S1)//取栈顶元素 6
    { } char e; if(S1.top==S1.base)cout<<"\n\t\t\t 运算符栈已空!\n"; else e=*(S1.top-1); return e; void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素 { char e,*p; if(S1.top==S1.base)cout<<" "; else { p=S1.base; while(p
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料