intbiaodashi.cpp

用链栈实现的算法表达式 可以计算几位数字的算法。

#include<cstdio> 
#include<malloc.h> 
#define NULL 0 
typedef struct node{ 
int date; 
struct node *next; 
}SNode; 

SNode *InitStack()//初始化
{ 
   SNode *top; 
   top=(SNode *)malloc(sizeof(SNode)); 
   top->next=NULL; 
   return top; 
} 
void PushOptr(SNode *top,int x)//往栈中输入数据（运算符）
{ 
   SNode *p; 
   p=(SNode *)malloc(sizeof(SNode)); 
   p->date=x; 
   p->next=top->next; 
   top->next=p; 

} 
int PopOptr(SNode *top)//删除结点并返回该结点的值（运算符）
{ 
   SNode *p; 
   int x; 
   if(top==NULL) 
   return NULL; 
   p=top->next; 
   x=p->date; 
   top->next=p->next; 
   free(p); 
   return x; 
} 
void PushOpnd(SNode *top,int x)//插入值x的结点（运算数）
{ 
   SNode *p; 
   p=(SNode *)malloc(sizeof(SNode)); 
   p->date=x; 
   p->next=top->next; 
   top->next=p;  
} 
int PopOpnd(SNode *top)//删除结点（运算数）
{ 
   SNode *p; 
   int x; 
   if(top==NULL) 
   return NULL; 
   p=top->next; 
   x=p->date; 
   top->next=p->next; 
   free(p); 
   return x; 
} 
int GetTop(SNode *top)//求结点的值
{ 

   return (top->next)->date; 
} 
int ch(int c)
{
	if(c>=0&&c<=9)
		return 1;
	else 
		return 0;
}
int In(int c)//判断输入是否为符号或是返回1其它返回0
{ 
	int n; 
   switch(c)
     { 
   	case '+': 
   	case '-': 
   	case '*': 
   	case '/': 
   	case '(': 
   	case ')': 
  	case '#':n=1;break; 
  	default:n=0;break; 
     } 
   return n; 
} 
char Precede(int x,int y)
{ 
int i,j; 
int form[7][7]={{1,1,-1,-1,-1,1,1},
				{1,1,-1,-1,-1,1,1},
				{1,1, 1, 1,-1,1,1},
				{1,1, 1, 1,-1,1,1},
				{-1,-1,-1,-1,-1,0,2},
				{1,1,1,1,2, 1,  1 },
				{-1,-1,-1,-1,-1,2,0}
				}; 
  switch(x)
   { 
	case '+':i=0;break; 
	case '-':i=1;break; 
	case '*':i=2;break; 
	case '/':i=3;break; 
	case '(':i=4;break; 
	case ')':i=5;break; 
	case '#':i=6;break; 
    } 
  switch(y)
  { 
	case '+':j=0;break; 
	case '-':j=1;break; 
	case '*':j=2;break; 
	case '/':j=3;break; 
	case '(':j=4;break; 
	case ')':j=5;break; 
	case '#':j=6;break; 
   } 
    if(form[i][j]==1) 
	return '>'; 
    else 
	if(form[i][j]==-1) 
	return '<'; 
	else 
	return '='; 

} 
int Operate(int x,int z,int y)
{ 
int a=x,b=y; 
switch(z){ 
    case '+':return a+b; 
    case '-':return a-b; 
    case '*':return a*b; 
    case '/':return a/b; 
  } 
} 
int Eval_Exp()
{ 
  int a,b,c,r,f,z; 
  int result=0; 
  SNode *top[2];
  top[0]=InitStack(); 
  PushOptr(top[0],'#'); 
  top[1]=InitStack(); 
  c=getchar(); 
  while(c!='#'||(GetTop(top[0]))!='#')
  { 
		if(!In(c))//操作数入栈
		{ 
			PushOpnd(top[1],c-'0'); 
			c=getchar();
			while(!In(c))
			{   
			
				PushOpnd(top[1], PopOpnd(top[1])*10+c-'0');
				c=getchar();
			}
		 } 
		 else  //操作符比较
		 { 
				 r=Precede(GetTop(top[0]),c); 
				 switch(r)
				 { 
					case '<':
						PushOptr(top[0],c); //操作符入栈
						c=getchar(); 
						break; 
					case '=':
						PopOptr(top[0]); //删除操作符
						c=getchar(); 
						break; 
					case '>':
						b=PopOptr(top[0]); //弹出两个操作数和操作符
						a=PopOpnd(top[1]); 
						z=PopOpnd(top[1]); 
						result=Operate(z,b,a); 
						f=result; 
						PushOpnd(top[1],f); 
						break; 
				} 
			} 
	} 
	return f;
} 
void main()
{ 
	int result; 
	result=Eval_Exp(); 
	printf("%d\n",result); 
}