表达式计算器(数据结构) - 中科因仑“3+1”工程特种兵精英论坛

//我们首先建立一个动态双向链表：
/* 建立一个头结点*/
Formula_head = new node;
init_node(Formula_head);
Formula_head->ch = getchar();
Formula_follow = Formula_head;
/* 从用户读取输入*/
for(;;){
newnode = new node; /* 新增加一个节点来存储输入*/
init_node(newnode); /* 初始化节点数据 */
while(1){ /* 获取输入数据，并且删除空格*/
newnode->ch = getchar();
//cin >> newnode->ch ;
if(' ' != newnode->ch ){
//print_link_data(Formula_follow);
break;
}
}
/* 结束输入*/
if('\n' == newnode->ch){
break;
}
/* 加入节点*/
Formula_follow = add_node(Formula_follow, newnode);
}
//读取表达式之后，需要对表达式进行校对，处理未知数和防止输入不规则表达式（错误表达式）：
/* 检查是否是未知数算式*/
if( check_unknow(Formula_head) ){
x_head = Formula_head;
Formula_head = NULL;
X_flag = 1;
continue;
}
/*如果有未知数的处理*/
if(X_flag){
Formula_head = add_x_in_link(Formula_head,x_head);
}
/*检查错误*/
if(check(Formula_head)){
continue;
}
/***************************************************
** 函数名称：check
** 函数功能：扫描链表,检查表达式是否错误
** 入口参数：node *head
** 出口参数：
***************************************************/
int check(node *head)
{
int brackets = 0;
for(; head; head=head->next){
/*连续出现2个运算符，报错*/
if(('+'==head->ch) || ('-'==head->ch) ||
('*'==head->ch) || ('/'==head->ch)){
if(('+'==head->next->ch) || ('-'==head->next->ch) ||
('*'==head->next->ch) || ('/'==head->next->ch)){
cout<<"erro: Consecutive two operators!"<<endl;
return 1;
}
}
/* 括号不匹配，报错*/
if('(' == head->ch){
brackets++;
}
if(')' == head->ch){
brackets--;
if(brackets<0){
cout<<"erro: brackets is not right,please check it out!"<<endl;
return 1;
}
}
}
/* 括号不匹配*/
if(0 != brackets){
cout<<"erro: brackets is not right,please check it out!"<<endl;
return 1;
}
/*没错返回0*/
return 0 ;
}
/***************************************************
** 函数名称：check_unknow
** 函数功能：检查是否为未知数算式
** 入口参数：node *head
** 出口参数：
***************************************************/
int check_unknow(node *head)
{
if(('x'==head->ch) && ('='==head->next->ch) && (NULL!=head->next->next)){
return 1 ;
}
return 0;
}

复制代码

