算术表达式求值 设埔桓龀绦颍菔居盟惴畔确ǘ员泶锸角笾档墓獭＃ㄓ谜皇迪郑?nbsp 基本要求： 1、以字符序列的形式从键盘输入语法正确的

#include<iostream.h> 
#include<stdio.h> 
#include<stdlib.h> 
#include<math.h> 
#include<cstring>

#define S_SIZE 100 //存储空间初始分配量 
#define S_ZENG 10 //存储空间分配增量 
#define OK 1 


typedef struct 
{ //定义顺序栈 
int *base; //栈底指针，在构造前和销毁后的值为NULL 
int *top; //栈顶指针 
int ssize; //当前已分配的存储空间，以元素为单位 
}sqstack; //以上为栈的顺序存储表示 




ins(sqstack &s) //构造一个空栈 
{ 
s.base=(int *)malloc(S_SIZE * sizeof(int));//获取栈底 
if(!s.base)exit(-1); //存储分配失败 
s.top=s.base; //因为是空栈，栈顶和栈底指向同一个位子 
s.ssize=S_SIZE; //栈长度 
return OK; //创建完成返回OK 
} 




gettop(sqstack s/*,int &e*/) //取栈顶元素 
{ 
if(s.top==s.base) return -1; //空栈无法返回元素，返回－1 
//e=*(s.top-1); //取得栈顶元素 
return *(s.top-1); 
} 





push(sqstack &s,int e) //入栈，插入e为栈顶元素 
{ 
if(s.top-s.base>=s.ssize) //如果栈满追加存储空间 
{ 
s.base=(int *)realloc(s.base,(s.ssize+S_ZENG)*sizeof(int)); 
if(!s.base)exit(-1); //存储分配失败 
s.top=s.base+s.ssize; //设定栈顶指针 
s.ssize+=S_ZENG; //设定长度 
} 
*s.top++=e; 
return OK; 
} 





pop(sqstack &s,char &e) //出栈，若栈不空，删除栈顶元素，用e返回值 
{ 
if(s.top==s.base)return -1; 
e=*--s.top; 
return OK; 

} 




char precede(char a,char b)
{
int i,j;
char Table[10][10]={' ','+','-','*','/','%','(',')','#','^',
                    '+','>','>','<','<','<','<','>','>','<',
                    '-','>','>','<','<','<','<','>','>','<',
                    '*','>','>','>','>','>','<','>','>','<',
                    '/','>','>','>','>','>','<','>','>','<',
                    '%','>','>','>','>','>','<','>','>','<', 
                    '(','<','<','<','<','<','<','=',' ','<',
                    ')','>','>','>','>','>',' ','>','>','>',
                    '#','<','<','<','<','<','<',' ','=','<',
                    '^','>','>','>','>','>','<','>','>','>',
               };
for(i=0;i<10;i++)
   if(Table[0][i]==b)                                /*锁定纵坐标*/
    break;
for(j=0;j<10;j++)                                    /*锁定横坐标*/
   if(Table[j][0]==a)
    break;
return Table[j][i];
}/*Precede*/




int mod(int &m,int &n)
{int r;  
r=m%n;  
while(r)  
{  
 m=n;n=r;  
 r=m%n;  
}  
return r;  
}





 operate(int a,unsigned char theta, int b)
{ 
switch(theta)
{ 
case '+': return a+b; 
case '-': return a-b; 
case '*': return a*b; 
case '/': return a/b; 
case '^': return (int)pow(a,b); 
case '%': return mod(a,b);
default : return 0; 
} 
}


char op[9]={'+' , '-' , '*' , '/' ,'(' , ')' , '#','^','%'}; 
char *TestOp=&op[9];
int in(char Test,char* TestOp) 
{ 
int Find=0; 
for (int i=0; i< 9; i++) 
{ 
if (Test == TestOp[i]) Find= 1; 
} 
return Find; 
} 






int suansu() //核心算法，算术表达式求值，optr为运算符栈，opnd为运算数栈 
{ 
char c,e,a,b,theta,x; 
sqstack optr,opnd; 
ins(optr);push(optr,'#'); 
ins(opnd);c=getchar(); 
while(c!='#'||gettop(optr)!='#') 
{ 
if(!in(c,op)){push(opnd,c);c=getchar();} 
else 
switch(precede(gettop(optr),c)) 
{ 
case'<': 
push(optr,c);c=getchar(); 
break; 
case'=': 
pop(optr,x);c=getchar(); 
break; 
case'>': 
pop(optr,theta); 
pop(opnd,b);pop(opnd,a); 
push(opnd,operate(a,theta,b)); 
break; 
} 
} 
return gettop(opnd); 
}






void main()
{
int x;
cout<<"***********************************"<<endl;
cout<<"请输入表达式:"<<endl;
x=suansu();
cout<<"结果是:"<<x<<endl;
cout<<"***********************************"<<endl;
}
 
 

/*void main()
{
char ch[80];
int x;
cout<<"***********************************"<<endl;
cout<<"请输入表达式:"<<endl;
cin>>ch;
x=suansu();
cout<<"结果是:"<<x<<endl;
cout<<"***********************************"<<endl;
}*/