软件综合实习算术表达式实验报告.pdf

算术表达式求值实验报告

1.实验题目

求一个可能包含加，减，乘，除，乘方的中缀表达式的值。

2.需求分析

程序用栈和序列编写，首先将中缀表达式转换到后缀表达式，然后对后缀表达

求值。

①输入的形式和输入值的范围：输入包含加、减、乘、除、乘方运算的中缀表达式；

②输出的形式：先把中缀表达式转换为后缀表达式，再对后缀表达式求值，输出一个整

数。

③程序所能达到的功能：能对包含加，减，乘，除，乘方的中缀表达式求值。

④测试数据：

31*(5-(-3+25))+70^2输出结果为4374

2*5+6*(7-8)+6输出结果为10

3.概要设计

1)为了实现上述程序的功能，需要定义操作数栈和运算符栈:

typedefintStatus;

{templatetypenameT1,typenameT2StatusInitStack(T1S){S.base=(T2*)m

alloc(STACK_INIT_SIZE*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base;/

/顺序栈结构

floatdata[MaxSize];

inttop;

}OpStack,SeqStack;

voidInitStack(SeqStacks);//初始化

voidPush1(SeqStackS1,chare);//声明入栈函数

voidPush2SeqStack2S2,floate);//声明入压栈函数

intStackEmpty(SeqStacks);//判断栈是否为空

intGetTop(SeqStacks,DataType*e);//取栈顶元素

intPushStack(SeqStacks,DataTypee);//入栈

intPopStack(SeqStacks,DataType*e);//出栈

voidTranslateE(chars1[],chars2[]);//将中缀表达式转化为后缀表达式

floatComputeE(chars[]);//计算后缀表达式

2)本程序包含7个函数：

①主函数main()

②计算后缀表达式的函数ComputeE()

③中缀表达式转换为后缀表达式的函数TranslateE()

④初始化栈InitStack()

⑤判断栈是否为空的函数StackEmpty()

⑥入栈函数PushStack()

⑦出栈函数popStack()

4.详细设计

部分重要伪码算法:

1)栈的定义

typedefstruct

{

floatdata[MaxSize];

inttop;

}OpStack,SeqStack;

2)判断栈是否为空

/*若栈S为空栈，则返回TRUE，否则返回FALSE*/

StatusStackEmpty(LinkStackS)

{

if(S.count==0)

returnTRUE;

else

returnFALSE

/*把S置为空栈*/

StatusClearStack(LinkStack*S)

{

LinkStackPtrp,q;

p=S-top;

while(p)

{

q=p;

p=p-next;

free(q);

}

S-count=0;

returnOK;

}

3）中缀表达式转换为后缀表达式

voidTranslateE(charstr[],charexp[])

{

SeqStacks;

charch;

DataTypee;

inti=0,j=0;

InitStack(s);

ch=str[i];

i++;

while(ch!=\0)/