数据结构例程——表达式求值（用栈结构）

我会带着你远行 2022-04-17 00:04 172阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

本文针对[数据结构基础系列网络课程(3)：栈和队列][3]中第5课时[栈的应用1-表达式求值][1-]。

例：用户输入一个包含“+”、“-”、“\*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。  
![这里写图片描述][20150915105847204]

解答：

#include <stdio.h>#include <stdlib.h>#define MaxOp 100#define MaxSize 100struct  //设定运算符优先级{    char ch;   //运算符    int pri;   //优先级}lpri[]= {
        {
        '=',0},{
        '(',1},{
        '*',5},{
        '/',5},{
        '+',3},{
        '-',3},{
        ')',6}},rpri[]= {
        {
        '=',0},{
        '(',6},{
        '*',4},{
        '/',4},{
        '+',2},{
        '-',2},{
        ')',1}};int leftpri(char op)    //求左运算符op的优先级{    int i;    for (i=0; i<MaxOp; i++)        if (lpri[i].ch==op)            return lpri[i].pri;}int rightpri(char op)  //求右运算符op的优先级{    int i;    for (i=0; i<MaxOp; i++)        if (rpri[i].ch==op)            return rpri[i].pri;}bool InOp(char ch)       //判断ch是否为运算符{    if (ch=='(' || ch==')' || ch=='+' || ch=='-'            || ch=='*' || ch=='/')        return true;    else        return false;}int Precede(char op1,char op2)  //op1和op2运算符优先级的比较结果{    if (leftpri(op1)==rightpri(op2))        return 0;    else if (leftpri(op1)<rightpri(op2))        return -1;    else        return 1;}void trans(char *exp,char postexp[])//将算术表达式exp转换成后缀表达式postexp{    struct    {        char data[MaxSize]; //存放运算符        int top;            //栈指针    } op;               //定义运算符栈    int i=0;                //i作为postexp的下标    op.top=-1;    op.top++;                  //将'='进栈    op.data[op.top]='=';    while (*exp!='\0')      //exp表达式未扫描完时循环    {        if (!InOp(*exp))        //为数字字符的情况        {            while (*exp>='0' && *exp<='9') //判定为数字            {                postexp[i++]=*exp;                exp++;            }            postexp[i++]='#';   //用#标识一个数值串结束        }        else    //为运算符的情况            switch(Precede(op.data[op.top],*exp))            {            case -1:           //栈顶运算符的优先级低:进栈                op.top++;                op.data[op.top]=*exp;                exp++;     //继续扫描其他字符                break;            case 0:        //只有括号满足这种情况                op.top--;      //将(退栈                exp++;     //继续扫描其他字符                break;            case 1:             //退栈并输出到postexp中                postexp[i++]=op.data[op.top];                op.top--;                break;            }    } //while (*exp!='\0')    while (op.data[op.top]!='=')    //此时exp扫描完毕,退栈到'='为止    {        postexp[i++]=op.data[op.top];        op.top--;    }    postexp[i]='\0';    //给postexp表达式添加结束标识}float compvalue(char exp[]) //计算后缀表达式的值{    struct    {        float data[MaxSize];    //存放数值        int top;            //栈指针    } st;               //定义数值栈    float d;    char ch;    int t=0; //t作为exp的下标    st.top=-1;    ch=exp[t];    t++;    while (ch!='\0')    //exp字符串未扫描完时循环    {        switch (ch)        {        case'+':            st.data[st.top-1]=st.data[st.top-1]+st.data[st.top];            st.top--;            break;        case '-':            st.data[st.top-1]=st.data[st.top-1]-st.data[st.top];            st.top--;            break;        case '*':            st.data[st.top-1]=st.data[st.top-1]*st.data[st.top];            st.top--;            break;        case '/':            if (st.data[st.top]!=0)                st.data[st.top-1]=st.data[st.top-1]/st.data[st.top];            else            {                printf("\n\t除零错误!\n");                exit(0);  //异常退出            }            st.top--;            break;        default:            d=0; //将数字字符转换成数值存放到d中            while (ch>='0' && ch<='9')   //为数字字符            {                d=10*d+ch-'0';                ch=exp[t];                t++;            }            st.top++;            st.data[st.top]=d;        }        ch=exp[t];        t++;    }    return st.data[st.top];}int main(){    char exp[]="(56-20)/(4+2)"; //可将exp改为键盘输入    char postexp[MaxSize];    trans(exp,postexp);    printf("中缀表达式:%s\n",exp);    printf("后缀表达式:%s\n",postexp);    printf("表达式的值:%g\n",compvalue(postexp));    return 0;}
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7 
        8 
        9 
        10 
        11 
        12 
        13 
        14 
        15 
        16 
        17 
        18 
        19 
        20 
        21 
        22 
        23 
        24 
        25 
        26 
        27 
        28 
        29 
        30 
        31 
        32 
        33 
        34 
        35 
        36 
        37 
        38 
        39 
        40 
        41 
        42 
        43 
        44 
        45 
        46 
        47 
        48 
        49 
        50 
        51 
        52 
        53 
        54 
        55 
        56 
        57 
        58 
        59 
        60 
        61 
        62 
        63 
        64 
        65 
        66 
        67 
        68 
        69 
        70 
        71 
        72 
        73 
        74 
        75 
        76 
        77 
        78 
        79 
        80 
        81 
        82 
        83 
        84 
        85 
        86 
        87 
        88 
        89 
        90 
        91 
        92 
        93 
        94 
        95 
        96 
        97 
        98 
        99 
        100 
        101 
        102 
        103 
        104 
        105 
        106 
        107 
        108 
        109 
        110 
        111 
        112 
        113 
        114 
        115 
        116 
        117 
        118 
        119 
        120 
        121 
        122 
        123 
        124 
        125 
        126 
        127 
        128 
        129 
        130 
        131 
        132 
        133 
        134 
        135 
        136 
        137 
        138 
        139 
        140 
        141 
        142 
        143 
        144 
        145 
        146 
        147 
        148 
        149 
        150 
        151 
        152 
        153 
        154 
        155 
        156 
        157 
        158

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[3]: http://edu.csdn.net/course/detail/1405/
[1-]: http://edu.csdn.net/course/detail/1405/22208
[20150915105847204]: /images/20220417/1906cb1e4edc4059b79d6c0f5d919ea0.png
[SouthEast]: /images/20220417/d89abd0e7483481392ce05b8e7918ccc.png