数据结构表达式求值.docx

数据结构表达式求值

#include<iostream>
using namespace std;

#define TRUE 1
#define FALSE 0

#define Stack_Size 20
#define Stack_Float 30
/*建立字符栈*/
typedef struct
{
char elem[Stack_Size];//存储定义
int top;
}Stack_char;
void InitStack(Stack_char*S)//初始化顺序栈
{
S->top=-1;
}
int Push(Stack_char *S,char x)//进栈
{
if(S->top==Stack_Size-1) return (FALSE);
S->top++;
S->elem[S->top]=x;
return (TRUE);
}
int Pop(Stack_char*S,char*x)//出栈
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
int GetTop(Stack_char*S,char*x)// 取栈顶
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
return(TRUE);
}
}
char GetTop(Stack_char S)
{
char x;
GetTop(&S,&x);
return x;
}
//建立数字栈
typedef struct//建立
{
float elem[Stack_Float];
int top;
}Stack_float;

void InitStack(Stack_float*S)//初始化
{
S->top=-1;
}

int Push(Stack_float*S,float e) //进栈
{
if(S->top==Stack_Float-1) return(FALSE);
else
{
S->top++;
S->elem[S->top]=e;
return(TRUE);
}
}
int Pop(Stack_float*S,float*x)//出栈
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
int GetTop(Stack_float*S,float*x)// 取栈顶
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
return(TRUE);
}
}
float GetTop(Stack_float S)
{
float x;
GetTop(&S,&x);
return x;
}
bool In(char ch)//判断字符
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return (TRUE);
else return(FALSE);
}
float GetNumber(char*ch)//转化数码
{
return (*ch-48);
}
float Execute(float a,char op,float b)
{
switch(op)
{
case'+':return(a+b);break;
case'-':return(a-b);break;
case'*':return(a*b);break;
case'/':return(a/b);break;
default:cout<<"不能运算";break;
}
}

char Compare(char x,char ch)
{
if(x=='+'||x=='-')
if(ch=='+'||ch=='-'||ch==')'||ch=='#') return ('>');
else return ('<');
if(x=='*'||x=='/')
if(ch=='(') return('<');
else return('>');
if(x=='(')
if(ch==')') return('=');
else return('<');
if(x==')')
if(ch!='(') return('>');
if(x=='#')
if(ch=='#') return('=');
else return('<');
}
float ExpEvaluation()
{
float n,v,a,b;char op;
Stack_char OPTR;
Stack_float OVS;
InitStack(&OPTR);
InitStack(&OVS);
Push(&OPTR,'#');
cout<<"请输入一个表达式串（以#结束）"<<endl;
char ch;
ch=getchar();
while(ch!='#'||GetTop(OPTR)!='#')
{
if(!In(ch))
{
n=GetNumber(&ch);
Push(&OVS,n);
ch=getchar();
}
else

switch(Compare(GetTop(OPTR),ch))
{
case'<':
Push(&OPTR,ch);
ch=getchar();
break;
case'>':
Pop(&OPTR,&op);
Pop(&OVS,&b);
Pop(&OVS,&a);
v=Execute(a,op,b);
Push(&OVS,v);
break;
case'=':
Pop(&OPTR,&op);
ch=getchar();
break;
}
}
v=GetTop(OVS);
return(v);
}

int main()
{
cout<<ExpEvaluation()<<endl;

system("pause");
return 0;
}

完善版
#include<iostream>
using namespace std;

#define TRUE 1
#define FALSE 0

#define Stack_Size 20
#define Stack_Float 30
/*建立字符栈*/
typedef struct
{
char elem[Stack_Size];//存储定义
int top;
}Stack_char;
void InitStack(Stack_char*S)//初始化顺序栈
{
S->top=-1;
}
int Push(Stack_char *S,char x)//进栈
{
if(S->top==Stack_Size-1) return (FALSE);
S->top++;
S->elem[S->top]=x;
return (TRUE);
}
int Pop(Stack_char*S,char*x)//出栈
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
int GetTop(Stack_char*S,char*x)// 取栈顶
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
return(TRUE);
}
}
char GetTop(Stack_char S)
{
char x;
GetTop(&S,&x);
return x;
}
void ClearStack(Stack_char*S)//清空栈
{
if(S->top!=-1) S->top=-1;
}
/*建立数字栈*/

typedef struct//建立
{
float elem[Stack_Float];
int top;
}Stack_float;

void InitStack(Stack_float*S)//初始化
{
S->top=-1;
}

