weixinwobuwan
weixinwobuwan
采纳率50%
2015-12-17 02:52 阅读 1.5k
已采纳

怎样用c实现链栈的算术表达式运算,不得使用stl模板

按照严蔚敏版的书上的算法,用c语言链栈实现,不让使用stl模板,有没有原代码

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

2条回答 默认 最新

  • 已采纳
    q3733353520 我用双手-成就你的梦想 2015-12-19 06:37

    #include"stdio.h"

    #include"stdlib.h"

    #include"string.h"

    #include"math.h"

    #define true 1

    #define false 0

    #define OPSETSIZE 8

    typedef int Status;

    unsigned char Prior[8][8] =

    { // 运算符优先级表

    // '+' '-' '*' '/' '(' ')' '#' '^'

    /*'+'*/'>','>','<','<','<','>','>','<',

    /*'-'*/'>','>','<','<','<','>','>','<',

    /*'*'*/'>','>','>','>','<','>','>','<',

    /*'/'*/'>','>','>','>','<','>','>','<',

    /*'('*/'<','<','<','<','<','=',' ','<',

    /*')'*/'>','>','>','>',' ','>','>','>',

    /*'#'*/'<','<','<','<','<',' ','=','<',

    /*'^'*/'>','>','>','>','<','>','>','>'

    };

    typedef struct StackChar

    {

    char c;

    struct StackChar *next;

    }SC; //StackChar类型的结点SC

    typedef struct StackFloat

    {

    float f;

    struct StackFloat *next;

    }SF; //StackFloat类型的结点SF

    SC SC_Push(SC *s,char c) //SC类型的指针Push,返回p

    {

    SC *p=(SC
    )malloc(sizeof(SC));

    p->c=c;

    p->next=s;

    return p;

    }

    SF SF_Push(SF *s,float f) //SF类型的指针Push,返回p

    {

    SF *p=(SF
    )malloc(sizeof(SF));

    p->f=f;

    p->next=s;

    return p;

    }

    SC *SC_Pop(SC *s) //SC类型的指针Pop

    {

    SC *q=s;

    s=s->next;

    free(q);

    return s;

    }

    SF *SF_Pop(SF *s) //SF类型的指针Pop

    {

    SF *q=s;

    s=s->next;

    free(q);

    return s;

    }

    float Operate(float a,unsigned char theta, float b) //计算函数Operate

    {

    switch(theta)

    {

    case '+': return a+b;

    case '-': return a-b;

    case '*': return a*b;

    case '/': return a/b;

    case '^': return powf(a,b);

    default : return 0;

    }

    }

    char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'};

    Status In(char Test,char *TestOp)

    {

    int Find=false;

    for (int i=0; i< OPSETSIZE; i++)

    {

    if(Test == TestOp[i])

    Find= true;

    }

    return Find;

    }

    Status ReturnOpOrd(char op,char *TestOp)

    {

    for(int i=0; i< OPSETSIZE; i++)

    {

    if (op == TestOp[i])

    return i;

    }

    }

    char precede(char Aop, char Bop)

    {

    return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];

    }

    float EvaluateExpression(char* MyExpression)

    {

    // 算术表达式求值的算符优先算法

    // 设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合

    SC *OPTR=NULL; // 运算符栈,字符元素

    SF *OPND=NULL; // 运算数栈,实数元素

    char TempData[20];

    float Data,a,b;

    char theta,*c,Dr[]={'#','\0'};

    OPTR=SC_Push(OPTR,'#');

    c=strcat(MyExpression,Dr);

    strcpy(TempData,"\0");//字符串拷贝函数

    while (*c!= '#' || OPTR->c!='#')

    {

    if (!In(*c, OPSET))

    {

    Dr[0]=*c;

    strcat(TempData,Dr); //字符串连接函数

    c++;

    if (In(*c, OPSET))

    {

    Data=atof(TempData); //字符串转换函数(double)

    OPND=SF_Push(OPND, Data);

    strcpy(TempData,"\0");

    }

    }

    else // 不是运算符则进栈

    {

    switch (precede(OPTR->c, *c))

    {

    case '<': // 栈顶元素优先级低

    OPTR=SC_Push(OPTR, *c);

    c++;

    break;

    case '=': // 脱括号并接收下一字符

    OPTR=SC_Pop(OPTR);

    c++;

    break;

    case '>': // 退栈并将运算结果入栈

    theta=OPTR->c;OPTR=SC_Pop(OPTR);

    b=OPND->f;OPND=SF_Pop(OPND);

    a=OPND->f;OPND=SF_Pop(OPND);

    OPND=SF_Push(OPND, Operate(a, theta, b));

    break;

    } //switch

    }

    } //while

    return OPND->f;

    } //EvaluateExpression

    int main(void)

    {

    char s[128];

    puts("请输入表达式:");

    gets(s);

    puts("该表达式的值为:");

    printf("%s\b=%g\n",s,EvaluateExpression(s));

    return 0;

    }

    
    
    点赞 评论 复制链接分享
  • q3733353520 我用双手-成就你的梦想 2015-12-17 06:57

相关推荐