7.txt

Data Structure Question

用递归方式求解表达式

//用递归方式求解表达式
#include <iostream.h>
#include <math.h>
#define N 200
#define Q 0x3a
//#define Q 0x35
//char a[10]="5((x+x)*x)";
//char a[10]="5((x*x)+x)";
//char a[10]="5(x*x)";
//char a[15]="5(x*((x*x)+x))";
char a[100]="5((((x+x)*(x*x))*((x*x)+(x+x)))+x)";
int az=5;
int sc(char aa[N]);
int t(char s[N]);
main()
{
a[0]=Q;
cout<<t(a);
cin>>az;
}
int t(char s[N])
{
    int lj=0,i,kh=0;
char aa[N],bb[N];
    if(s[1]=='x')return(1);
else
{
    do
{
    lj++;
    if(s[lj]=='(')kh++;
    if(s[lj]==')')kh--;
}while((s[lj]!='+'&&s[lj]!='*')||kh!=1);

aa[0]=a[0];
bb[0]=a[0];
    for(i=2;i<lj;i++)
    aa[i-1]=s[i];
for(i=lj+1;i<=N;i++)
    bb[i-lj]=s[i];
// cout<<"aa="<<aa<<" bb="<<bb<<endl;;
    if(s[lj]=='+')
    return t(aa)+t(bb);
if(s[lj]=='*')
    return t(aa)*sc(bb)+sc(aa)*t(bb);
}
}
int sc(char aa[N])
{
int b[N]={{0}};
char d[N];//B为系数 C为指数栈 D为符号栈
int ks=1,kf=1,kh=1,i=0;//ks系数指针 kf符号指针 kh括号计数

if(aa[1]=='x')return(a[0]-0x30);
    do
{
i++;
switch(aa[i])
{
    case '(':
        kh++;
break;
    case 'x':
    b[ks]=a[0]-0x30;ks++;
break;
    case '+':
    d[kf]='+';kf++;
break;
    case '*':
    d[kf]='*';kf++;
break;
    case ')':
    if(kh!=1)
        {
        kh--;
        kf--;
        if(d[kf]=='+')
{
b[ks-2]=b[ks-2]+b[ks-1];
ks--;b[ks]=0;
}
        if(d[kf]=='*')
{
    b[ks-2]=b[ks-2]*b[ks-1];
ks--;b[ks]=0;
}
        }
}
}while(kh!=1);
// cout<<"sc aa="<<aa<<" "<<b[1]<<endl;
return b[1];
}