以前大二，上数据结构的时候，书上提到了将式子，比如"-(100+52)*2"输入，然后就可以输出计算结果的算法实现，可一直没试，没想到实现起来还真麻烦，有许多容错机制需要注意，这是我到现在为止没发现任何使用限制（当然运算符只限于+、-、*、/和括号运算符）的版本了，拿来分享，望不吝赐教。
#include<stdio.h>
#include<stdlib.h>
#define INPUT_LENGTH 100
#define MAX_INT_LENGTH 5
struct operates {
char operate;
struct operates * next_operator;
};
struct operands{
int operand;
struct operands * next_operand;
};
int separator(char *,struct operates **,struct operands **);
int calculate(struct operates *,struct operands *);
int ganerate(int,int,char);
int asc_to_int(char *,int *actual_int);
void main()
{
char whether_to_exit,input_string[INPUT_LENGTH];
struct operates *head_of_operators;
struct operands * head_of_operands;
int the_result;
whether_to_exit='n';
while(whether_to_exit!='q' && whether_to_exit!='Q') //用于判断一次计算完毕，用户是否要进行下一次计算。
{
printf("Please input the formula you wanna calculate:\n");
gets(input_string);
if(separator(input_string,&head_of_operators,&head_of_operands)==-1)
{
printf("You have input an invalid formula,please try again\n");
continue;
}
the_result=calculate(head_of_operators,head_of_operands);
printf("The result of the formula above is:%d\n",the_result);
}
printf("Thank you for using my programme;)");
}
int separator(char *input_string,struct operates **head_of_operators,struct operands **head_of_operands)//提取字符串中的操作数和操作符，不进行检错。
{
struct operates *op1;
struct operands *op2;
int int_from_string,mark_for_minor,return_from_asc_to_int,counter_for_left,counter_for_right;
char tmp_char,phase_char,*tmp_ptr;
op1=op2=phase_char=NULL;
mark_for_minor=counter_for_left=counter_for_right=0;
tmp_ptr=input_string;
///////检错部分
tmp_char=*tmp_ptr;
if(tmp_char=='+' || tmp_char=='*' || tmp_char=='/' || (tmp_char=='-' && (*(input_string+1)!='(' && (*(input_string+1)<'0' || *(input_string+1)>'9'))))
return -1;
while(*(input_string+1)!=NULL)
input_string++;
if(*input_string!=')' && !(*input_string>='0' && *input_string<='9') && *input_string!=' ')
return -1;
/////////检错完结
/////////以下对以负号打头的式子进行处理：
if(*tmp_ptr=='-')
{
op2=(struct operands *)malloc(sizeof(struct operands));
*head_of_operands=op2;
op2->next_operand=NULL;
op2->operand=0;
}
//////处理结束
while(*tmp_ptr!=NULL)
{
tmp_char=*tmp_ptr;
if(tmp_char==' ')
{
tmp_ptr++;
continue;
}
if(tmp_char >='0' && tmp_char <='9')//提取其中数字，然后将缓冲区指针向前推进。
{
phase_char=NULL;
if((return_from_asc_to_int=asc_to_int(tmp_ptr,&int_from_string))==-1)
{
printf("Too large int.\n");
return -1;
}
tmp_ptr+=return_from_asc_to_int;
if(op2==NULL)
{
op2=(struct operands*)malloc(sizeof(struct operands));
if(mark_for_minor==1)
{
op2->operand=0-int_from_string;
mark_for_minor=0;
}
else
op2->operand=int_from_string;
op2->next_operand=NULL;
*head_of_operands=op2;
}
else
{
op2->next_operand=(struct operands*)malloc(sizeof(struct operands));
op2=op2->next_operand;
if(mark_for_minor==1)
{
op2->operand=0-int_from_string;
mark_for_minor=0;
}
else
op2->operand=int_from_string;
op2->next_operand=NULL;
}
}
else if(tmp_char=='+' || tmp_char == '-' || tmp_char == '*' || tmp_char == '/' || tmp_char == '(' || tmp_char == ')')
{
//////////以下是检错部分：
if(tmp_char=='(')
counter_for_left++;
if(tmp_char==')')
counter_for_right++;
if(phase_char!=NULL)
{
if(!((tmp_char=='(' && phase_char!=')') || (phase_char=='(' && tmp_char=='-') || (phase_char==')' && tmp_char!='(')))//当两个运算符连续出现时，只能是这几种情况："(-","+(","-(","*(","/(",")+"...
return -1;
}
phase_char=tmp_char;
//////////检错结束
if(op1==NULL)
{
op1=(struct operates *) malloc(sizeof(struct operates));
op1->operate=tmp_char;
op1->next_operator=NULL;
*head_of_operators=op1;
}
else
{
op1->next_operator=(struct operates *) malloc( sizeof(struct operates));
op1=op1->next_operator;
op1->operate=tmp_char;
op1->next_operator=NULL;
}
tmp_ptr++;
if(tmp_char=='(' && *(tmp_ptr) == '-')
{
tmp_ptr++;
mark_for_minor=1;
}
}
else
{
printf("Invalid char(s)!\n");
return -1;
}
}
//////检错部分：
if(counter_for_left!=counter_for_right)
return -1;
}
int calculate(struct operates *head_of_operators,struct operands *head_of_operands)
{
struct operands *operand_polor;
struct operates *operator_polor,*pre;
operand_polor=head_of_operands;
pre=operator_polor=head_of_operators;
if(head_of_operators->next_operator!=NULL && head_of_operators->operate=='(' && head_of_operators->next_operator->operate==')')
{
if(head_of_operators->next_operator->next_operator!=NULL)
return calculate(head_of_operators->next_operator->next_operator,head_of_operands);
else
return head_of_operands->operand;
}
if(head_of_operators->next_operator==NULL)
return ganerate(operand_polor->operand,operand_polor->next_operand->operand,head_of_operators->operate);
else
{
while(operator_polor->next_operator!=NULL && (operator_polor->operate=='(' || operator_polor->next_operator->operate=='(' || (operator_polor->operate=='+' || operator_polor->operate=='-') && (operator_polor->next_operator->operate=='*' || operator_polor->next_operator->operate=='/')))
{
if(operator_polor->operate=='(' && operator_polor->next_operator->operate==')')
{
pre->next_operator=operator_polor->next_operator->next_operator;
return calculate(head_of_operators,head_of_operands);
}
else
{
pre=operator_polor;
if(operator_polor->operate!='(')
operand_polor=operand_polor->next_operand;
operator_polor=operator_polor->next_operator;
}
}
operand_polor->operand=ganerate(operand_polor->operand,operand_polor->next_operand->operand,operator_polor->operate);
operand_polor->next_operand=operand_polor->next_operand->next_operand;
pre->next_operator=operator_polor->next_operator;
if(operator_polor==head_of_operators)
return calculate(head_of_operators->next_operator,head_of_operands);
else
return calculate(head_of_operators,head_of_operands);
}
}
int ganerate(int op1,int op2,char operate)
{
switch(operate)
{
case '+':return(op1+op2);
case '-':return(op1-op2);
case '*':return(op1*op2);
case '/':return(op1/op2);
}
}
int asc_to_int(char *input_string,int *actual_int)
{
int j;
char tmp_for_int[MAX_INT_LENGTH+1],*tmp_ptr;
j=0;
tmp_ptr=input_string;
while(*tmp_ptr>='0' && *tmp_ptr<='9')
{
if(j > MAX_INT_LENGTH-1)
return -1;
tmp_for_int[j]=*tmp_ptr;
tmp_ptr++;
j++;
}
tmp_for_int[j]='\0';
*actual_int=atoi(tmp_for_int);
return j;
}
以下是打好包的程序，解压可直接运行：
