数据结构与算法 计算表达式(一)
一、简单说明
计算中缀表达式。比如1+2*3、（56-20-6）/(4+2-1)。
二、实现主要思路
1、为各运算符指定优先级
说明：‘=’是为了辅助比较运算符，这样子设置优先级，只有括号情况下才会有优先级相等的情况。
2、逐个扫描算数表达式，运算数用一个栈(num)存储、运算符用一个栈(op)存储
3、当右运算符优先级低于左运算符时，op栈弹出一个运算符，num栈弹出两个运算数，然后进行计算。
4、扫描表达式结束，继续扫描执行先压栈而没有执行的运算符
5、最后num栈的第一个元素就是表达式的结果。
举例说明：表达式 (56-20)/(4+2)
三、效果
四、源码
exp.c源文件
#include <stdio.h>
#include <stdlib.h> //memset()函数所在的头文件
#define SIZE 100 //定义临时存放数据的空间大小
struct OP //运算符结构体 (这个结构体其实是一个栈的结构)
{
char data[SIZE]; //存放运算符
int top; //相当于栈顶指针
}op; //定义结构体变量，op存放运算符
struct NUM//运算数结构体 (这个结构体其实是一个栈的结构)
{
float data[SIZE]; //存放运算数
int top; //相当于栈顶指针
}num; //定义结构体变量，num存放运算数
struct PRI //用来存储运算符的优先级
{
char op; //运算符
int pri; //优先级
};
//定义左运算符优先级结构体数组
struct PRI lpri[] = {{'=',0},{'(',1},{'+',3},{'-',3},{'*',5},{'/',5},{')',6}};
//定义右运算符优先级结构体数组
struct PRI rpri[] = {{'=',0},{'(',6},{'+',2},{'-',2},{'*',4},{'/',4},{')',1}};
//函数声明部分
int LeftPri(char op);//求左运算符op的优先级
int RightPri(char op);//求右运算符op的优先级
int IsOp(char ch);//判断ch是否是运算符
int JudgePri(char lop,char rop); //判断左右运算符的优先级
float CountExp(char* exp);//计算表达式
float Str2Float(char* str); //字符串转换为 float数字
void Count(char op);//*/+-运算
int main(int argc,char* argv[])
{
char exp1[] = "(56-20-6)/(4+2-1)" ;
char exp2[] = "5-1*2*3+12/2/2";
float res = CountExp(exp1);
printf("(56-20-6)/(4+2-1)的结果是：%lf\n",res);
res = CountExp(exp2);
printf("5-1*2*3+12/2/2的结果是：%lf\n",res);
return 0;
}
int LeftPri(char op)//求左运算符op的优先级
{
int i = 0;//计数器
for(i = 0;i < sizeof(lpri)/sizeof(lpri[0]);i++)//求左运算符的个数sizeof(lpri)/siozeof(lpri[0])
{
if(lpri[i].op == op)//如果 左运算符结构体有匹配的运算符
{
return lpri[i].pri;//返回对应的运算符的优先级
}
}
return -1;//没有匹配的运算符
}
int RightPri(char op)//求右运算符op的优先级
{
int i = 0;//计数器
for(i = 0;i < sizeof(rpri)/sizeof(rpri[0]);i++)//求右运算符的个数sizeof(lpri)/siozeof(lpri[0])
{
if(rpri[i].op == op)//如果 右运算符结构体有匹配的运算符
{
return rpri[i].pri;//返回对应的运算符的优先级
}
}
return -1;//没有匹配的运算符
}
int IsOp(char ch)//判断ch是否是运算符
{
//如果是指定的运算符则返回1，否则返回0
if(ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '(' || ch == ')' )
{
return 1;
}
else
{
return 0;
}
}
int JudgePri(char lop,char rop)//判断左右运算符的优先级 左运算符大于右运算符返回1，相等返回0，左小于右返回-1
{
if(LeftPri(lop)> RightPri(rop))//左运算符大于右运算符返回1
{
return 1;
}
else if(LeftPri(lop)== RightPri(rop))//相等返回0，只有左右括号这一种情况
{
return 0;
}
else //左运算符小于右运算符返回-1
{
return -1;
}
}
float CountExp(char* exp) //计算表表达式
{
memset(&(num.data),0,SIZE); //将num结构体中的数组data清零
memset(&(op.data),0,SIZE); //将op结构体中的数组data清零
num.top = -1; //初始化栈顶指针
op.top= -1;
op.data[++op.top] = '='; //将'='进栈 ,先++
int i = 0; //用来指示str位置
char str[10] = {0};//临时存放字符串数字
while(*exp!='\0') //循环扫描exp表达式
{
if(!IsOp(*exp)) //如果不是运算符
{
i = 0;
memset(str,0,10);//每循环一次次清零
while(*exp>='0' && *exp<='9')//是数字
{
str[i++] = *exp++ ;//将数字字符添加到str中,添加后i加1
}
str[i++] = '#';//人为加上结束符 ，辅助进行字符串转换为 float数字
num.data[++num.top] = Str2Float(str);//将字符串转换为 float数字并赋值给 num的data数组，注意top先++；
}
else //是运算符
{
switch(JudgePri(op.data[op.top],*exp))
{
case -1://栈顶的运算符优先级低，进栈
op.data[++op.top] = *exp;
break;
case 0://优先级一样，说明是括号 ，只有这一种情况
op.top--;//将'('退栈
break;
case 1://栈顶的运算符优先级高，先出栈进行计算，后入栈
do
{
Count(op.data[op.top--]);//*/+- 运算
}while(JudgePri(op.data[op.top],*exp) == 1);//直到栈顶的运算符优先级不比 右运算符的优先级高，才准备将右运算符入栈
if(*exp != ')')//如果不是')'才入栈
{
op.data[++op.top] = *exp;
}
break;
default:
break;
}
exp++;//继续向下扫描exp
}
}
for(i = op.top;i>0;i--)//因为上面是按根据表达式执行的，扫描执行先压栈而没有执行的
{
Count(op.data[i]);
}
return num.data[0]; //执行完毕，num.data的第一个元素就是结果
}
float Str2Float(char* str) //字符串转换为 float数字
{
float flt = 0.0;
while(*str >= '0' && *str <= '9')//是数字
{
flt = 10*flt+*str++-'0';
}
//*str-'0'解释,比如当str="520"，*str是字符'5'时，字符'5'的ASCII码 是 53，
//而字符'0' 的ASCII码是48，那么 *str-'0' 的值是5，完成字符数字到数字的转换
// 10*解释： 比如当str="520"，
//第一次时flt = 10*0.0+'5'-'0' ==>是5
//第二次时flt = 10*5.0+'2'-'0' ==>是52
//第三次时flt = 10*5.0+'2'-'0' ==>是520 完成字符串数字到数字的转换
return flt;
}
void Count(char op)//*/+-运算
{
float temp = 0.0; //用来存放临时计算结果;
switch(op)
{
case '*':
temp = num.data[num.top--];//取出两个数相乘
temp *= num.data[num.top--];
num.data[++num.top] = temp;//将计算结果进栈
break;
case '/':
temp = num.data[num.top--];//取出被除数 注意是倒着取的
if(temp==0) //被除数不能为0
{
printf("\n被除数为0\n");
return;
}
temp = num.data[num.top--]/temp; //取出除数 1 ÷2 1是除数，2是被除数
num.data[++num.top] = temp;//将计算结果进栈
break;
case '+':
temp = num.data[num.top--];//取出两个数相加 ，顺序不影响相加
temp += num.data[num.top--];
num.data[++num.top] = temp;//将计算结果进栈
break;
case '-':
temp = (num.data[num.top--]);//取出被减数 ,注意是倒着取的
temp = (num.data[num.top--])-temp;
num.data[++num.top] = temp;//将计算结果进栈
break;
default:
break;
}
}
五、注意
有待进一步测试。
Code
