算法——算术表达式计算问题（堆栈典型应用）

古城微笑少年丶 2022-07-26 08:48 93阅读 0赞

## 1.中缀表达式和后缀表达式的描述 ##

在编译系统中，算术表达式可以分为三类：**算术表达式，关系表达式，逻辑表达式**。

任何一个算术表达式都是由：操作数，运算符和分界符组成。我们把**操作数，运算符和分界符（分界符标志了一个算术表达式的结束）称为一个算术表达式的单词**

**中缀表达式**：算术表达式中的运算符总是出现在两个操作数之间（除单目运算符外）

> A+（B-C/D）\*E

**后缀表达式**：表达式中的运算符出现在操作数之后。编译系统对于中缀表达式处理方法是将其变成后缀表达式

> ABCD/-E\*+

--------------------

## 2.后缀表达式的特点 ##

1.  后缀表达式的操作数和中缀表达式的操作数先后次序完全相同（上面ABCDE），只是运算符的先后次序改变了（+-/\*）；
2.  后缀表达式中没有括号，后缀表达式的运算次序就是其执行次序

--------------------

## 3.后缀表达式的实现过程 ##

编译系统设置一个存放运算符的堆栈，初始时栈顶置一个分界符“\#”。编译系统从左到右依次扫描中缀表达式，每读到一个操作数就把它作为后缀表达式的一部分输出，每读到一个运算符（分界符也看作运算符）就将其优先级与栈顶运算符优先级运算符进行比较，以决定是就所读到的运算符进栈，还是将栈顶运算符作为最为后缀算术表达式的一部分输出。

1.运算符优先级别注意：  
若把O1看成栈顶运算符，O2看成当前扫描读到的运算符。

*  **当O1为“+”或“-”，O2为“\*”或“/”时，O1的优先级 < O2的优先级**(满足先乘除，后加减)
 *  **当O1为“+”“-”“\*”或“/”，O2为“（”时，O1的优先级 < O2的优先级**（满足先括号内，后括号外的规则）
 *  **当O1的运算符和O2的运算符同级别时，O1的优先级 > O2的优先级别**（同级别先左后右规则）
 *  **由于后缀表达式无括号，当O1为“（”，O2为“）”时，用标记“=”使算法在此时去掉该对算法；**
 *  **当O1为“\#”时，O2为“\#”时，用标记“=”使算法在此时结束处理**
 *  **若表中的值为空，则不允许出现这种情况，一旦出现即为中缀算术表达式语法出错，如O1为“）”，而O2为“（”情况，即为中缀表达式语法错误！**

2.算法步骤：  
（1）设置一个堆栈，初始时将栈顶元素置为\#

（2）顺序读入中缀算术表达式，当读到的单词为操作数是就将其输出，并接着读下一个单词

（3）单读到的单词为运算符时，令a为当前栈顶运算符的变量，b为当前扫描读到运算符的变量，把当前读到的运算符赋给b,然后比较变量a的优先级和b的优先级。若a的优先级高于ｂ的优先级，则将ａ退栈并作为后缀表达式的一个单词输出，，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。

> 若优先级　ａ＜ｂ，则将ｂ的值进栈，然后接着读下一个单词
    > 
    > 若优先级　ａ＞ｂ，则将ａ退栈并作为后缀表达式的一个单词输出，然后比较新的栈顶元素运算符ａ的优先级与ｂ的优先级。
    > 
    > 若优先级　ａ＝ｂ且ａ为“（”，ｂ为“）”。则将ａ退栈，接着读下一个单词
    > 
    > 若优先级　ａ＝ｂ且ａ为“＃”，ｂ为“＃”。算法结束。

## ４.函数实现 ##

