数据结构实验2Word文档格式.docx

数据结构实验2Word文档格式.docx

《数据结构实验2Word文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构实验2Word文档格式.docx（8页珍藏版）》请在冰点文库上搜索。

算术表达式求值

利用题目一所定义的栈（顺序栈或链栈）实现算术表达式求值运算，并进行验证给出结果。

三、实验问题描述

这里限定的算术表达式求值问题是：

用户输入一个包含“+”、“—”、“*”、“/”、正整数和圆括号的合法算术表达式，计算该表达

式的运算结果。

四、实验步骤

1．实验问题分析

数据组织：

在设计相关算法中用到栈，这里采用顺序栈存储结构

设计运算算法：

①将算术表达式转换成后缀表达式

②后缀表达式求值

③设计求解程序

④运行结果

2．功能（函数）设计

voidmain（）

{

charexp[]="

（56-20）/（4+2）"

;

charpostexp[MaxSize];

trans（exp,postexp）;

printf（"

中缀表达式：

%s\n"

exp）;

后缀表达式：

postexp）;

表达式的值：

%g\n"

compvalue（postexp））;

}

五、实验结果（程序）及分析

#include<

iostream>

usingnamespacestd;

#defineMaxOp50

#defineMaxSize50

struct

{charch;

intpri;

lpri[]={{'

='

0},{'

（'

1},{'

*'

5},{'

/'

+'

3},{'

-'

）'

6}},

rpri[]={{'

6},{'

4},{'

2},{'

1}};

intleftpri（charop）

inti;

for（i=0;

i<

MaxOp;

i++）

if（lpri[i].ch==op）

returnlpri[i].pri;

intrightpri（charop）

if（rpri[i].ch==op）

returnrpri[i].pri;

intInOp（charch）if（ch=='

||ch=='

）

return1;

else

return0;

intPrecede（charop1,charop2）

if（leftpri（op1）==rightpri（op2））

elseif（leftpri（op1）<

rightpri（op2））

return-1;

voidtrans（char*exp,charpostexp[]）

struct

chardata[MaxSize];

inttop;

}op;

inti=0;

op.top=-1;

op.top++;

op.data[op.top]='

while（*exp!

\0'

）

if（!

InOp（*exp））

while（*exp>

0'

&

*exp<

9'

postexp[i++]=*exp;

exp++;

postexp[i++]='

#'

else

switch（Precede（op.data[op.top],*exp））

case-1:

op.data[op.top]=*exp;

break;

case0:

op.top--;

case1:

postexp[i++]=op.data[op.top];

while（op.data[op.top]!

{

postexp[i]='

floatcompvalue（char*postexp）

floatdata[MaxSize];

}st;

floatd,a,b,c;

st.top=-1;

while（*postexp!

switch（*postexp）

case'

:

a=st.data[st.top];

st.top--;

b=st.data[st.top];

c=a+b;

st.top++;

st.data[st.top]=c;

case'

c=b-a;

c=a*b;

if（a!

=0）

c=b/a;

\n\t除0错误\n"

）;

exit（0）;

default:

d=0;

while（*postexp>

*postexp<

d=10*d+*postexp-'

postexp++;

st.data[st.top]=d;

return（st.data[st.top]）;

voidmain（）

六、结论与分析

在本次实验中掌握了栈的定义，学会栈的初始化，掌握栈的前缀、中缀以及后缀表达式求值和前缀、中缀和后缀表达式相互之间的转换，感觉在实验中也遇到不少问题，都有相对的解决。