int Push(Stack_float*S,float e) //进栈
{
if(S->top==Stack_Float-1) return(FALSE);
else
{
S->top++;
S->elem[S->top]=e;
return(TRUE);
}
}
int Pop(Stack_float*S,float*x)//出栈
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
S->top--;
return(TRUE);
}
}
int GetTop(Stack_float*S,float*x)// 取栈顶
{
if(S->top==-1) return(FALSE);
else
{
*x=S->elem[S->top];
return(TRUE);
}
}
float GetTop(Stack_float S)
{
float x;
GetTop(&S,&x);
return x;
}
void ClearStack(Stack_float*S)//清空栈
{
if(S->top!=-1) S->top=-1;
}
/*一些函数*/
char a[7]={ '+','-','*','/','(',')', '#'};
char p[7][7]= //优先权集合
{ {'>','>','<','<','<','>','>'},
{'>','>','<','<','<','>','>'},
{'>','>','>','>','<','>','>'},
{'>','>','>','>','<','>','>'},
{'<','<','<','<','<','=','@'},
{'>','>','>','>','@','>','>'},
{'<','<','<','<','<','@','='} };

bool Ins(char ch)//判断数字
{
if(ch>=48&&ch<=57) return(TRUE);
else return(FALSE);
}
bool Inc(char ch)//判断字符
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')
return (TRUE);
else return(FALSE);
}
float GetNumber(char*ch)//转化数码
{
return (*ch-48);
}
float Execute(float a,char op,float b)
{
switch(op)
{
case'+':return(a+b);break;
case'-':return(a-b);break;
case'*':return(a*b);break;
case'/':return(a/b);break;
default:cout<<"不能运算";break;
}
}
char Compare(char x,char ch)
{
//char x;
// GetTop(&S,&x);
int i,j,k;
for(i=0;i<7;i++)
{
if(x==a[i]) j=i;
if(ch==a[i]) k=i;
}
return p[j][k];
}
Stack_char OPTR;
Stack_float OVS;
//InitStack(&OPTR);
//InitStack(&OVS);
void ExpEvaluation()
{
InitStack(&OPTR);
InitStack(&OVS);
Push(&OPTR,'#');
cout<<"请输入一个表达式串（以#结束）"<<endl;
char ch;
int w=0,q=0,y=0,z=0,m=0;float n=0,v,a,b;char op;
ch=getchar();
if(!Ins(ch))
{
if(ch=='(') z=1;
else if(ch=='-') {w=1;ch=getchar();}//记录输入负号
else
{
cout<<"输入错误，请重新a";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ExpEvaluation();
exit(1);
}
}
//else {}
while(ch!='#'||GetTop(OPTR)!='#')
{
if(Ins(ch))
{
n=n*10+GetNumber(&ch);
q=1;//记录输入数字
y=0;//记录输入字符
ch=getchar();
}
//cout<<"n值"<<n<<endl;
//system("pause");
if(Inc(ch))
{
if(ch=='(') z=1;
if(w==1)
{
// cout<<"z"<<z<<endl;
if(q==0)
{

if(z==1)
{
Push(&OPTR,ch);
//cout<<"+++"<<GetTop(OPTR)<<endl;
z=0;
m=2;//记录负的左括号
ch=getchar();
continue;
}
else if(ch=='-') {w=0;ch=getchar();}
else{
cout<<"输入错误，请重新b";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ExpEvaluation();
exit(1); }
}
else
{cout<<"w"<<w<<endl;n=-n;w=0;
if(m==2){n=-n;m--;cout<<"m"<<m<<endl;} }
}
//else {}
if(q==1)
{
Push(&OVS,n);
cout<<"栈顶"<<GetTop(OVS)<<endl;
n=0;
q=0;
}
if(y==1)
{
if(GetTop(OPTR)=='('&&ch=='-')
{w=1;ch=getchar();}
else if(ch=='(') z=1;//记录左括号
else
{
//cout<<"c"<<ch<<endl;
cout<<"输入错误，请重新c";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ClearStack(&OVS);
ExpEvaluation();
exit(1);
}
}
if(y==0||z==1)
{
//cout<<"d"<<ch<<endl;
//cout<<"o栈顶"<<GetTop(OPTR)<<endl;
//cout<<"***"<<Compare(GetTop(OPTR),ch)<<endl;
switch(Compare(GetTop(OPTR),ch))
{
case'<':
Push(&OPTR,ch);
y=1;z=0;
ch=getchar();
//cout<<"e"<<GetTop(OPTR)<<endl;
break;
case'>':
Pop(&OPTR,&op);
Pop(&OVS,&b);
Pop(&OVS,&a);
if(op=='/'&&b==0)
{
cout<<"输入错误，请重新d";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ClearStack(&OVS);
ExpEvaluation();
exit(1);
}
v=Execute(a,op,b);
if(m==1){v=-v;m=0;}
Push(&OVS,v);
//cout<<"*栈顶"<<GetTop(OVS)<<endl;
break;
case'=':
Pop(&OPTR,&op);
ch=getchar();
break;
case'@':
cout<<"括号不匹配，请重新e";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ClearStack(&OVS);
ExpEvaluation();
exit(1);
}
}
}
if(!Inc(ch)&&!Ins(ch))
{
cout<<"输入错误，请重新f";
fflush(stdin); //清理缓存
ClearStack(&OPTR);
ClearStack(&OVS);
ExpEvaluation();
exit(1);
}
}
v=GetTop(OVS);
cout<<v<<endl;
system("pause");
}

int main()
{
ExpEvaluation();
return 0;
}
对我有帮助