鱼C论坛

 找回密码
 立即注册
查看: 3170|回复: 0

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

[复制链接]
发表于 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();
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表