| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 820 人关注过本帖
标题:设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法 ...
只看楼主 加入收藏
fxkect
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2013-12-1
结帖率:0
收藏
已结贴  问题点数:20 回复次数:3 
设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值的算法
程序可以实现中缀表达式转换到后缀表达式,但是求值地时候出了问题,不知道怎么回事。
希望大神么能给看看是哪里出了问题,帮忙修改一下。。。
#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();
}

[ 本帖最后由 fxkect 于 2013-12-2 20:40 编辑 ]
搜索更多相关主题的帖子: include 表达式 
2013-12-01 22:04
yuccn
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:何方
等 级:版主
威 望:167
帖 子:6814
专家分:42393
注 册:2010-12-16
收藏
得分:10 
问问题要先把问题清理好怎么问把,谁知道你期望是什么

我行我乐
公众号:逻辑客栈
我的博客:
https://blog.yuccn. net
2013-12-02 09:51
fxkect
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2013-12-1
收藏
得分:0 
回复 2楼 yuccn
自己修改了半天也没弄明白哪里出错了,只能希望又人能帮忙看看,
共同找一下问题所在。。。
2013-12-02 20:43
RFM199
Rank: 2
等 级:论坛游民
帖 子:1
专家分:15
注 册:2012-11-15
收藏
得分:10 
我看了一下,两个栈都用的char类型的符号栈,建议用两种栈,一个数字栈,一个符号栈。这个地方就有错了:
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;
}
做运算前,由于你是符号类型的,应该进行类型转换,a=a-'0';
可以参看课本源码:
 SElemType Precede(SElemType t1,SElemType t2) /* 同algo3-6.c */
 { /* 根据教科书表3.1,判断两符号的优先关系 */
   SElemType f;
   switch(t2)
   {
     case '+':
     case '-':if(t1=='('||t1=='=')
                f='<';
              else
                f='>';
              break;
     case '*':
     case '/':if(t1=='*'||t1=='/'||t1==')')
                f='>';
              else
                f='<';
              break;
     case '(':if(t1==')')
              {
                printf("ERROR1\n");
                exit(ERROR);
              }
              else
                f='<';
              break;
     case ')':switch(t1)
              {
                case '(':f='=';
                         break;
                case '=':printf("ERROR2\n");
                         exit(ERROR);
                default: f='>';
              }
              break;
     case '=':switch(t1)
              {
                case '=':f='=';
                         break;
                case '(':printf("ERROR2\n");
                         exit(ERROR);
                default: f='>';
              }
   }
   return f;
 }

 Status In(SElemType c) /* 几乎与algo3-6.c相同 */
 { /* 判断c是否为运算符 */
   switch(c)
   {
     case'+':
     case'-':
     case'*':
     case'/':
     case'(':
     case')':
     case'=':return TRUE; /* 此句不同于algo3-6.c */
     default:return FALSE;
   }
 }

 SElemType Operate(SElemType a,SElemType theta,SElemType b) /* 有改动 */
 {
   SElemType c;
   switch(theta)
   {
     case'+':c=a+b;
             break;
     case'-':c=a-b;
             break;
     case'*':c=a*b;
             break;
     case'/':c=a/b;
   }
   return c;
 }

 SElemType EvaluateExpression() /* 有改动 */
 { /* 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈 */
   SqStack OPTR,OPND;
   SElemType a,b,d,x,theta;
   char c; /* 存放由键盘接收的字符串 */
   char z[6]; /* 存放整数字符串 */
   int i;
   InitStack(&OPTR); /* 初始化运算符栈 */
   Push(&OPTR,'='); /* =是表达式结束标志 */

   InitStack(&OPND); /* 初始化运算数栈 */
   c=getchar();
   GetTop(OPTR,&x);
   while(c!='='||x!='=')
   {
     if(In(c)) /* 是7种运算符之一 */
       switch(Precede(x,c))
       {
         case'<':Push(&OPTR,c); /* 栈顶元素优先权低 */
                 c=getchar();
                 break;
         case'=':Pop(&OPTR,&x); /* 脱括号并接收下一字符 */
                 c=getchar();
                 break;
         case'>':Pop(&OPTR,&theta); /* 退栈并将运算结果入栈 */
                 Pop(&OPND,&b);
                 Pop(&OPND,&a);
                 Push(&OPND,Operate(a,theta,b));
       }
     else if(c>='0'&&c<='9') /* c是操作数 */
     {
       i=0;
       do
       {
         z[i]=c;
         i++;
         c=getchar();
       }while(c>='0'&&c<='9');
       z[i]=0;
       d=atoi(z); /* 将字符串数组转为整型存于d */
       Push(&OPND,d);
     }
     else /* c是非法字符 */
     {
       printf("ERROR3\n");
       exit(ERROR);
     }
     GetTop(OPTR,&x);
   }
   GetTop(OPND,&x);
   return x;
 }

 void main() /* 有改动 */
 {
   printf("请输入算术表达式,负数要用(0-正数)表示,并以=结束\n");
   printf("%d\n",EvaluateExpression());
 }
2013-12-03 11:46
快速回复:设计并实现将一个中缀表达式转换成逆波兰式,然后对此逆波兰表达式求值 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016147 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved