1、 1 题目题目: :算术表达式求值演示算术表达式求值演示 一、一、 需求分析需求分析 1. 问题描述：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个经 典例子。设计一个程序演示用算符优先法对算术表达式求值的过程。 2. 基本要求：利用教科书表 3.1 给出的算符优先关系，实现对算术四则混合运算表达式 的求值。 3. 测试数据：教科书例 3-1 的算术表达式 3*（7-2）。 二、二、 概要分析概要分析 栈的抽象数据类型定义 ADT SqStack 数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0 数据关系：R1=| ai-1,ai D,i=1,2,3,，n
2、约定其中 ai端为栈底，an端为栈顶。 操作集合： (1)void InitStack1(SqStack1 /声明栈建立函数 (2)void InitStack2(SqStack2 /声明栈建立函数 (3)void evaluate(SqStack1 /确定如何入栈函数 (4)void Push1(SqStack1 /声明入栈函数 (5)void Push2(SqStack2 /声明入压栈函数 (6)char GetTop1(SqStack1 /声明取栈顶元素函数 (7)float GetTop2(SqStack2 /声明取栈顶元素函数 (8)char Pop1(SqStack1 /声明出栈函
3、数 (9)float Pop2(SqStack2 /声明出栈函数 (10)char Compare(char m,char n);/声明比较函数 (11)float Operate(float a,char rheta,float b);/声明运算函数 (12)void DispStack1(SqStack1 /从栈底到栈顶依次输出各元素 (13)void DispStack2(SqStack2 /从栈底到栈顶依次输出各元素 ADT SqStack 三、 详细设计 2 源程序 #include using namespace std; #define STACK_INIT_SIZE 100 #
4、define STACKINCREMENT 10 typedef struct /运算符栈 char *base; char *top; int stacksize; SqStack1; typedef struct /运算数栈 float *base; float *top; int stacksize; SqStack2; void InitStack1(SqStack1 /声明栈建立函数 void InitStack2(SqStack2 /声明栈建立函数 void evaluate(SqStack1 /确定如何入栈函数 void Push1(SqStack1 /声明入栈函数 void P
5、ush2(SqStack2 /声明入压栈函数 char GetTop1(SqStack1 /声明取栈顶元素函数 float GetTop2(SqStack2 /声明取栈顶元素函数 char Pop1(SqStack1 /声明出栈函数 float Pop2(SqStack2 /声明出栈函数 char Compare(char m,char n);/声明比较函数 float Operate(float a,char rheta,float b);/声明运算函数 void DispStack1(SqStack1 /从栈底到栈顶依次输出各元素 void DispStack2(SqStack2 /从栈底
6、到栈顶依次输出各元素 /*主函数*/ void main() SqStack1 S1;/定义运算符栈 3 SqStack2 S2;/定义运算数栈 /freopen(“data1.in“,“r“,stdin); /freopen(“data1.out“,“w“,stdout); InitStack1(S1);/调用栈建立函数 InitStack2(S2);/调用栈建立函数 evaluate(S1,S2);/调用确定如何入栈函数 coutch; c=ch0; cout1)t=t*10+e; c=chs+; if(n=-1) e=float(c-48); t=t+e/10; c=chs+; if(c=.) n=-1; c=chs+; if(c=0 goto as; if(c9) Push2(S2,t); cout“ else if(n=*|n=/)/输入的符号为“*“、“/“
