qz.c.txt

C语言编写的 任意输入表达式的波兰表示 此程序将计算出结果

	#include<stdlib.h>
	#include<stdio.h>
	#define stack_init_size1 40
	#define stack_init_size2 20
	#define stackincrement1 40
	#define stackincrement2 20
	typedef struct{
	    int *base;
	    int *top;
	    int stacksize;
	}s_stack;
	typedef struct{
	    char *base;
	    char *top;
	    int stacksize;
	}f_stack;
	
	static char Weigh[8][9]=
	    {
	        {'>','>','<','<','<','>','>','<','>'},{'>','>','<','<','<','>','>','<','>'},
	        {'>','>','>','>','<','>','>','>','>'},{'>','>','>','>','<','>','>','>','>'},
	        {'<','<','<','<','<','=','>','<','>'},{'>','>','>','>','>','>','>','>','>'},
	        {'<','<','<','<','<','>','=','<','='},{'>','>','>','>','<','>','>','>','>'},
	        //{'<','<','<','<','<','>','=','<','='} 
	    };
	
	int Seriallize(char c)
	{
	    switch(c)
	    {
	    case '+': return 0;
	    case '-': return 1;
	    case '*': return 2;
	    case '/': return 3;
	    case '(': return 4;
	    case ')': return 5;
	    case '#': return 6;
	    case '^': return 7;
		case '\n': return 8;	
	    default:return 9;
	    }
	
	}
	
	void s_push(s_stack *s,int e)
	{
	
	     if(s->top-s->base>=s->stacksize)
	     {
	         s->base=(int *)realloc(s->base,(s->stacksize+stackincrement1)*sizeof(int));
	         if(!s->base) exit(0);
	         s->top=s->base+s->stacksize;
	         s->stacksize+=stackincrement1;
	     }
	    *s->top=e; s->top++;
	    /*printf("the s_stack has the data:%d\n",*(s->top-1));*/
	}
	void  f_push(f_stack *f,char e)
	{
	     if(f->top-f->base>=f->stacksize)
	     {
	         f->base=(char *)realloc(f->base,(f->stacksize+stackincrement2)*sizeof(char));
	         if(!f->base) exit (0);
	         f->top=f->base+f->stacksize;
	         f->stacksize+=stackincrement2;
	     }
	     *f->top=e;f->top++;
	    /* printf("the f_stack has the sign:%c\n",*(f->top-1));*/
	}
	
	int s_gettop(s_stack *s)
	{
	    s->top--;
	    return *s->top;
	}
	
	char f_gettop(f_stack *f)
	{
	    f->top--;
	    return *f->top;
	}
	bool f_ifempty(f_stack *f)
	{
		if (f->base==f->top)
		{
		  return true;
		}
		else
		{
		  return false;
		}
	}
	
	char EstimateCalculator(f_stack *f,char c)
	{
	    int m,n;
	    char w;
	    m=Seriallize(c);
	    w=*(f->top-1);
	    n=Seriallize(w);
	    return Weigh[n][m];
	}
	int Pow(int p,int q)
	{
		if (q==0)
		{
		   return 1;
		}
		else
		{
			return p*Pow(p,q-1);
		}
	}
	int Operate(int p,char r,int q)
	{
	        switch(r)
	    {
	        case '+': return q+p;
	        case '-': return p-q;
	        case '*': return q*p;
	        case '/': return p/q;
	        case '^': return Pow(p,q);
	    }
	}
	bool Calculate(int &Result)
	{
	    int h=0,iResult;
	
	    int iWrong=0;
		int iNumberOut=0;
	    char cNewChar;
	    s_stack istackNumber;
	    f_stack cstackCalculator;
	
	
	    istackNumber.base=(int*)malloc(stack_init_size1*sizeof(int));
	    if(!istackNumber.base) return 0;
	    istackNumber.top=istackNumber.base;
	    istackNumber.stacksize=stack_init_size1;
	
	    cstackCalculator.base=(char*)malloc(stack_init_size2*sizeof(char));
	    if(!cstackCalculator.base) return 0;
	    cstackCalculator.top=cstackCalculator.base;
	    cstackCalculator.stacksize=stack_init_size2;
	    *cstackCalculator.top='#';cstackCalculator.top++;
	
	    cNewChar=getchar();
		//getchar是一个一个字符读入。
	    //比如12先读入1，再读入2。
		
		
		
		while((!(f_ifempty(&cstackCalculator))||(cNewChar!='\n'))&&(iWrong==0))
	    {//只要运算符号栈不空或者最后一次输入的符号不是回车则运行以下程序. 
		 //换句话说,这段程序结束的条件是所有的运算符用完,
		 //而且当前输入的有时回车.	
			int t;
		    
	        int p,q;
	
	        char r;
	        if(Seriallize(cNewChar)==9)
			//当前读入的不是运算符，而是数。
	        {   
				if(h>0)//第h次读入
				{
	               t=s_gettop(&istackNumber);
				   //取出数栈里最后一个数。
	               s_push(&istackNumber,t*10+cNewChar-48);
				   //把取出的数乘于10加上当前读入字符（减去48）对应的数存回数栈。
				}
	   else s_push(&istackNumber,cNewChar-48);//第一个字符比如12的1。
	            h++;
				cNewChar=getchar();
	
	        }
	        else
			//当前读入的符号是运算符。
	        switch(EstimateCalculator(&cstackCalculator,cNewChar))
	        {
	          case '<'://当前的运算符号的级别高于前一个运算符。
	               f_push(&cstackCalculator,cNewChar);
				   //运算符压入
				   cNewChar=getchar();
				   h=0;
				   break;
	          case '='://当前的运算符号的级别等于前一个运算符。
	               cstackCalculator.top--;
	               cstackCalculator.stacksize--;
				   //前一个运算符退栈。
	               if (cNewChar!='\n')
	               {
	                 cNewChar=getchar();
				   }
	               h=0;
				   break;
	          case '>'://当前的运算符号的级别小于前一个运算符。
	               if (cstackCalculator.top-cstackCalculator.base<1)
	               {
	                 iWrong=1;
					 
				     }
				   else
				   {
					   r=f_gettop(&cstackCalculator);
					   //从运算符栈中取出当前运算所需要的运算符.
				   }
				  
				   
	              
			      if ((istackNumber.top-istackNumber.base)>1)
				  {//从数栈里的数取出当前要进行运算的二个数进行运算.
						   q=s_gettop(&istackNumber);
						   p=s_gettop(&istackNumber);
						   
						   iResult=Operate(p,r,q);
						   s_push(&istackNumber,iResult);
						   
				  }
				  else
				  {//数栈里的数不足两个.
	
						   iWrong=1;
				  }
				  break;
				  
			}//switch
		}
	
		if(iWrong==1)
		{
			return false;
			Result=0;
	    }
		else
		{
			Result=s_gettop(&istackNumber);
			return true;
		}
		free(cstackCalculator);
		free(istackNumber);
	}
	
	
	
	int main()
	{
	    
		char cIfCalculate='y';
		
		while ((cIfCalculate=='y'))
		{
		   printf("please input the expression and end it with enter!\n");
		   int iResult;
	
		   bool blLegalExpression=Calculate(iResult);
		   if (blLegalExpression)
		   {
		      printf("the answer is %d\n",iResult);
		   }
		   else
		   {
			 printf("You have input the incorrect expression!!!\n");
		   }
		   printf("continue to calculate?press y to continue,and any key to break.");
		   cIfCalculate=getchar();
		   fflush(stdin);
		   //刷新标准输入流,否则程序将接着在那里读入我们不需要的字符.
		}
		return 0;
	}