需 求 分 析(附代码)

一、需求分析

（1）首先定义两个栈OPTR、OPND，栈OPTR用于存放运算符，栈OPND用于存放操作数；定义一个一维数组expr【】存放表达式串。

（2）主函数主要包括两部分：（1）判断运算符优先权，返回优先权高的；（2）操作函数。

（3）开始将‘#’入操作符栈，通过一个函数来判别算术运算符的优先级。且规定‘#’的优先级最低。在输入表达式的最后输入‘#’，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈。遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

（4）最初实现的加、减、乘、除及带小括号的基本运算，但考虑到实用性，后来的设计中有加上了乘方运算。在乘方运算中借用了C库中自带的乘方函数pow。

二、 概要设计

1、 设定栈的抽象数据类型定义：

ADT Stack {

数据对象：

D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }

数据关系：

R1＝{ | ai-1, ai∈D, i=2,...,n }

约定an 端为栈顶，a1 端为栈底。

基本操作：

InitStack(&S)

操作结果：构造一个空栈 S。

DestroyStack(&S)

初始条件：栈 S 已存在。

操作结果：栈 S 被销毁。

StackEmpty(S)

初始条件：栈 S 已存在。

操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。

StackLength(S)

初始条件：栈 S 已存在。

操作结果：返回 S 的元素个数，即栈的长度。

GetTop(S, &e)

初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。

ClearStack(&S)

初始条件：栈 S 已存在。

操作结果：将 S 清为空栈。

Push(&S, e)

初始条件：栈 S 已存在。

操作结果：插入元素 e 为新的栈顶元素。

Pop(&S)

初始条件：栈 S 已存在且非空。

操作结果：删除 S 的栈顶元素，并用 e 返回其值。

} ADT Stack

2、表达式的抽象数据类型

ADT arithmetic

{

数据对象：D1={‘+’、‘-’、‘*’、‘/’、‘#’,‘^’}

D2={ a1 a2 a3 a4 ……}

基本操作：

int In(int c)

//判断输入字符c是否为运算符,返回1，则c为操作符，返回0则c不是操作符

char precede(int top,char c)

//判断当前运算符与前一个运算符的优先级，前一个运算符高于或等于当前运算符的优先级则返回‘>’， 前一个运算符小于当前运算符的优先级则返‘<’，当前一个运算符为‘（’当前运算符为‘）’时返回‘=’，用于去除表达式的括号。

elemtype operate(elemtype a,char theta,elemtype b)

//计算运算过程中的两个数的值，a，b为两个操作数，theta为操作符，成功，返回两个数的运算结果

elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)

//求表达式的值的整个操作过程，通过调用相应的函数实现遇到运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。

}

3、本程序包含的模块：

（1）、主程序模块

void main()

{

struct Sqstack opnd;//操作数栈

struct Sqstack optr;//操作符栈

elemtype result;

result=evaluate(opnd,optr);

printf("the result is %d\n",result);

}

（2）运算模块——实现数据表达式的运算

（3）栈模块——实现栈抽象数据类型

模块调用关系：

5、 计算表达式的伪码

初始化操作符栈

将‘#’入操作符栈

初始化操作数栈

输入字符c

while(c!='#'||gettop(optr)!='#')

{

如果c是操作数

{

如果flag=1；

将操作数栈的栈顶元素出栈，和c共同转化为相应的int类型的数后入操作数栈

若flag=0

则将c-48入操作数栈

flag=1；

输入c

}

否则{

将c和操作符栈的栈顶元素比较

若c的优先级高于栈顶元素

C入操作符栈

输入下一个字符c

若为c与栈顶元素是一对括号，

则将栈顶元素出栈

输入下一字符c

若c的优先级低于栈顶元素

则计算操作数栈的栈顶的两个元素的运算，后将运算结果入栈

}

}//while

三、详细设计

1、输入字符为char类型

栈结构

struct Sqstack

{

elemtype *top; //栈顶指针

elemtype *base; //栈底指针

int stacksize; //栈的大小

};

2、栈的基本操作

（1）初始化栈

status initstack(struct Sqstack &s)

{

s.base=(elemtype *)malloc(stack_size*sizeof(elemtype));

if(!s.base)

return OVERFLOW;

s.top=s.base;

s.stacksize=stack_size;

return OK;

}

（2）入栈

status push(struct Sqstack &s,elemtype e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*

sizeof(elemtype));

if(!(s.base))

return OVERFLOW;

s.top=s.base+s.stacksize;

s.stacksize+=stack_increasement;

}

* s.top++=e;

return OK;

}

（3）出栈

elemtype pop(struct Sqstack &s)

{

elemtype e;

if(s.top= =s.base)

return ERROR;

e=*--s.top;

return e;

}

（4）取栈顶元素

elemtype gettop(struct Sqstack &s)

{

elemtype e;

if(s.top==s.base)

return ERROR;

e=*(s.top-1);

return e;

}

3、判断c是否是操作数

代码具体设计：

int In(int c)

//判断输入字符是否为运算符,返回1，则c为操作符，返回0则c不是操作符

