jisuan.cpp

算术表达式求值源代码

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>
#include<string.h>
#include<math.h>
#define stack_size_normal 100   //栈的初始化容量
#define stackincrement  10    //栈的容量递增量

//运算符的堆栈,元素类型为字符型
typedef struct lnode_optr{
	char *base;
	char *top;
	int stacksize;
}sqstack_optr;
//运算符的堆栈,元素类型为字符型
typedef struct lnode_opnd{
	int *base;
	int *top;
	int stacksize;
}sqstack_opnd;

//对运算符栈的操作；
sqstack_optr creatstack_optr()   //构造运算符栈
{
	sqstack_optr s;
    s.base=(char*)malloc(stack_size_normal*sizeof(char));  //直接指明了栈中的元素类型;
	if(!s.base) exit(0);
	s.top=s.base;
	s.stacksize=stack_size_normal;
	return s;
}
void push_optr(sqstack_optr &s,char e) //运算符压栈;
{
	if(s.top-s.base>=s.stacksize)
	{
    s.base=(char*)realloc(s.base,(stack_size_normal+stackincrement)*sizeof(char));
      if(!s.base) exit(0);
	  s.top=s.base+s.stacksize;
	  s.stacksize+=stackincrement;
	}
	*s.top++=e;
}
void pop_optr(sqstack_optr &s,char &e)  //运算符出栈;
{
	if(s.top==s.base) exit(0);
	e=*--s.top;
}
void gettop_optr(sqstack_optr &s,char &e) //取栈顶的运算符;
{
	if(s.top==s.base) exit(0);
	e=*(s.top-1);
}
//对数字栈的操作；
lnode_opnd creatstack_opnd()   //构造运算数栈;
{
	lnode_opnd s;
    s.base=(int *)malloc(stack_size_normal*sizeof(int));
	if(!s.base) exit(0);
	s.top=s.base;
	s.stacksize=stack_size_normal;
	return s;
}

void push_opnd(lnode_opnd &s,int n)//运算数压栈;
{
	if(s.top-s.base>=s.stacksize)
	{
    s.base=(int*)realloc(s.base,(stack_size_normal+stackincrement)*sizeof(int));
      if(!s.base) exit(0);
	  s.top=s.base+s.stacksize;
	  s.stacksize+=stackincrement;
	}
	*s.top++=n;
}

void pop_opnd(lnode_opnd &s,int &n)   //运算数出栈;
{
	if(s.top==s.base) exit(0);
	n=*--s.top;
}
void gettop_opnd(lnode_opnd &s,int &n)  //取栈顶的运算数;
{
	if(s.top==s.base) exit(0);
	n=*(s.top-1);
}

//运算符的优先级判别函数,列为读进的运算符,行为栈顶的运算符;
char youxianji(char lie,char hang)
{
	int    i,j;
	char bijiao[9][9]={' ','+','-','*','/','(',')','#','^',
		               '+','>','>','<','<','<','>','>','<',
                       '-','>','>','<','<','<','>','>','<',	                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                       '*','>','>','>','>','<','>','>','<',
					   '/','>','>','>','>','<','>','>','<',
					   '(','<','<','<','<','<','=',' ',' ',
					   ')','>','>','>','>',' ','>','>',' ',
					   '^','>','>','>','>',' ',' ','>',' ',
					   '#','<','<','<','<','<',' ','=','<'};
for(i=0;i<8;i++)
   if(bijiao[0][i]==lie)
	   break;
for(j=0;j<8;j++)
   if(bijiao[j][0]==hang)
	   break;
   return bijiao[j][i];  //返回优先级的表标识;
}
//根据弹出的运算符作相应的运算操作,并返回运算结果;
int  operate(int a,char theta,int b)
{
	int result;
	switch(theta)  //识别运算符;
	{
	case '+':result=b+a;break;
    case '-':result=b-a;break;
    case '*':result=b*a;break;
	case '/':result=b/a;break;
	case '^':result=int(pow(b,a));break; cout<<result<<endl;
	}
   return result;	
}
//对用户输入的算术表达式进行合理的读取,并作相应的操作;
int qiuzhi(char s[])
{ 
	char ch='#',e,kuohao,theta;
	int number=0,a,b,result,g[5],i=0,j,exp=0,loop=1;   
    sqstack_optr  optr;
    sqstack_opnd  opnd; 
    optr=creatstack_optr();     //构造运算符栈;
	opnd=creatstack_opnd();     //构造运算数栈;
	push_optr(optr,'#');
	//循环识别表达式;
    while(*s!=NULL)
	{   
		
		number=int(*s)-48;   //对字符的处理;
		if(number>=0&&number<=9){   //读进的是运算数时;
			while(int(*s)>=48&&int(*s)<58){  //这段程序可以读出多位的整数;
				g[i]=int(*s)-48;
				i++;
				s++;
			}
			if(i>1){ //算出1-5位整数的值
			number=0;
	        for(j=i-1;j>=0;j--){
			   number=number+int(g[j]*pow(10,exp));   //根据数组的相关信息
			    exp=exp+1;
			}
		   }
		  push_opnd(opnd,number);   //把最后的准确的整数值压进运算数栈;
		  i=exp=0;  //初始化整数的累加变量;
		}
       if(int(*s)<48||int(*s)>57) //读进的是运算符;
		{  
			ch=*s;
			gettop_optr(optr,e);
			switch(youxianji(ch,e))  //跟栈顶的运算符作优先级比较;
			{
			case '<':push_optr(optr,*s);break;   //栈顶的优先级低则读进的运算符压栈;
            case '=':pop_optr(optr,kuohao);break; //这里消掉一对括号或者"#"号;
			case '>':pop_optr(optr,theta);  //栈顶的优先级高则弹出来作相应的运算;
				     pop_opnd(opnd,a);
					 pop_opnd(opnd,b);
                     push_opnd(opnd,operate(a,theta,b));
				     if(*s!='#'&&*s!=')')    push_optr(optr,*s);  //处理不同的读进运算符;
					 else s=s-1;
					 break;
			}

		}
		s++;   //读下一个表达式字符;
	
	}
	gettop_opnd(opnd,result); //弹出最后运算数栈的栈顶元素,它就是运算的最后结果;
	return result;
}
void main()
{
  char str[60],*pstr; 
  int result,loop=20,choice;
  while(loop)
  {
   pstr=str;
   cout<<"请输入你要求值的表达式"<<endl;
   cin>>str;
   //对输入的表达式进行处理
   for(;*pstr!=NULL;pstr++) ;
   *pstr++='#';
   *pstr='\0';
   
   result=qiuzhi(str);
   cout<<"表达式的运算结果为："<<endl<<"  "<< str<<"\b="<<result<<endl;
   cout<<"是否继续进行运算？是按1/ 否按0:";
   cin>>choice;
   if(choice==0)
	   exit(0);
   loop--;
  }
}