post_bintree.c

用C语言实现一个简单数学计算器

#include <stdio.h>
#include <io.h>
#include <malloc.h>
#define LEN  255


//type
//node * pnode;
//op=-1/( ;-2/);-3/#;

typedef struct 
{int NodeClass;
 void * left,* right;
 int data;
}node;

typedef  node* pnode;
pnode bt;//树的根结点
int stack_op[LEN];  //操作符
int top_op; 
char temp[2];
int poststr[LEN];
char instr[LEN];
int postp,inp;


init_stack()//初始化
{
  top_op=0;
}

int push_op(int op)//入
{
  if (top_op==LEN) return -1; //满
  stack_op[top_op]=op;
  top_op++;
  return 0;
}

int pop_op() //弹
{
  --top_op;
  return stack_op[top_op];
}

int empty_op()//空？
{
  if (top_op==0) return 1; //空
  return 0;
}

int getnum(char ch)
{
  temp[0]=ch;
  temp[1]=0;
  return atoi(temp);
}

int comp(f_num)//比较优先级
{ char temp;
  if (empty_op()) return -1; //空
  temp=pop_op(); push_op(temp);
  if (temp==-1) {if (f_num>=1) return 1;}
	    else if (temp==-3) return 1;//#
		else   switch (instr[temp])
				{       case '+':
						case '-':{if (f_num>2) return 1;break;}
						case '*':
						case '/':{if (f_num>3) return 1;break;}
						default:return -1;
				}
	return 0;
}

int compu() //计算
{ int op1;
   if (empty_op())  {printf("  \nERROR INPUT");exit(0);}  op1=pop_op();poststr[postp]=op1;postp++;
    return 0;
}

void destroytree(pnode p)
{ if (p==NULL) return;
if (p->NodeClass==1) {free(p);return;}
if (p->NodeClass==0) {destroytree(p->left);destroytree(p->right);return;}
else exit(0);
}

main(int argc,char * argv[])
{ char ch;
  int flag,i;
  int pro,popop;
  float result;
  init_stack(); push_op(-3);flag=1;memset(poststr,0,LEN);postp=0;
  memset(instr,0,LEN);inp=0;

  if (argc!=2) {printf("请在命令行写出表达式！\n"); exit(0);}
  while ( (ch=argv[1][0]) != 0  )
  { 
   switch (ch)
	{case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	case '0':{instr[inp]=ch;poststr[postp]=inp;inp++;postp++;break;}
	case '+':
	case '-':{while ((pro=comp(2))==0) 
			    if (compu()==-1) {printf("  \nERROR INPUT");exit(0);}
			  if (pro==-1){printf("  \nERROR INPUT");exit(0);}	
			  instr[inp]=ch;
		      push_op(inp);
			  inp++;
			  break;
			 }
	case '*':
	case '/':{while ((pro=comp(3))==0) 
			if (compu()==-1){printf("  \nERROR INPUT");exit(0);}
			  if (pro==-1){printf("  \nERROR INPUT");exit(0);}	
			  instr[inp]=ch;
		      push_op(inp);
			  inp++;
			  break;
			 }
	case '(':{push_op(-1);break;}
	case ')':{while (1)
			 {  if (empty_op()) {printf("  \nERROR INPUT");exit(0);} 
		        popop=pop_op();
				if (popop==-1) break;
				push_op(popop);if (compu()==-1){printf("  \nERROR INPUT");exit(0);}
			 }
		     break;}      
    case '#':{while (1)
			 {  if (empty_op()) {printf("  \nERROR INPUT");exit(0);} 
		        popop=pop_op();
				if (popop==-3) break;
				push_op(popop);if (compu()==-1){printf("  \nERROR INPUT");exit(0);}
			 }		      
			 break;}      
	default :printf("  \nERROR INPUT");exit(0);
	}
    
	argv[1]++;
	if ((argv[1][0]==0)&&(flag)) {flag=0;argv[1]--;argv[1][0]='#';}
  }//while
  
  if ((top_op!=0)||(inp!=postp)) {printf("  \nERROR INPUT");exit(0);}
  
  if (buildbt(&bt,poststr,instr,inp)==-1)  {printf("  \nERROR INPUT");exit(0);};
  
  printpoststr(poststr,postp,instr);
  result=getresult(bt);
  printf("\n 结果为：\n   %f\n",result);
  destroytree(bt);
  return 0;
}

int printpoststr(int *poststr,int postp,char * instr)
{int i;
 printf(" 后序表达式为：\n   ");  
 for(i=0;i<postp;i++)
	 printf("%c",instr[poststr[i]]);
 return 0;
}

float getresult(pnode p)
{float r1,r2;
  if (p==NULL) return 0;
  if (p->NodeClass==1) return (getnum(p->data));
  if (p->NodeClass==0) 
  { if ( (r1=getresult(p->left))==-1) {printf("  \nERROR INPUT");exit(0);}
    if ( (r2=getresult(p->right))==-1){printf("  \nERROR INPUT");exit(0);}
    switch (p->data)
	{ case '+':return(r1+r2);break;
 	case '-':return(r1-r2);break;
	case '*':return(r1*r2);break;
	case '/':return(r1 / r2);break;
	default:{printf("  \nERROR INPUT");exit(0);}
	}
  }
  else {printf("  \nERROR INPUT");exit(0);}
}


int buildbt(pnode * pbt,int * poststr,char * instr,int num)
{ return buildtree(pbt,poststr,0,num,instr,0,num);}

int buildtree(pnode * p,int * poststr,int postl,int postr,char * instr,int inl,int inr)
{   char ch;  int i,ll,rl;
	if (postr-postl<=0) {*p=NULL;return 0;}
	ch=instr[poststr[postr -1]];
    *p=malloc(sizeof(node));	
	(*p)->data=ch;(*p)->left=NULL;(*p)->right=NULL;
	switch (ch)
	{case '1':
	case '2':
	case '3':
	case '4':
	case '5':
	case '6':
	case '7':
	case '8':
	case '9':
	case '0':{(*p)->NodeClass=1;break;}
	case '+':
	case '-':
	case '/':
	case '*': {(*p)->NodeClass=0;break;}
	default :printf("  \nERROR INPUT");return (-1);
	}
    i=poststr[postr -1];//取得根结点在中序序列中的位置
	ll=i-inl;rl=inr-(i+1);
   if (buildtree(&((*p)->left),poststr,postl,postl+ll,instr,inl,inl+ll)==-1){printf("  \nERROR INPUT");return (-1);}
   if (buildtree(&((*p)->right),poststr,postr-rl-1,postr-1,instr,inr-rl,inr)==-1){printf("  \nERROR INPUT");return (-1);}
   return 0;
}