数据结构表达式求值.docx

数据结构表达式求值

#include
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<<"请输入一个表达式串（以#结束）"<
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<
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)//进栈
{
ifS->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<<"请输入一个表达式串（以#结束）"<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值"< if(ch=='(') z=1;
if(w==1)
{
// cout<<"z"<<lush(stdin); //清理缓存
ClearStack(&OPTR);
ExpEvaluation();
exit(1); }
}
else
{cout<<"w"< //else {}
if(q==1)
{
Push(&OVS,n);
cout<<"栈顶"<getchar();}
else if(ch=='(') z=1;//记录左括号
else
{
//cout<<"c"< ExpEvaluation();
exit(1);
}
}
if(y==0||z==1)
{
//cout<<"d"<
switch(Compare(GetTop(OPTR),ch))
{
case'<':
Push(&OPTR,ch);
y=1;z=0;
ch=getchar();
//cout<<"e"< 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<<"*栈顶"<37、 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<