设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法

fxkect · 发表于 2013-12-2 21:46:49

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

程序可以实现中缀表达式转换到后缀表达式，但是求值地时候出了问题，不知道怎么回事。
希望大神么能给看看是哪里出了问题，帮忙修改一下。。。
#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[7][7]={{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[m][n];
}
void  EvaluateExpression()  //将中缀表达式转换为后缀表达式并求值
{
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();
}

账号		自动登录	找回密码
密码			立即注册