int PostExp(char str[])  //借助堆栈计算后缀表达式str的值
    {
        DataType x,x1,x2;
        int i;
        LsNode *head;    //定义头指针变量head
        StackInitiate(&head);   //初始化链式堆栈head
        for(i-0;str[i]!=#;i++) //循环直到输入为#
        {
            if(isdigit(str[i]))   //当str[i]为操作数时
            {
                x=(int)(str[i]-48);  //转换成int类型数据存于变量x中
                StackPush(head,x);   //x入栈
            }
            else                     //当str[i]为运算符时
            {  
                StackPop(head,&x2);  //退栈的操作数，存于变量x2中
                StackPop(head,&x1);  //退栈的被操作数，存于变量x1中
                switch(str[i])      //执行str[i]所表示的运算
                {
                case '+':
                    {
                        x1+=x2; break;
                    }
                case '-':
                    {
                        x1-=x2; break;
                    }
                case '*':
                    {
                        x1*=x2; break;
                    }
                case '/':
                    {
                        if(x2==0.0)
                        {
                            printf("除数为0错误！\n");
                            exit(0);
                        }
                        else
                        {
                            x1/=x2;
                            break;
                        }
                    }
    
                }
                StackPush(head,x1);    //运算结果入栈
            }
    
        }
        StackPop(head,&x);     //得到计算结果存于x
        return x;             //返回计算结果
    }

## 5.应用 ##

【例4】设有后缀算术表达式ABCD/-E\*+，其中，变量A等于3，变量B等于6，变量C等于4，变量D等于2，变量E等于5，设计一个程序，求出该后缀算术表达式的值。

#include<stdio.h>
    #include<malloc.h> //包含有exit()函数
    #include<stdlib.h> //包含isdigit()函数
    #include<ctype.h> //定义DataType（）函数
    typedef int DataType;
    #include"LinStack.h"
    
    int PostExp(char str[])  //借助堆栈计算后缀表达式str的值
    {
        DataType x,x1,x2;
        int i;
        LsNode *head;    //定义头指针变量head
        StackInitiate(&head);   //初始化链式堆栈head
        for(i-0;str[i]!=#;i++) //循环直到输入为#
        {
            if(isdigit(str[i]))   //当str[i]为操作数时
            {
                x=(int)(str[i]-48);  //转换成int类型数据存于变量x中
                StackPush(head,x);   //x入栈
            }
            else                     //当str[i]为运算符时
            {  
                StackPop(head,&x2);  //退栈的操作数，存于变量x2中
                StackPop(head,&x1);  //退栈的被操作数，存于变量x1中
                switch(str[i])      //执行str[i]所表示的运算
                {
                case '+':
                    {
                        x1+=x2; break;
                    }
                case '-':
                    {
                        x1-=x2; break;
                    }
                case '*':
                    {
                        x1*=x2; break;
                    }
                case '/':
                    {
                        if(x2==0.0)
                        {
                            printf("除数为0错误！\n");
                            exit(0);
                        }
                        else
                        {
                            x1/=x2;
                            break;
                        }
                    }
    
                }
                StackPush(head,x1);    //运算结果入栈
            }
    
        }
        StackPop(head,&x);     //得到计算结果存于x
        return x;             //返回计算结果
    }
    
    void main()
    {
        char str[]="3642/-5*+#";
        int result;
        result=PostExp(str);
        printf("后缀算术表达式计算结果为：%d",result);
    }

1.请点击————>[关于是否为阿拉伯数字isdigit（）函数的介绍][isdigit]  
2.exit()函数  
exit() 结束当前进程/当前程序/，在整个程序中，只要调用 exit ，就结束

return() 是当前函数返回，当然如果是在主函数main, 自然也就结束当前进程了，如果不是，那就是退回上一层调用。在多个进程时.如果有时要检测上进程是否正常退出的.就要用到上个进程的返回值..

exit(1)表示进程正常退出. 返回 1;

exit(0)表示进程非正常退出. 返回 0.

[isdigit]: http://baike.sogou.com/v10526760.htm?fromTitle=isdigit