问题描述

数据结构-表达式求值，为什么只能求类似于3*（5-2）的一位数表达式？求大神指点

#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -1
using namespace std;
typedef struct
{
int base;
int *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
{
S.base=(int *)malloc(STACK_INIT_SIZE * sizeof(int));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int ClearStack(SqStack &S)
{
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int GetTop(SqStack S,int &e)
{
if(S.base==S.top)
return ERROR;
e=(S.top-1);
return OK;
}
int Push(SqStack &S,int e)
{
if((S.top-S.base)>=S.stacksize)
{
S.base=(int )realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base)
exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top=e;
S.top++;
return OK;
}
int Pop(SqStack &S,int &e)
{
if(S.top==S.base) return ERROR;
S.top--;
e=*S.top;
return OK;
}
int Pop2(SqStack &S,char &e)
{
if(S.top==S.base) return ERROR;
S.top--;
e=*S.top;
return OK;
}
bool StackEmpty(SqStack S)
{
if(S.top==S.base)
return true;
else
return false;
}
int StackLength(SqStack S)
{
int len=0;
if(S.top==S.base)
return 0;
else
while(S.top!=S.base)
{
S.top--;
len++;
}
return len;
}
//数制转换:输入任意一个非负十进制整数，打印输出与其等值的进制数
void conversion(SqStack S)
{
int N,id,n;
cout<<"请输入任意一个非负十进制整数：";
cin>>N;
cout<<"请输入需要转换的进制 ：";
cin>>id;
n=N;
while(N)
{
Push(S,N%id);
N=N/id;
}
cout<<"此时栈的长度为"<
cout
while(S.top!=S.base)
{
S.top--;
cout
}
cout
cout
}
//括号匹配的检验
int match(SqStack S)
{
char a[100],b[100];
cout
cin>>a;
for(int i=0;i
{
cout
if((a[i]!='[') && (a[i]!=']') && (a[i]!='(') && (a[i]!=')'))
{
cout
return 0;
}
else
{
if((a[i]=='[')||(a[i]=='('))
{
Push(S,a[i]);
cout
}
else if(a[i]==']')
{
if(S.top==S.base)
{
cout
return 0;
}
else
{
S.top--;
if(*S.top=='[')
{
b[i]=*S.top;
cout
cout
}
else
{
cout
return 0;
}
}
}
else
{
if(a[i]==')')
{
if(S.top==S.base)
{
cout
return 0;
}
else
{
S.top--;
if(*S.top=='(')
{
b[i]=*S.top;
cout
cout
}
else
{
cout
return 0;
}
}
}
}
}
}
cout
return 1;
}
//行编辑程序
void LineEdit(SqStack S)
{
char a[100],b[100];
int *base=S.base;
cout
cin>>a;
for(int i=0;i
{
while(a[i]!=EOF && a[i]!='
')
{
if(a[i]=='#') //'#'表示前一个字符无效
{
Pop2(S,b[i-1]);
cout
break;
}
else if(a[i]=='@') //'@'表示当前行中的字符均无效
{
ClearStack(S);
break;
}
else
{
Push(S,a[i]);
break;
}
}
}
while(base!=S.top)
{
cout
base++;
}
cout
}
int Precede(char a,char b) //1代表'>';0代表'=';-1代表'<'
{
int st;
if(a=='+')
{
switch(b)
{
case '+': st=1;
break;
case '-': st=1;
break;
case '': st=-1;
break;
case '/': st=-1;
break;
case '(': st=-1;
break;
case ')': st=1;
break;
case '#': st=1;
break;
}
}
else if(a=='-')
{
switch(b)
{
case '+': st=1;
break;
case '-': st=1;
break;
case '*': st=-1;
break;
case '/': st=-1;
break;
case '(': st=-1;
break;
case ')': st=1;
break;
case '#': st=1;
break;
}
}
else if(a=='*')
{
switch(b)
{
case '+': st=1;
break;
case '-': st=1;
break;
case '*': st=1;
break;
case '/': st=1;
break;
case '(': st=-1;
break;
case ')': st=1;
break;
case '#': st=1;
break;
}
}
else if(a=='/')
{
switch(b)
{
case '+': st=1;
break;
case '-': st=1;
break;
case '*': st=1;
break;
case '/': st=1;
break;
case '(': st=-1;
break;
case ')': st=1;
break;
case '#': st=1;
break;
}
}
else if(a=='(')
{
switch(b)
{
case '+': st=-1;
break;
case '-': st=-1;
break;
case '*': st=-1;
break;
case '/': st=-1;
break;
case '(': st=-1;
break;
case ')': st=0;
break;
case '#': break;
}
}
else if(a==')')
{
switch(b)
{
case '+': st=1;
break;
case '-': st=1;
break;
case '*': st=1;
break;
case '/': st=1;
break;
case '(': break;
case ')': st=1;
break;
case '#': st=1;
break;
}
}
else if(a=='#')
{
switch(b)
{
case '+': st=-1;
break;
case '-': st=-1;
break;
case '*': st=-1;
break;
case '/': st=-1;
break;
case '(': st=-1;
break;
case ')': break;
case '#': st=0;
break;
}
}
return st;
}
int Operate(int a,char theta,int b)
{
int result;
switch(theta)
{
case'+': result=a+b;
break;
case'-': result=a-b;
break;
case'*': result=a*b;
break;
case'/': result=a/b;
break;
}
return result;
}
int EvaluteExpression()
{
SqStack OPTR,OPND;
char x,theta;
char arr[100],dr[]={'#'};
int j=0,e,n,a,b,result;
int y;
int optrT,*optrB,*opndT,*opndB;
InitStack(OPTR);
Push(OPTR,'#'); //以int值进栈，出栈需转换
InitStack(OPND);
//cout<<"请输入算术表达式："; //算术表达式以'#'结束
//cin>>arr;
cout<<"请输入：";
cin>>y
for(int i=0;i<strlen(arr);i++)
{
GetTop(OPTR,e);
cout<<"***************************"<<endl;
cout<<"i="<<i<<endl;
cout<<"输入字符"<<arr[i]<<endl;
cout<<"char(e)="<<char(e)<<endl;
if(arr[i]!='#' || char(e)!='#')
{
if(arr[i]!='+' && arr[i]!='-' && arr[i]!='*' && arr[i]!='/' && arr[i]!='(' && arr[i]!=')' && arr[i]!='#') //操作数
{
Push(OPND,arr[i]-'0');
opndT=OPND.top;
opndB=OPND.base;
cout<<"操作数栈中元素：";
while(opndT!=opndB)
{
opndT--;
cout<<*opndT<<" ";
}
cout<<endl;
}
else
{
GetTop(OPTR,e);
cout<<"e="<<char(e)<<endl;
n=Precede(char(e),arr[i]);
cout<<"n="<<n<<endl;
switch(n)
{
case -1: Push(OPTR,arr[i]);
optrT=OPTR.top;
optrB=OPTR.base;
cout<<"运算符栈中元素：";
while(optrT!=optrB)
{
optrT--;
cout<<char(*optrT)<<" ";
}
cout<<endl;
break;
case 0: Pop2(OPTR,x);
opndT=OPND.top;
opndB=OPND.base;
cout<<"操作数栈中元素：";
while(opndT!=opndB)
{
opndT--;
cout<<*opndT<<" ";
}
cout<<endl;
optrT=OPTR.top;
optrB=OPTR.base;
cout<<"运算符栈中元素：";
while(optrT!=optrB)
{
optrT--;
cout<<char(*optrT)<<" ";
}
cout<<endl;
break;
case 1: Pop2(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,theta,b));
i--;
opndT=OPND.top;
opndB=OPND.base;
cout<<"操作数栈中元素：";
while(opndT!=opndB)
{
opndT--;
cout<<*opndT<<" ";
}
cout<<endl;
optrT=OPTR.top;
optrB=OPTR.base;
cout<<"运算符栈中元素：";
while(optrT!=optrB)
{
optrT--;
cout<<char(*optrT)<<" ";
}
cout<<endl;
break;
}
}
}
}
GetTop(OPND,result);
cout<<arr<<"="<<result<<endl;
return OK;
}
int main()
{
/*SqStack S;
InitStack(S);
conversion(S);
match(S);
LineEdit(S);*/
EvaluteExpression();
return OK;
}

解决方案

你代码错误太多，参考这个
http://blog.163.com/the_show_27@yeah/blog/static/107887293201032274128788/

人家就几十行代码，却能做比你多几倍的事情。

解决方案二：

表达式求值：2*(3*(5+2))