算术表达式求值分解.doc

算术表达式求值演示 一、需求分析 (1) 输入的形式：语法正确的、不含变量的字符序列形式整数表达式范围是－(215-l)~(215-1) 运算符：+，-，*，/，（，） 表达式结束运算符 # (2) 输出的形式：范围是－(215-l)~(215-1)的整数 (3) 程序所能达到的功能：实现对算术四则混合运算表达式的求值1) Calculate ——计算表达式的值 2) Exit ——退出 (4) 测试数据 1) 8 2) 2-2-2-3; 3) 4+26/12-2*7; 4) 18-3*7-15/6; 5) 2*(6+2*(3+6*(6+6)))；(1) 为实现上述程序功能需要的抽象数据类型：1) 栈的抽象数据类型：ADT Stack{ 数据对象：D={ ||ai∈elemset, i=1,2, …,n，n≥0 }数据关系：R1={?| ai-1，ai∈D, i=2，…，n }基本操作：nitStack() 操作结果：构造一个空栈。GetTop（S，e） 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(S，e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。2) 系统中子程序及功能要求： Precede(char c1,char c2):比较两个字符的优先级，并返回比较结果。 Operate(SElemType a,char op,SElemType b):函数进行四则运算，并返回运算结果。 judge(char op):判断是否为运算符。 EvaluateExpression()：进行四则混合运算，并返回运算结果。 (2) 本次程序设计中一共有三个模块，一个是由主函数构成的模块，一个是由各个子功能函数构成的栈模块,第三个是由运算等函数构成的运算模块。 (3) 主模块可以对子模块中的函数进行调用，但子模块不能对主模块中的内容进行调用；子模块中的函数可相互调用。具体函数调用关系如下： main 调用 EvaluateExpression() EvaluateExpression() 调用 Precede、Operate、judge、InitStack()、 GetTop、 Push、Pop。 三、详细设计 (1) 程序流程图： (2) 元素类型、结点类型和指针类型 typedef int Status; typedef int SElemType; //元素类型 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; //结点类型和指针类型 (3) 栈的基本操作定义如下： Status InitStack(SqStack *S); //构造一个空栈S Status GetTop(SqStack S) //若栈不空，则返回栈顶元素，否则返回ERROR Status Push(SqStack *S,SElemType e); //插入e为新的栈顶元素 Status Pop(SqStack *S,SElemType *e); //若栈不空，则删除S的栈顶元素，用e返回其值，返回OK，否则返回ERROR (4) 系统中子程序的基本操作定义： Char Precede(char c1,char c2); //进行运算符的优先级比较，并返回比较结果。 SElemType Operate(SElemType a,char op,SElemType b); //进行两个整数数的四则运算，并返回运算结果。 Status judge(char op) //判断是否为运算符。 SElemType EvaluateExpression() //进行四则混合运算，并返回运算结果。 (5) 部分基本操作的源程序如下： Status Push(SqStack *S,SElemType e) { *(S-top)++=e;