算术表达式求值-数据结构实验报告.docx

算术表达式求值-数据结构实验报告 清华大学数据结构课程实验报告（20 -20 学年第学期） 报告题目：算术表达式求值 任课老师： 专业： 学号： 姓名： 二0一年月日 摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点而算符优先法的设计恰巧符合先入先出的思想故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值 关键字：算符优先法；算术表达式；数据结构；栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”利用算符优先法对算术表达式求值 2、设计目的 （1）通过该算法的设计思想，熟悉栈的特点和应用方法； （2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。

（3）通过程序设计，进一步熟悉栈的基本运算函数； （4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力3、基本要求： （1）使用栈的顺序存储表示方式； （2）使用算符优先法； （3）用C语言实现； （4）从键盘输入一个符合要求的算术表达式，输出正确的结果 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路： 为了实现算符优先法，可以使用两个工作栈一个称做OPTR，用以寄存运 算符；另一个称做OPND ，用以寄存操作数或运算结果 算法的基本思想是： （1）首先置操作数栈为空栈，表达式起始符“#”作为运算符栈的栈底元素； （2）依次读入表达式中每个字符，若是操作数则进入OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为“#”） 算法中还调用了两个函数其中函数Precede 是判定运算符栈顶运算符1θ与读入的运算符2θ之间优先关系的函数；函数Operate 为进行二元运算b a θ的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。

2、方案设计 （1）抽象数据类型定义 ADT Stack{ 数据对象：D={ i a | i a ∈ElemSet,i=1,2,…,n,, n ≧0} 数据对象：R1={ | i a , 1-i a ∈D ，i=2,…,n} 约定n a 端为栈顶，i a 端为栈底 基本操作： InitStack(&S) 操作结果：构造一个空栈S GetTop(S) 初始条件：栈S 已存在 操作结果：用P 返回S 的栈顶元素 Push(&S, e) 初始条件：栈S 已存在 操作结果：插入元素e 为新的栈顶元素 Pop(&S, e) 初始条件：栈S 已存在 操作结果：删除S 的栈顶元素，并用e 返回其值 Precede(1c ,2c ) 初始条件：1c ,2c 为运算符 操作结果：判断运算符优先权，返回表示优先权高低关系的“”的字符 Operate(a, OP, b) 初始条件：a, b 为整数，OP 为运算符 操作结果：a 与b 进行运算，OP 为二元运算符，返回其值 }ADT Stack （2）符号之间的优先权关系比较 1θbase=(float*)malloc((STACK_INIT_SIZE)*sizeof(float)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } void initStack(sqStack *S) //构造空栈（运算符栈）{ S->base=(char*)malloc((STACK_INIT_SIZE)*sizeof(char)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } float GetTop(SqStack *S) //用e返回栈顶元素（运算数）{ float e; if(S->top==S->base) return ERROR; e=*(S->top-1); return e; } char getTop(sqStack *S) //用e返回栈顶元素（运算符）{ char e; if(S->top==S->base) return ERROR; e=*(S->top-1); return e; } float Push(SqStack *S,float e) //插入e为新的栈顶元素（运算数）{ if(S->top-S->base>=S->stacksize) { S->base=(float*)realloc(S->base,(S->stacksize+STACKINCREMEN T)*sizeof(float)); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *S->top++=e; return e; } char push(sqStack *S,char e) //插入e为新的栈顶元素（运算符）{ if(S->top-S->base>=S->stacksize) { S->base=(char*)realloc(S->base,(S->stacksize+STACKINCREMENT )*sizeof(char)); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *(S->top)=e; (S->top)++; return e; } float Pop(SqStack *S) //删除栈顶元素(运算数) { float e; if(S->top==S->base) return ERROR; (S->top)--; e=*(S->top); return e; } char pop(sqStack *S) //删除栈顶元素(运算符) { char e; if(S->top==S->base) return ERROR; (S->top)--; e=*(S->top); return e; } int jiancha1(char e) //判断e是运算符还是运算数 { if(e!='+'&&e!='-'&&e!='*'&&e!='/'&&e!='('&&e!=')'&&e!='#') return 1; else return 0; } void jiancha2(char e) //判断e是否为合法的运算符或运算数{ if(e==48||e==49||e==50||e==51||e==52||e==53||e==54||e==55||e= =56||e==57) flag=1; else if(e=='+'||e=='-'||e=='*'||e=='/'||e=='('||e==')'||e=='#') flag=1; else flag=0; } char Precede(char p,char q) //优先级比较函数 { switch(p) { case'+':if((q=='*')||(q=='/')||(q=='(')) return'';break; case'-':if((q=='*')||(q=='/')||(q=='(')) return'';break; case'*':if(q=='(') return '';break; case'/':if(q=='(') return '';break; case'(':if(q==')') return '='; else if(q=='#') return ' '; else return '';break; case'#':if(q=='#') return '='; else if(q==')') return ' '; else return '<';break; default: printf("你的输入非法\n"); } } float Operate(float s,char yunsuanfu,float t) //二元运算操作 。