数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序

数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序本文简介：实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）

数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序本文内容：

实习报告

题目：设计一个演示用运算优先法对算数表达式求值过程的程序。

班级：

姓名：

学号：

完成日期：

一、

需求分析

1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.

2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。

3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。

4测试数据见原题。

5程序执行的命令包括：

（1）

建立算数表达式；

（2）

得到运算表达式的值；

（3）

演示运算过程。

二、

概要设计

1.

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

ADT

Stack{

数据对象

D＝{

ai

|

ai

∈charSet,i=1,2,.,n,n≥0

}

数据关系：

R1＝{

|

ai-1,ai∈D,i=2,.,n

}

（约定an

端为栈顶，a1

端为栈底）

基本操作：

InitStack（

inttop;

int

stacksize;

}SqStack1;//操作数栈

typedef

struct{

charbase;

chartop;

int

stacksize;

}SqStack2;//操作符栈

2、

栈类型

typedef

struct{

charbase;

chartop;

int

stacksize;

}Stack;

//栈类型

栈的基本操作设置如下：

void

InitStack(Stack

S.top=p;

S.size++;

Return

TRUE;

}

else

return

FALSE;

}

Status

Pop(Stack

else{

p=S.top;S.top=S.top->next;

e=p->:data;S.size--;

return

TRUE;

}

}

3、运算代码

int

Operate(int

a,char

theta,int

b)

//计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值

{

int

c;

if(theta==

+

)

c=a+b;

else

if(theta==

-

)

c=a-b;

else

if(theta==

)

c=a*b;

else

c=a/b;

return

c;

}//Operate

int

result(SqStack1OPND,SqStack2OPTR)

//求值

{

char

a=0;

char

theta;

int

b,c,number=0;

IntInitStack(OPND);

CharInitStack(OPTR);

CharPush(OPTR,#

);

a=getchar();

while(a!=

#

||

CharGetTop(OPTR)!=

#

)

{

printf(“输入字符：%c

“,a);

if(!In(a))//不是运算符则进栈

{

number=0;

while(!In(a))

{

number

=

number*10

+(a-48);//处理多位整数z=10*x+y

a

=

getchar();

}

IntPush(OPND,number);

printf(“主要操作：Push(OPND,%d)

“,number);

}

else

switch(Precede(a,CharGetTop(OPTR)))

{

case

:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作：Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈：%d

OPTR栈：%c\n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“The

result

is

%d.\n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

4.主函数和其他函数的代码

void

main()

//主函数，使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“Please

enter

an

expression

with

a

end

of

#

.\n“);

printf(“The

Expression:“);

result(OPND,OPTR);

}

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,#include

#include

#include

#define

STACK_INIT_SIZE

100

#define

STACKINCREMENT

10

#define

ERROR

0

#define

OK

1

//********************************************栈模块

typedef

struct

SqStack1//运算数栈

{

intbase;

inttop;

int

stacksize;

}SqStack1;

typedef

struct

SqStack2//运算符栈

{

charbase;

chartop;

int

stacksize;

}SqStack2;

void

IntInitStack(SqStack1S)

{

S->base=(int)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

void

CharInitStack(SqStack2S)

{

S->base=(char)malloc(STACK_INIT_SIZE*sizeof(char));

if(!S->base)

exit(ERROR);

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;

}

int

IntGetTop(SqStack1S)

//取栈顶元素

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

char

CharGetTop(SqStack2S)

//取栈顶元素

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*((*S).top-1);

return

e;

}

int

IntPush(SqStack1S,int

e)

{(*S).top++=e;

return

OK;

}

int

CharPush(SqStack2S,char

e)

{(*S).top++=e;

return

OK;

}

int

IntPop(SqStack1S)

{

int

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

int

CharPop(SqStack2S)

{

char

e;

if((*S).top==(*S).base)

return

0;

e=*--(*S).top;

return

e;

}

//——————————————————*******************运算模块

char

Precede(char

a,char

b)//运算优先级判断

{

int

i,j;

char

Table[8][8]={,+,-,*,/,(,),#,+,>,>,,>,-,>,>,,>,*,>,>,>,>,,>,/,>,>,>,>,,>,(,,>,>,>,,>,>,#,:

theta=CharPop(OPTR);

c=IntPop(OPND);

b=IntPop(OPND);

IntPush(OPND,Operate(b,theta,c));

printf(“主要操作：Operate(%d,%c,%d)

“,b,theta,c);

break;

}

printf(“OPND栈：%d

OPTR栈：%c\n“,IntGetTop(OPND),CharGetTop(OPTR));

}

printf(“\n结果:%d.\n“,IntGetTop(OPND));

//打印输出表达式值

return

OK;

}

//————————————————————————主程序模块

void

main()

//主函数，使用自定义函数完成功能

{

SqStack1

s1,*OPND;

SqStack2

s2,*OPTR;

OPND=

OPTR=

printf(“请输入算数表达式并以

#

结尾.\n“);

printf(“算数表达式:“);

result(OPND,OPTR);

}