2313.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;
char youxianji(char lie,char hang)
{
	int    i,j;
	char bijiao[8][8]={' ','+','-','*','/','(',')','#',
		               '+','>','>','<','<','<','>','>',
                       '-','>','>','<','<','<','>','>',	                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                       '*','>','>','>','>','<','>','>',
					   '/','>','>','>','>','<','>','>',
					   '(','<','<','<','<','<','=',' ',
					   ')','>','>','>','>',' ','>','>',
					   '#','<','<','<','<','<',' ','=',};
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];
}
//对操作符栈的操作；
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);
}


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;
	}
   return result;	
}

int qiuzhi(char s[])
{
	char ch='#',e,kuohao,theta;
	int number=0,a,b,result,g[5],i=0,j,exp=0;
    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)		
		   push_opnd(opnd,number);
           
	  else
		{  
			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];
   int result;
   cout<<"请输入你要求值的表达式，并用#号结束。"<<endl;
   cin>>str;
   result=qiuzhi(str);
   
   cout<<"该表达式的值为："<<result<<endl;
}