suanshubiaodashi.cpp

关于栈中算术表达式求法 别人写的

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXNUM 100

char top(char a[])
{
  int i;
  char b;
   for(i=0;a[i]!='\0';i++);
        
   b=a[i-1];
   return b;
}


int power(char x,int &base)//  base用来保证括号内运算权限比括号外高
{
	int power;
    if(x=='+'||x=='-')
		power=base+1;
	if(x=='*'||x=='/')
		power=base+2;
    if(x=='(')
	{
		power=3;
		base+=3;
	}
	if(x==')')
	{
		power=-1;
	
	}
	if('0'<=x&&x<='9')
		power=0;
	return power;
}
int pop1(int a[])// 先返回栈顶值再出栈
{
   int i,b;
   for(i=0;a[i];i++);//!='\0'
       
   b=a[i-1];
   a[i-1]='\0'; 
   return b;
}
char pop2(char a[])// 先返回栈顶值再出栈
{
   int i;
   char b;
   for(i=0;a[i]!='\0';i++);
        
   b=a[i-1];
   a[i-1]='\0'; 
   return b;
}
int math(int x,char y,int z)//运算xyz,y是运算符
{
	if (y=='+')
		x=x+z;
	if (y=='-')
		x=x-z;
	if (y=='*')
		x=x*z;
	if (y=='/')
		x=x/z;
	return x;
}

void push1(int a[],int b)//入栈
{
   int i;
   for(i=0;a[i];i++);//!='\0'
     
   a[i]=b;
   a[i+1]='\0';      
}
void push2(char a[],char b)//入栈
{
   int i;
   for(i=0;a[i]!='\0';i++);
        
   a[i]=b;
   a[i+1]='\0';      
}


void infixtoSuffix(const char * infix) //
{ 
   int i,b,c,base=0,opnd[MAXNUM],m,a;
   char y,x,optr[MAXNUM];
   opnd[0]='\0';
   optr[0]='\0';
  for (i = 0; infix[i] != '\0'; i++)
  {
	x=infix[i];
    if (power(x,base)==0)//数字就入栈
	{
        if (i>0&&power(infix[i-1],base)==0)
		{
			b=pop1(opnd);
			a=10*b+int(x-'0');
		}
		else
            a=int(x-'0');//
        push1(opnd,a);
//**********************
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
         printf("%-15s%-10c%d入OPND栈\n", optr, x, a);
//**********************
	}
    else if (power(x,base)==-1)//')',运算消除一对()
	{    
    	

        a=pop1(opnd);
     	b=pop1(opnd);
    	y=pop2(optr);
    	c=math(b,y,a);
    	push1(opnd,c);  
		////////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
		printf("%-15s%-10c计算%d%c%d并将结果%d压入OPND栈\n", optr, x,b, y,a,c);
 //       printf("主要操作 :  计算%d%c%d并将结果%d压入OPND栈\n\n", b,y,a,c);
		//////////////////////////////////


		y=pop2(optr);
		///////////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
         printf("%-15s          %c出OPTR栈\n", optr, y);
  		/////////////////////////////////


    	if(y=='(')	;  //考虑如3+5*(3+5*6)
    	else
		{ 
     	
			while(y!='(')
			{
			a=pop1(opnd);
        	b=pop1(opnd);
    		c=math(b,y,a);
        	push1(opnd,c);
			//////////////////////////
            for(m=0;opnd[m];m++)
	        	printf("%d ", opnd[m]);
	    	m=10-m;
	    	for(m;m!=0;m--)
     		    printf("  ");
    		printf("%-15s          计算%d%c%d并将结果%d压入OPND栈\n", optr, b, y,a,c);
		///////////////////////////////////

	    	y= pop2(optr);
			}
			////////////////////////////////
            for(m=0;opnd[m];m++)
    	    	printf("%d ", opnd[m]);
    		m=10-m;
     		for(m;m!=0;m--)
    		    printf("  ");
            printf("%-15s          %c出OPTR栈\n", optr, y);
		//////////////////////////////////  
		}
		base-=3;
	}
    else if (power(x,base)==3)
	{
		push2(optr,x);
		///////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
         printf("%-15s%-10c%c入OPTR栈\n", optr, x, x);

    }
	else
	{
    	if(power(x,base)>power(top(optr),base))
		{push2(optr,x);
		///////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
         printf("%-15s%-10c%c入OPTR栈\n", optr, x, x);
		///////////////////////////
		}
    	else 
		{
            a=pop1(opnd);

        	b=pop1(opnd);

        	y=pop2(optr);

	    	c=math(b,y,a);

    		push1(opnd,c);
			/////////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(m;m!=0;m--)
		    printf("  ");
		printf("%-15s%-10c计算%d%c%d并将结果%d压入OPND栈\n", optr, x ,b, y,a,c);
		///////////////////////////////////
    	push2(optr,x);
			/////////////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(;m!=0;m--)
		    printf("  ");
         printf("%-15s%-10c%c入OPTR栈\n", optr, x, x);
		///////////////////////////////
		}
	}
  }
  y=pop2(optr);
 
  while(opnd[1]!='\0')
  {
      a=pop1(opnd);

      b=pop1(opnd);

      c=math(b,y,a);

	  push1(opnd,c);
	  //////////////////////////////////
        for(m=0;opnd[m];m++)
	    	printf("%d ", opnd[m]);
		m=10-m;
		for(;m!=0;m--)
		    printf("  ");
		printf("%-15s          计算%d%c%d并将结果%d压入OPND栈\n", optr, b, y,a,c);
		//////////////////////////////
      y=pop2(optr);
  }
printf("算术表达式计算结果为：%d\n",opnd[0]);

} 


void getline(char * line, int limit) 
{ 
       char c;
       int i = 0;
       while (i < limit - 1 && (c = getchar()) != EOF && c != '\n')
              line[i++] = c;
       line[i] = '\0';
} 

void main() 
{ 
	char infix[MAXNUM] ;
        printf("                 ***********************************\n");
		printf("                 *        算术表达式求值演示       *\n");
		printf("                 *   ---------------------------   *\n");
        printf("                 * 制 作 人         starrysky      *\n");
		printf("                 * 个人信息         见论坛简介     *\n");
        printf("                 * QQ               297456458      *\n");
		printf("                 * ————————————————*\n");
		printf("                 ***********************************\n");
		printf("\n\n说明：\n如下表达式非法：\n   数字和'('直接连接在一起，如 1+2(1+1)\n   请输入一个表达式,如3*(7-2)。\n\n请输入表达式 :");
        getline(infix, MAXNUM); 
		printf("\n");
		printf("OPND栈               OPTR栈        输入字符    主要操作\n");
        infixtoSuffix(infix);
		printf("按回车结束。");
		getchar();
  
}