{

char p[10]="+-*/()#^";

int i=0;

while(p[i]!='\0')

{

if(p[i]= =c)

return 1;

i++;

}

return 0;

}

6、 判断运算符的优先级

算数符优先关系模块——描述算符之间的优先关系,如下表：

char precede(char top,char c)

//top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回‘<’,c的优先级小于top‘>’，c与top构成括号匹配返回‘=’

{

char result;

switch(c)

{

case '#':

result='>';break;

case '+':

case '-':

if(top= ='# ' | | top= = ' ( ' )

result='<';

else

result='>';break;

case '*':

case '/':

if(top= ='*'||top= ='/'||top= ='^')

result='>';

else

result='<';break;

case ')':

if(top=='(')

result='=';

else

result='>';break;

case '(':

result='<';break;

case '^':

result='<';break;

default:

printf("the operater is out of band.\n");

}

return result;

}

5、将输入的字符数据转换为相应的int类型

（1）若为各位数，则直接将输入的字符减48后入栈，若为多位数，则通过flag来实现。（2）若输入字符c为操作数且flag=1，则将操作数栈的栈顶元素出栈后乘以10，然后加上，（c-48）然后将二者的和入操作数栈。

代码设计：

if(!In(c))//c若为操作数则入opnd栈

{

if(flag= =1)

{

e=pop(opnd);

push(opnd,(e*10+(c-48)));

}

else

push(opnd,c-48);

flag=1;

c=getchar();

}

6、具体运算函数

elemtype operate(elemtype a,char theta,elemtype b)

//该函数实现相应的加、减、乘、除、乘方及带小括号的基本数学运算

{

elemtype result;

switch(theta)

{

case '+':

result=a+b;break;

case '-':

result=a-b;break;

case '*':

result=a*b;break;

case '/':

if(b= =0)

//当除数为0时

{

printf("分母为0,the result is error\n");

result=0;

}

else

result=a/b;break;

case '^':

result=(int)pow((double)a,(double)b);break;

default:

printf("the operater is wrong.\n");

}

return result;

}

7、运算主函数

elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)

{

elemtype a,b,c,theta,e;

initstack(optr); // 初始化操作符栈

push(optr,'#');

initstack(opnd); // 初始化操作数栈

c=getchar();

int flag=0;

//输入的时操作数时，将flag=1；输入为操作符时flag=0；

//当前输入为操作数且flag=1时，将操作数栈的栈顶元素出栈，

//然后和当前输入转换成相应的int类型

while(c ! = ' # ' || gettop ( optr ) ! = ' # ' )

{

if(!In(c))

//c若为操作数则入opnd栈

{

if(flag= =1)

{

e=pop(opnd);

//取栈顶元素 push(opnd,(e*10+(c-48)));

//将取出的栈顶元素，与当前操作数相加，后将结果如操作数栈

}

else

push(opnd,c-48);//将操作数直接入栈

flag=1;

c=getchar();

}

else

{

flag=0;

//当前字符为操作码，则如操作符栈，并将flag置为0

switch(precede(gettop(optr),c))

// 判断当前操作数与操作符栈中的栈顶元素的优先级

{

case '<':

push(optr,c); c=getchar();

break;

// 若当前操作符的优先级高于操作符栈的栈顶元素，则将

//前操作符入操作符栈

case '=':

e=pop(optr);

c=getchar();

break;

// 若当前操作符与操作符栈的栈顶元素构成匹配的括号，则//将操作符栈顶元素出栈

case '>':

theta=pop(optr);

b=pop(opnd);

a=pop(opnd);

push(opnd,operate(a,theta,b));

break;

// 若当前操作符的优先级低于操作符栈的栈顶元素，则将操作符栈栈顶

//元素出栈，并将操作数栈的栈顶两个元素出栈，计算

//两个元素以操作符栈顶元素的数学运算

}//switch

}

}//while

return pop(opnd);

}

函数调用关系图

evaluate（）

main（）主函数

nitstack gettop l n pop push precede push

gettop operate

四、调试分析

1、输入的操作数和操作码由于是字符串类型的，在原设计中实现的操作都是对个位数实现的。由于仅是对个位数的运算，实用性不大，故在后来的设计中，通过一个标志flag实现了标志操作数的连续输入的判别，继而实现了多位数的表达式运算。开始只实现了加、减、乘、除及带小括号的数学运算，考虑到实用性，在后来的设计中有实现了乘方的运算。

2、本设计的关键是运算符优先级的判断，由于优先级的错判，很容导致结果的运算错误。 要明晰判断当前运算符和运算符栈栈顶元素的先后顺序，这个易出错误。

3、在本次设计中充分利用了，栈先进后出的特点。

4、该设计的内存分配：初始化栈时，每个栈分配100个内存单元，如果不够用，以后每次可增加10个动态内存单元。

5、由于程序比较长，在调试期间，可以再每个调用函数中加上printf语句，通过观察程序的运行过程，理由查找错误，和改进程序。

6、程序时间复杂度为O（n）；

7、该设计，自顶向下，分层设计，将每个功能模块化，简洁明了。

8、经验体会：借助DEBUG调试器和数据观察窗口，可以加快找到程序的瑕点

