一、设计思想
计算算术表达式可以用两种方法实现:
1.中缀转后缀算法
此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算.具体实现方法如下:
（1）中缀转后缀
需要建一个操作符栈op和一个字符数组exp,op栈存放操作符，字符数组用来存放转换以后的后缀表达式。首先，得到用户输入的中缀表达式,将其存入str数组中。对str数组逐个扫描，如果是数字或小数点,则直接存入exp数组中，当扫描完数值后,在后面加一个＃作为分隔符。
如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，
出栈存入exp数组,直到遇到左括号，左括号丢掉。然后继续扫描下一个字符,直到遇到str中的结束符号\0，扫描结束。结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空.到此在exp数组最后加结束字符\0。我们就得到了后缀表达式。
（2）后缀表达式计算
此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。继续扫描,知道扫描结束,此时值栈中的数值就是计算的结果,取出返回计算结果。
2。两个栈实现算法
此算法需要两个栈，一个值栈od，一个操作符栈op。将用户输入的数学表达式存入str数组中,对其数组进行逐个扫描。
当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存
入值栈中,一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。
如果遇到操作符，若op栈为空，直接入栈;若栈不为空，与栈顶元素比较优先等级,若比栈顶操作符优先等级高，直接入op栈,如果低于或等于栈顶优先等级，op栈出栈,再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op栈。继续扫描直到遇到str中的结束字符\0，扫描结束。此时看操作符栈是否为空，若不为空，出栈，再从值栈中取出两个数值进行计算，将其结果存入值栈,一直进行此操作，直到操作符栈为空。此时把值栈中的数值取出，即为所得的最终计算结果。
二、算法流程图
第一种算法：中缀转后缀算法
其主函数流程图为:
图1 主函数算法流程图
中缀转后缀算法流程图如下：
图2 中缀转后缀算法流程图
计算后缀表达式流程图如下：
图3 后缀表达式计算流程图
第二种算法:两个栈算法
其主函数流程图为:
图4 主函数算法流程图
直接计算数学表达式流程图如下：
图5 直接计算表达式流程图
三、源代码
下面给出的是用中缀转后缀算法实现的程序的源代码：
#include<stdio.h>
＃include<string.h>
#include〈math。h>
＃include<stdlib。h〉
＃define MAXSIZE 100 //定义宏，数组最大长度为100
//函数实现中缀转后缀，将存储数学表达式的数组str传参进来，exp存储后缀表达式
void trans（char str[］,char exp［])
｛
struct
{
char data[MAXSIZE］；//用来存放操作符
int top；//数组下标
}op；//用结构体创建操作符栈
char ch；
int i=0，j=0，tempi=0；
op.top=-1；//给操作符栈初始化，令下标为—1
while（ch!='\0'）
{
ch=str[i]； //取str数组的第i个元素赋值给ch
if（（ch〉=’0'＆＆ ch<=’9’) ｜｜ ch=='.’)//对数值操作
{
tempi=i；//若ch为数字或小数点,将其下标值赋给临时下标tempi
//依次向后扫描str数组，若一直为数字，跳入while循环
while((ch〉='0’ && ch〈= ’9') ｜｜ ch == '.')
{
tempi++；
exp［j]=ch;//将数字存入exp数组中
j++;
ch=str［tempi]；//取str数组中下标为tempi的元素赋给ch
}
exp[j]=’#’;j++;//用#做分隔符，将数值分隔开
i=tempi;//跳出循环，将此时的tempi赋给i,继续向后扫描
}
//对操作符操作
else if(ch==’+’｜｜ch==’-’｜｜ch=='*'|｜ch=='/’｜｜ch=='％' ｜| ch == ’(' |｜ ch == ’)'）
｛
int level（char op);//声明level函数
if（ch==’（’）//如果为（,直接进栈
｛c语言while语句流程图
op.top++；
op。data［op。top］=ch;//进栈操作
}
else if(ch==’）’)
｛
//如果为）,一直出栈直到遇到(
while（level（op.p］)！=—1)//若栈顶元素不为(,进入while循环
｛
exp[j]=op.p］;//操作符出栈,存入exp数组中
op.top—-;
j++;
if（op。top==-1）break；//如果栈为空，跳出循环
}
op。top—-;//左括号pop出来
｝
else if（op.top==-1)//如果栈为空，直接进栈
｛
op。top++;
op。data［op。top］=ch；//进栈操作
｝
//如果所扫描的操作符优先等级比栈顶元素高,直接进栈
else if(level(ch)>level(op。data［op。top］)）
{
op.top++;
op.data［op.top]=ch;//进栈操作
}
else
｛
//如果所扫描的操作符优先等级没有栈顶元素高,
//一直出栈直到比栈顶元素优先级高
while(level(ch)〈=level(op.data［op.top]))
{
exp[j]=op.data［op.top]；//出栈存入exp数组中
op.top——;
j++；
if（op.top==-1)break;//如果栈为空，跳出循环
}
op.top++;
op。p］=ch;//比栈顶元素优先级高,入栈
}
i++;//str下标加1，向后扫描
｝
｝
while(op。top!=—1)//扫描结束后如果操作符栈不为空，出栈直至为空
{
exp［j]=op。data［op.top］；//出栈存入exp数组中
op。top—-；
j++;
｝
exp［j］=’\0’;//赋\0结束exp字符数组
｝
int level(char op)//判断操作符优先等级
{
if（op == '+’ ｜| op == '—')//若为+、-，等级为1
return 1；
else if(op == ’＊’ ｜| op == ’/’ ｜｜ op == ’％’）
return 2； //若为＊、/、％，等级为2
else if(op == '（’)
return —1 ; //若为(,等级为-1
else
return —3； //其他等级为-3；
｝
double calvalue（double od1,double od2，char tempop)//计算
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论