设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法
程序可以实现中缀表达式转换到后缀表达式，但是求值地时候出了问题，不知道怎么回事。希望大神么能给看看是哪里出了问题，帮忙修改一下。。。
#include<stdio.h>
#include<stdlib.h>
#define Max_Size 20
#define MaxSize 10
typedef char SElemType;
typedef struct lnode{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S)//初始化栈
{
S.base=(SElemType*)malloc(Max_Size*sizeof(SElemType));
if(!S.base)
exit(-1);
S.top=S.base;
S.stacksize=Max_Size;
}
SElemType GetTop(SqStack S)//取得栈顶元素
{
SElemType e;
if(S.top==S.base)
return -1;
e=*(S.top-1);
return e;
}
void Push(SqStack &S,SElemType e)//元素进栈
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+MaxSize)*sizeof(SElemType));
if(!S.base)
exit(-1);
S.top=S.base+S.stacksize;
S.stacksize+=MaxSize;
}
*S.top++=e;
}
void Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)
exit(-1);
e=*--S.top;
}
int In(char c)//判断是否为运算符
{
if((c=='+')||(c=='-')||(c=='*')||(c=='/')||(c=='(')||(c==')')||(c=='#'))
return 1;
else
return 0;
}
SElemType Operate(SElemType a,SElemType m,SElemType b)//运算
{
SElemType x;
switch(m){
case '+': x=a+b;break;
case '-': x=a-b;break;
case '*': x=a*b;break;
case '/': x=a/b;break;
}
return x;
}
SElemType Precede(SElemType m,SElemType n)//判断运算符的优先级
{
int a={{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},
{1,1,1,1,2,1,1},
{-1,-1,-1,-1,-1,2,0}};
switch(m){
case '+': m=0;break;
case '-': m=1;break;
case '*': m=2;break;
case '/': m=3;break;
case '(': m=4;break;
case ')': m=5;break;
case '#': m=6;break;
}
switch(n){
case '+': n=0;break;
case '-': n=1;break;
case '*': n=2;break;
case '/': n=3;break;
case '(': n=4;break;
case ')': n=5;break;
case '#': n=6;break;
}
return a;
}
voidEvaluateExpression()//将中缀表达式转换为后缀表达式并求值
{
SqStack OPTR,OPND;
SElemType x,c,a,theta,b;
InitStack(OPTR);
Push(OPTR,'#');
InitStack(OPND);
c=getchar();
putchar(c);
while(c!='#'||(GetTop(OPTR)!='#'))
{
if(!In(c))//不是运算符则进栈
{
Push(OPND,c);
c=getchar();
putchar(c);
}
else
switch(Precede(GetTop(OPTR),c))//比较栈顶运算符跟当前运算符的优先级
{
case -1: {
Push(OPTR,c);
c=getchar();
putchar(c);
break;}//当前运算符的优先级高，进栈
case 0 : {Pop(OPTR,x);
putchar(c);
c=getchar();
break;}//运算符优先级相同，退栈
case 1: {Pop(OPTR,theta);
Pop(OPND,b);
Pop(OPND,a);
putchar(b);
putchar(a);
putchar(theta);
x=Operate(a,theta,b);
putchar(x);
Push(OPND,x);//将运算结果入栈
break;}//当前运算符的优先级低，出栈，参与运算
}
}
printf("\n求值结果: ");
printf(GetTop(OPND));
printf("\n");
}
void main()
{
printf("请按顺序输入表达式 (表达式以'#'结束，如2*(3+2)# ): \n");
EvaluateExpression();
}
页:
[1]