9、要注意在算数运算中，除数不能为0，在开始的设计中没有注意到这一点。

10、在表达式的运算中，要注意输入的是字符串，应将其转换为相应的整形类型的数据再进行运算。否则将出错。并且应当操作数的出栈顺序，以及相应的运算顺序，先出栈的为第二操作数，第二次出栈的为第一操作数。

五、用户手册

1、本程序的运行环境为DOS操作系统，执行文件为：LiangHong.exe

2、进入演示程序后，即显示文本方式的用户界面：

****************************************************************

请输入算术表达式，以‘#’结尾

****************************************************************

3、输入算数表达式后，并以‘#’结尾，按回车键，即可得到运算结果

六、测试结果

输入结果

3*（7-2）# the result is 15

8# the result is 8

1+2+3+4# the result is 10

88-1*5# the result is 83

1024/4*8# the result is 2048

1024/(4*8)# the result is 32

(20+2)*(6/2)# the result is 66

3-3-3# the result is - 3

8/(9-9)# 分母为0，the result is error

2*(6+2*(3+6*(6+6)))# the result is 312

(((6+6)*6+3)*2+6)*2# the result is 312

2^10# the result is 1024

3^(5-(6+7)+6+7-5)# the result is 1

附原代码:

#include

#include

#include

#define stack_size 100

#define stack_increasement 10

#define OK 1

#define TRUE 1

#define FALSE 0

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int status;

typedef int elemtype;

struct Sqstack

{

elemtype *top;

elemtype *base;

int stacksize;

};

status initstack(struct Sqstack &s)

{

s.base=(elemtype *)malloc(stack_size*sizeof(elemtype));

if(!s.base)

return OVERFLOW;

s.top=s.base;

s.stacksize=stack_size;

return OK;

}

elemtype gettop(struct Sqstack &s)

{

elemtype e;

if(s.top==s.base)

return ERROR;

e=*(s.top-1);

return e;

}

status push(struct Sqstack &s,elemtype e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(elemtype *)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype));

if(!(s.base))

return OVERFLOW;

s.top=s.base+s.stacksize;

s.stacksize+=stack_increasement;

}

* s.top++=e;

return OK;

}

elemtype pop(struct Sqstack &s)

{

elemtype e;

if(s.top==s.base)

return ERROR;

e=*--s.top;

return e;

}

int In(int c) //判断输入字符是否为运算符,返回1，则c为操作符，返回0则c不是操作符

{

char p[10]="+-*/()#^";

int i=0;

while(p[i]!='\0')

{

if(p[i]==c)

return 1;

i++;

}

return 0;

}

char precede(char top,char c)

//top为操作符的栈顶元素，c为当前输入操作符，若c的优先级大于top返回'<',c的优先

//级小于top'>'，c与top构成括号匹配返回'='

{

char result;

switch(c)

{

case '#':

result='>';break;

case '+':

case '-':

if(top=='#'||top=='(')

result='<';

else

result='>';break;

case '*':

case '/':

if(top=='*'||top=='/'||top=='^')

result='>';

else

result='<';break;

case ')':

if(top=='(')

result='=';

else

result='>';break;

case '(':

result='<';break;

case '^':

result='<';break;

default:

printf("the operater is out of band.\n");

} // switch

return result;

}

elemtype operate(elemtype a,char theta,elemtype b)

{

elemtype result;

switch(theta)

{

case '+':

result=a+b;break;

case '-':

result=a-b;break;

case '*':

result=a*b;break;

case '/':

if(b==0)

{

printf("分母为0,the result is error\n");

result=0;

}

else

result=a/b;break;

case '^':

result=(int)pow((double)a,(double)b);break;

default:

printf("the operater is wrong.\n");

}

return result;

}

elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)

{

elemtype a,b,c,theta,e;

initstack(optr);

push(optr,'#');

initstack(opnd);

c=getchar();

int flag=0;

//输入的时操作数时，将flag=1；输入为操作符时flag=0；

//当前输入为操作数且flag=1时，将操作数栈的栈顶元素出栈，

//然后和当前输入转换成相应的int类型

while(c!='#'||gettop(optr)!='#')

{

if(!In(c))//c若为操作数则入opnd栈

{

if(flag==1)

{

e=pop(opnd);

push(opnd,(e*10+(c-48)));

}

else

push(opnd,c-48);

flag=1;

c=getchar();

}

else{

flag=0;

switch(precede(gettop(optr),c))

{

case '<':

push(optr,c);

c=getchar();break;

case '=':

e=pop(optr);

c=getchar();break;

case '>':

theta=pop(optr);

b=pop(opnd);

a=pop(opnd);

push(opnd,operate(a,theta,b));break;

}//switch

}//if

}//while

return pop(opnd);

}

void main()

{

struct Sqstack opnd;//操作数栈

struct Sqstack optr;//操作符栈

elemtype result;

printf("\n*********************************************************\n");

printf("\n\n\n please input the 运算表达式，以'#'结尾\n\n\n");

printf("\n*********************************************************\n");

result=evaluate(opnd,optr);

printf("the result is %d\n\n",result);

getchar();

}

数据结构-算术表达式求值（含需求分析和源代码）