用栈实现表达式计算文档格式.docx
《用栈实现表达式计算文档格式.docx》由会员分享，可在线阅读，更多相关《用栈实现表达式计算文档格式.docx（34页珍藏版）》请在冰点文库上搜索。
图3中缀转后缀表达式算法countfor（）函数流程图
利用两个栈（数字栈和符号栈）直接对表达式求值。
图4为算法二中main（）函数的算法流程图，主要功能为：
图4表达式直接求值算法main（）函数流程图
图5为算法二中Countfor（）函数的算法流程图，主要功能为：
利用两个栈直接对表达式进行取值计算。
图5表达式直接求值算法Countfor（）函数流程图
图6为算法二中Judge（）函数的算法流程图，主要功能为：
判断运算符并根据判断将两个数进行相应的计算，返回计算结果。
图6表达式直接求值算法Judge（）函数流程图
三、源代码
下面给出的是用一个栈对表达式中缀转后缀再进行运算的算法实现的程序的源代码：
#include"
stdafx.h"
stdio.h"
malloc.h"
stdlib.h"
#defineSTACK_INIT_SIZE10//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
typedefstruct
{//构建数字栈
double*base;
//在栈构造之前和销毁之后，base的值为NULL
double*top;
//栈的顶指针
intstacksize;
//当前已分配的存储空间，以元素为单位
}Od;
voidInitStack（Od&
S）
{//创建一个栈
S.base=（double*）malloc（STACK_INIT_SIZE*sizeof（double））;
//分配类型为double
if（!
S.base）
{
printf（"
OVERFLOW!
"
）;
//存储分配失败
}
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}//InitStack
staticGetTop（OdS,double&
e）
{//看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；
否则，0
if（S.top>
S.base）//栈不空
e=*（S.top-1）;
//将栈顶元素赋给e
return1;
elsereturn0;
}//GetTop
voidPush（Od&
S,doublee）
{//插入元素e为新的栈顶
if（S.top-S.base>
=S.stacksize）//栈满，追加存储
{
S.base=（double*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（double））;
exit（0）;
S.top=S.base+S.stacksize;
//修改站顶指针，指向新的栈顶
S.stacksize+=STACKINCREMENT;
//更新当前已分配的存储空间
*（S.top）++=e;
将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元
}//Push
staticPop（Od&
S,double&
{//删除S的栈顶元素，用e返回其值
if（S.top==S.base）return0;
e=*--S.top;
}//Pop
voidDestroyStack（Od&
{//销毁栈S
free（S.base）;
//释放栈空间
S.top=S.base=NULL;
//栈顶、栈底指针均为空
S.stacksize=0;
//当前已分配内存空间为0
}//DestroyStack
staticStackEmpty（OdS）
{//判断栈是否为空，栈空返回1，否则，返回0。
if（S.top==S.base）//空栈条件
else
return0;
}//StackEmpty
{//构建字符栈
char*base;
//在栈构造之前和销毁之后，base的值为NULL
char*top;
//栈的顶指针
//当前已分配的存储空间，以元素为单位
}Op;
voidInitStack（Op&
S.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
//分配类型为char
printf（"
//存储分配失败
staticGetTop（OpS,char&
{//看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；
elsereturn0;
}//GetTop
voidPush（Op&
S,chare）
if（S.top-S.base>
S.base=（char*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（char））;
//修改站顶指针，指向新的栈顶
//将e入栈，成为新的栈顶元素，栈顶指针上移1个存储单元
staticPop（Op&
S,char&
voidDestroyStack（Op&
staticStackEmpty（OpS）
intmain（intargc,double*argv[]）
voidMid_Back（chara[]）;
//中缀表达式转后缀表达式函数
inti=0;
//str[]数组的下脚标
intj=0;
//str_pass数组的下脚标
charstr[50];
//接受用户输入字符的数组
charstr_pass[50];
//接受数字字符的数组
请输入算数表达式：
\n"
scanf（"
%s"
&
str）;
//输入表达式
while（str[i]!
='
\0'
）//对str[]数组进行循环，知道str[i]为'
if（（str[i]>
0'
&
str[i]<
9'
）||str[i]=='
.'
）//如果str[i]是数字或者点
{
str_pass[j]=str[i];
//则将其赋给str_pass[]数组
j++;
i++;
（（str[i]>
））//再对下一个数组中的元素进行判断
str_pass[j]='
#'
;
//如果不是数字或者点，则添加#
j++;
}
else
//将运算符传到数组中
Mid_Back（str_pass）;
//将表达式传入中转后缀函数中
return0;
}
/**************中缀表达式转后缀表达式函数*****************/
voidMid_Back（chara[]）
{//中缀表达式转后缀表达式函数
inti=0;
//数组a[]下脚标
intj=0;
//数组Ba_str[]下脚标
charBa_str[50];
chare;
OpOp;
//声明符号栈函数
InitStack（Op）;
//创建一个符号栈
voidcountfor（charBa_str[]）;
//声明求值函数
for（i=0;
a[i]!
i++）
{//对数组a[]进行循环
if（（a[i]>
a[i]<
）||a[i]=='
||a[i]=='
）
{//判断a[i]是否为数字、点或者’#’，是则将元素传递到Ba_str[]数组中；
否则，再次进行判断
Ba_str[j]=a[i];
%c"
Ba_str[j]）;
j++;
else{
GetTop（Op,e）;
//看栈顶
if（StackEmpty（Op）||e=='
（'
||（（e=='
+'
||e=='
-'
）&
（a[i]=='
*'
%'
/'
））||a[i]=='
{Push（Op,a[i]）;
else{if（a[i]=='
）'
{//如果现有元素为’）’，则运算符出栈
Pop（Op,e）;
for（;
e!
{//直到出栈元素为’（’
Ba_str[j]=e;
//将出栈的运算符赋给Ba_str[j]
printf（"
//
//运算符出栈
}
else{//如果现有元素不为’）’,则运算符出栈
Pop（Op,e）;
Ba_str[j]=e;
//将出栈的运算符赋给Ba_str[j]
printf（"
j++;
GetTop（Op,e）;
if（StackEmpty（Op）||e=='
//对栈顶元素与现有元素进行优先级比较，符合以上情况的，现有元素进栈
{Push（Op,a[i]）;
else{//否则运算符出栈
Pop（Op,e）;
Push（Op,a[i]）;
//将现有元素放到栈中
Ba_str[j]=e;
}
while（!
StackEmpty（Op））//输出栈中所有运算符
{Pop（Op,e）;
Ba_str[j]=e;
DestroyStack（Op）;
//销毁栈
countfor（Ba_str）;
//将数组传递给求值函数
/*************************表达式求值函数*******************************/
voidcountfor（charBa_str[]）
OdOd;
//声明数字栈函数
InitStack（Od）;
//创建一个数字栈
//数组Consist[]下脚标
doublee;
intk=0;
doubleOd1,Od2;
charConsist[20];
Ba_str[i]!
{//对数组进行循环
if（（Ba_str[i]>
Ba_str[i]<
）||Ba_str[i]=='
||Ba_str[i]=='
{//如果元素为数字、点或者’#’，则将元素赋给Consist[j]
Consist[j]=Ba_str[i];
i++;
if（Ba_str[i]=='
{//如果元素为’#’
e=strtod（Consist,NULL）;
//利用strtod函数将字符串转换成double类型的数字
Push（Od,e）;
//数字进栈
for（j=0;
j<
20;
j++）//清空数组Consist[]以便重新使用
{Consist[j]='
j=0;
else--i;
{//否则，从数字栈中取两个数
Od1=Od2=0;
Pop（Od,e）;
Od2=e;
Od1=e;
switch（Ba_str[i]）
{//判断运算符
case'
:
{e=Od1-Od2;
Push（Od,e）;
break;
}//运算符为减号，则两数相减
{e=Od1+Od2;
}//运算符为加号，则两数相加
{e=Od1*Od2;
}//运算符为乘号，则两数相乘
{e=Od1/Od2;
}//运算符为除号，则两数相除
{k=（int）Od1%（int）Od2;
Push（Od,k）;
}//运算符为取余号，则两数相除取余
//degault:
//将表达式的结果“扔出”栈
=%f"
e）;
//对表达式的结果进行输出
DestroyStack（Od）;
下面给出的是用两个栈直接对表达式进行运算的算法实现的程序的源代码：
double*base;
double*top;
intstacksize;
S.base=（double*）malloc（STACK_INIT_SIZE*sizeof（double））;
if（!
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
if（S.top>
e=*（S.top-1）;
return1;
}
elsereturn0;
if（S.top-S.base>
=S.stacksize）//如果栈满，追加存储
S.base=（double*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（double））;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*（S.top）++=e;
if（S.top==S.base）return0;
e=*--S.top;
free（S.base）;
if（S.top==S.base）//空栈条件
else
return0;
/***********************************/
char*base;
char*top;
S.base=（char*）malloc（STACK_INIT_SIZE*sizeof（char））;
{//看栈顶，若栈非空，用e返回S的栈顶元素，并返回1；
return1;
if（S.top-S.ba
升级会员 