/***************************************************
** 函数名称：*mid_to_bk
** 函数功能：中缀转换成后缀表达式
** 入口参数：node *head
** 出口参数：
***************************************************/
node *mid_to_bk(node *head)
{
node *mid = Separate_str(head); /* 处理后的中缀表达式链表*/
node *bk = NULL; /* 后缀表达式头指针*/
node *ptr = bk;
node *oper = NULL; /* 符号堆栈 */
node *newnode = NULL;
node *code_node = NULL; /* 用来记录，保存地址 */
/* 开始转换*/
for(; mid; mid=mid->next){
/* 将节点数据拷贝到新节点去*/
newnode = new node;
init_node(newnode);
copy_node_data(newnode,mid);
/* 如果遇到数字就直接入栈*/
if(NUM == newnode->type){
/*加入链表*/
if(NULL == bk){
ptr = bk = add_node(ptr,newnode);
} else{
ptr = add_node(ptr,newnode);
}
}
/* 如果遇到特殊表达式*/
else if(SP_OPERATOR == newnode->type){
/* 如果前一个运算符也是特殊运算符就要出栈 */
while(oper){
if(SP_OPERATOR == oper->type){
code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
ptr = add_node(ptr,oper);
oper = code_node;
} else break;
}
oper = add_node(oper,newnode);
}
/*如果遇到普通运算符*/
else if(OPERATOR == newnode->type){
/*'('直接进栈*/
if('(' == newnode->ch){
oper = add_node(oper,newnode);
}
/*')'直接退栈到')'*/
else if(')' == newnode->ch){
while(oper){
if('(' == oper->ch)break;/* 遇到'('退栈结束*/
code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
ptr = add_node(ptr,oper);
oper = code_node;
}
oper = del_node(oper); /* 删除掉'('符号*/
}
/* 遇到+-全部退栈，直到遇到'('，或者退完为止*/
else if(('+' == newnode->ch) || ('-' == newnode->ch)){
while(oper){
if('(' == oper->ch)break; /* 遇到'('退栈结束*/
code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
ptr = add_node(ptr,oper);
oper = code_node;
}
oper = add_node(oper,newnode);
}
/* 遇到/* 把特殊运算符全部退栈处理*/
else if(('*' == newnode->ch) || ('/' == newnode->ch)){
while(oper){
if('(' == oper->ch)break; /* 遇到'('和特殊运算符截止*/
if(('+' == oper->ch) || ('-' == oper->ch))break;
code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
ptr = add_node(ptr,oper);
oper = code_node;
}
oper = add_node(oper,newnode);
}
/*
* 下面这段程序是调试使用
*/
#if 0
cout<<"mid: ";
print_link_data(test);
getchar();
#endif
}
}
/* 把最后留在堆栈里面的东西退出来*/
while(oper){
code_node = oper->befor; /* 将这个节点换到后缀表达式里面*/
ptr = add_node(ptr,oper);
oper = code_node;
}
ptr->next = NULL;
/*
* 下面这段程序是调试使用
*/
#if 0
cout<<"mid: ";
print_link_data(bk);
#endif
return bk;
}

复制代码

/***************************************************
** 函数名称：calculate
** 函数功能：对后缀表达式进行计算处理
** 入口参数：node *formula
** 出口参数：result[0]
*******************************************
********/
double calculate(node *formula)
{
double result[200];
int i=0;
for(; formula; formula = formula->next){
/*数据再次进堆栈*/
if(NUM == formula->type){
result = formula->num;
i++;
}
//由于前面进行了中缀表达式转化为逆波兰表达式，因此为这里的计算奠定了十足的运算基础。
/*遇到普通符号就直接进行判断并且计算*/
else if(OPERATOR == formula->type){
/*加法计算*/
if('+' == formula->ch){
i--;
result[i-1] = result[i-1]+result;
}
/*减法计算*/
if('-' == formula->ch){
i--;
result[i-1] = result[i-1]-result;
}
/*乘法计算*/
if('*' == formula->ch){
i--;
result[i-1] = result[i-1]*result;
}
/*除法计算*/
if('/' == formula->ch){
i--;
/* 如果除数是0的话提示错误*/
if(0 == result){
cout<<"erro: the divvisor equal zero!Please check is out!"<<endl;
exit(1);
} else{
result[i-1] = result[i-1]/result;
}
}
}
/*遇到特殊符号*/
else{
/*sin*/
if(!strcmp(formula->str,"sin")){ //进行符号匹配，如果是sin运算符，进行项目的运算。这里读者其实可以进行改进
result[i-1] = sin(result[i-1]);
}
/* cos*/
else if(!strcmp(formula->str,"cos")){
result[i-1] = cos(result[i-1]);
}
/* tan*/
else if(!strcmp(formula->str,"tan")){
result[i-1] = tan(result[i-1]);
}
/* log*/
else if(!strcmp(formula->str,"log")){
result[i-1] = log(result[i-1]);
}
/*sqrt*/
else if(!strcmp(formula->str,"sqrt")){
result[i-1] = sqrt(result[i-1]);
}
/*help*/
else if(!strcmp(formula->str,"help")){
r_file() ;
} else{
cout<<"have no this OPERATOR,if you want add it,please add it upon, thank you!\n"<<endl;
exit(1);
}
}
}
return result[0];
}

复制代码