问题描述
- 数据结构用栈实现算术表达式的求值运算
-
小白一枚，最近用栈实现算术表达式的求值运算结果出现好多问题，单独的加减乘除运算都能够实现，但一旦加上括号运算就停在那命令窗口也不能输入信息，跪求大神指点原因
附上代码和截图：
#include
#include
#include
#define STACK_INIT_SIZE 100 //存储空间初始分配量;
#define S 10 //存储空间分配增量;
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct{
char base;
char *top;
int stacksize;
}sqstack; //定义运算符类型栈;
typedef struct{
int *base;
int *top;
int stacksize;
}stack; //定义运算数栈;
void InitStack(sqstack &OPTR) //构建运算符栈;
{
OPTR.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
if(!OPTR.base)
printf("Error!
");
OPTR.top=OPTR.base;
OPTR.stacksize=STACK_INIT_SIZE;
return;
}
void Initstack(stack &OPND) //构建运算数栈;
{
OPND.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!OPND.base)
printf("ERror!");
OPND.top=OPND.base;
OPND.stacksize=STACK_INIT_SIZE;
return;
}
int In(char ch) //判断字符是否是运算符;
{
int r;
switch(ch)
{
case '+':
case '-':
case '':
case '/':
case '#':r=1;break;
default:r=0;break;
}
return r;
}
void PuSh(sqstack &OPTR,char ch) //运算符栈插入新的运算符栈顶元素;
{
if(OPTR.top-OPTR.base>=OPTR.stacksize) //栈满，追加存储空间;
{
OPTR.base=(char )realloc(OPTR.base,(OPTR.stacksize+S)*sizeof(char));
if(!OPTR.base)
printf("错误！");
OPTR.top=OPTR.base+OPTR.stacksize;
OPTR.stacksize+=S;
}
*OPTR.top++=ch;
printf("成功插入(puSh)运算符栈顶元素!
");
}
void PoP(sqstack &OPTR,char &ch) //删除字符的栈顶元素;(!!!!!!!!!!!!!!)
{
if(OPTR.top==OPTR.base)
printf("error");
ch= --OPTR.top;
printf("删除字符栈顶元素!
");
}
char GetTop(sqstack &OPTR) //得到运算符栈顶元素;(!!!!!!!!!!!!!)
{
char c;
if(OPTR.top==OPTR.base)
printf("error!");
c=*(OPTR.top-1);printf("运算符栈顶元素正常 "); return c;}
void Push(stack &OPND,int e) //运算数栈插入新的运算数栈顶元素;
{
if(OPND.top-OPND.base>=OPND.stacksize) //栈满，追加空间;
{ OPND.base=(int )realloc(OPND.base,(OPND.stacksize+S)*sizeof(int));
if(!OPND.base)
printf("运算数栈错误!");
OPND.top=OPND.base+OPND.stacksize;
OPND.stacksize+=S;
}
*OPND.top++=e;
printf("成功插入运算数栈!
");
}
void Pop(stack &OPND,int &e) //删除运算数栈的栈顶元素;(!!!!!!!!!!!!!!!)
{
if(OPND.top==OPND.base)
printf("error");e= --OPND.top;
printf("成功删除运算数栈!");
}
int Gettop(stack &OPND) //得到运算数栈顶元素;(!!!!!!!!!!!!!!!!!!)
{
int a;
if(OPND.top==OPND.base)
return 0;
else
a=*(OPND.top-1);
return a;
}
char compare(char a,char b) //判断运算符的优先级;
{
int i,j;
int array[7][7]= //1表示">"，-1表示"<",0表示"=",2表示不可能
{
{1,1,-1,-1,-1,1,1},
{1,1,-1,-1,-1,1,1},
{1,1,1,1,-1,1,1},
{1,1,1,1,-1,1,1},
{-1,-1,-1,-1,-1,0,2},
{1,1,1,1,2,1,1},
{-1,-1,-1,-1,-1,2,0}
};
switch(a)
{
case '+':i=0;break;
case '-':i=1;break;
case '*':i=2;break;
case '/':i=3;break;
case '(':i=4;break;
case ')':i=5;break;
case '#':i=6;break;
}
switch(b)
{
case '+':j=0;break;
case '-':j=1;break;
case '*':j=2;break;
case '/':j=3;break;
case '(':j=4;break;
case ')':j=5;break;
case '#':j=6;break;
}
if(array[i][j]==1)
return '>';
else if(array[i][j]==-1)
return '<';
else if(array[i][j]==0)
return '=';
else printf("error!");
printf("该函数被调用");
return 1;}
int operate(int p,char f,int q)
{
switch(f)
{
case '+':return p+q;
case '-':return p-q;
case '*':return p*q;
case '/':return p/q;
}
return 1;
}
int EvaluateExpression()
{
char c,f, d[100],e;
int i, num, tmpa, tmpb;
sqstack OPTR;
stack OPND;
InitStack(OPTR);Initstack(OPND);
PuSh(OPTR,'#');
c=getchar();
while(c!='#'||(e=GetTop(OPTR))!='#')
{
if(c>='0'&&c<='9')
{
i=0;
do{
d[i++]=c;
c=getchar();
}while(c>='0'&&c<='9');
d[i]='';
num=atoi(d);
Push(OPND, num);
}
else if(In(c))
{
switch(compare(GetTop(OPTR), c))
{
case '<': PuSh(OPTR, c);c=getchar();
break;
case '=': PoP(OPTR, f);c=getchar();
break;
case '>': PoP(OPTR, f);Pop(OPND, tmpb);Pop(OPND, tmpa);
Push(OPND, operate(tmpa, f, tmpb));
break;
}
}
}
return Gettop(OPND);
}
int EvaluateExpression(); //主操作函数
void main()
{
int r;
printf("请输入表达式:");
r=EvaluateExpression();
printf("输出结果为:%d
",r);
}
解决方案
解决方案二：
你有没有学数据结构啊 可以看看数据结构的书 可以把表达式转换成后置表达式然后计算 很方便的
解决方案三：
出入栈的限制条件把对括号的匹配也做成一个条件判断比较好。