《程序设计方法学》实验报告-算术表达式求值(2)

int stacksize; } Stack2;

3.2主要算法流程图（或算法伪代码）

1. Precede(char a1,char a2) 判断运算符优先权，返回优先权高的。 算符间的优先关系如下：

+ - * / ( ) # + > > > > < > < - < > > > < > < * < < > > < > < 表 1 算法伪代码如下：

char Precede(char a1,char a2) {

static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!',

'>', '>', '>', '>', '!', '>', '>',

'<', '<', '<', '<', '<', '!', '='}; //用一维数组存储49种情况 switch(a1) {

/* i为下面array的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; case '/' : i=3;break; case '(' : i=4;break; case ')' : i=5;break; case '#' : i=6;break; } switch(a2)

{

/* j为下面array的纵标 */ case '+' : j=0;break; case '-' : j=1;break;

/ < < > > < > < ( < < < < < < ) > > > > = > # > > > > > = case '*' : j=2;break; case '/' : j=3;break; case '(' : j=4;break; case ')' : j=5;break; case '#' : j=6;break;

}

return (array[7*i+j]); /* 返回运算符array[7*i+j]为对应的c1,c2优先关系*/ }

2. SElemType EvaluateExpression()主要操作函数。算法概要流程图：

利用该算法对算术表达式3*(7-2)求值操作过程如下： 步骤 1 2 3 4 5 6 7 8 9 10 OPTR栈 # # #* #*( #*( #*(- #*(- #*( #* # OPND栈 3 3 3 3 7 3 7 3 7 2 3 5 3 5 15 表2

算法伪代码如下：

SElemType EvaluateExpression()//主要操作函数

输入字符 3*(7-2)# *(7-2)# (7-2)# 7-2)# -2)# 2)# )# )# # # 主要操作 Push(OPND,’3’) Push(OPTR,’*’) Push(OPNR,’(’) Push(OPND,’7’) Push(OPNR,’-’) Push(OPND,’2’) Operate(‘7’,’-’,’2’) Pop(OPTR) Operate(‘3’,’*’,5’) Return(GetTop2(OPND)) { //算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈 SqStack OPTR,OPND; char c;

char Data[11];//定义此数组为了存放整数或小数 SElemType a,b,d,e;

InitStack(OPTR);//构造一个运算符栈 InitStack(OPND);//构造一个运算数栈 Push(OPTR,'#');//将#压入栈底 c=getchar(); GetTop(OPTR,e);

while(c!='#'||e!='#')//栈顶不是#号且输入不是#号 {

if(In(c))//是符号则进栈 {

switch(Precede(e,c)) {

case'<': //栈顶元素优先级低 Push(OPTR,c); c=getchar(); break;

case'=': //脱括号并接受下一字符 Pop(OPTR,e); c=getchar(); break;

case'>': //退栈并将运算结果入栈 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a);

Push(OPND,Operate(a,e,b)); break; }//switch }

else if(c>='0'&&c<='9'||c=='.') { int i=0;

while(c>='0'&&c<='9'||c=='.')

{

Data[i]=c; i++; c=getchar(); }

Data[i]='\\0';//数字没有存满,输入字符串结束符

d=atof(Data);//此处是把数组里的数字，实际上是按字符串；转换为double类型，然后把浮点型数字入栈

Push(OPND,d);//atof函数的形参是指针类型，故用数组名 } else {

cout<<\输入错误!\ exit(-1); }

GetTop(OPTR,e); }//while

GetTop(OPND,e); return e; }

4．测试结果

1.运行成功后界面。

2.输入正确的表达式后。

5．参考文献

1.《数据结构(C语言版)》 严蔚敏 清华大学出版社

2.《C语言程序设计》 丁峻岭 中国铁道出版社 3.《C程序设计》 谭浩强 清华大学出版社

附 录--程序源代码

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #include #include using namespace std; typedef double SElemType;

///////////////////////////////////////////////////////////////////////////////// /*以下为栈的操作*/

typedef struct SqStack //栈的顺序存储结构 {

SElemType *base;