数据结构：栈的应用—后缀表达式的运算、中缀表达式转后缀表达式

categories:

数据结构

后缀（逆波兰）表达式

中缀表达式：就是我们平时用的标准四则运算表达式，运算符在操作数中间，例如：9+（3-1）*3+10/2

后缀表达式：也称为逆波兰表达式，是将运算符写在操作数之后的表达式，例如上式的后缀表达式为：9 3 1 - 3 * + 10 2 / +

作用：对计算机而言，中缀表达式是比较复杂的结构，而逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序

计算机如何用后缀表达式求值

例如：中缀表达式 9+（3-1）*3+10/2 的后缀表达式 9 3 1 - 3 * + 10 2 / +，计算机如何用该后缀表达式进行运算呢

规则：从左到右遍历后缀表达式的每个数字和符号，遇到数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果

详细过程如下：9 3 1 - 3 * + 10 2 / +

初始化一个空栈，该栈用来对要运算的数字进出使用
后缀表达式中前三个都是数字，所以9 3 1依次进栈，如下图
接下来是 - 运算符，所以将栈顶的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈，如下图左侧
接着是数字3进栈，如下图右侧
接下来是* ，也就意味着栈中3与2出栈，相乘得到6，再将6入栈，如下图左侧
再下来是+ ，将6与9出栈，相加得到15，再将15入栈，如下图右侧
接着是10与2两数字进栈，如下图左侧
接下来是/ ，因此栈顶的2与10出栈，10与2相除得到5，5入栈，如下图右侧
最后是运算符+ ，所以5与15出栈相加得到20，再将20进栈，如下图左侧
后缀表达式遍历结束，最后栈中结果是20出栈，栈变为空，计算结束，如下图右侧

以上可以看出后缀表达式可以很顺利地解决计算问题，因此后缀表达式是很重要的，接下来就要知道常用的中缀表达式如何转换为后缀表达式

中缀表达式转后缀表达式

例：中缀表达式 9+（3-1）*3+10/2 转换为后缀表达式 9 3 1 - 3 * + 10 2 / +

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止，总结如下：
在这里插入图片描述

详细过程如下： 9+（3-1）*3+10/2 转换为后缀表达式 9 3 1 - 3 * + 10 2 / +

初始化一空栈，用来对符号进出栈使用，如下图左侧
第一个是数字9，直接输出，后面是符号+，进栈，如下图右侧
第三个字符是（，左括号还未配对，入栈，如下图左侧
第四个字符是数字3，直接输出，总表达式为9 3，接着是-，进栈，如下图右侧
接下来是数字1，输出，总表达式为9 3 1，后面是），此时，要去匹配之前的左括号，所以栈顶依次输出，直到（出栈。总的表达式现在为9 3 1 -，栈中剩下+，如下图左侧
紧接着是*，因为此时栈顶为+号，优先级低于乘号，因此不输出，乘号进栈，接着是数字3，输出，总表达式为9 3 1 - 3，如下图右侧
之后是+，此时栈顶为乘号，栈顶优先级高，因此栈中元素出栈并输出（没有比+更低的优先级，所以全部出栈），总输出表达式9 3 1 - 3 * +。然后将当前这个符号+进栈，如下图左侧
紧接着是数字10，直接输出，总表达式变为9 3 1 - 3 * + 10。然后是/ ,栈顶+优先级低于除号，/进栈，如下图右侧
接下来是最后一个数字2，输出，表达式为9 3 1 - 3 * +10 2，如下图左侧
中缀表达式遍历结束，将栈中符号依次全部出栈并输出，最后输出的后缀表达式为：9 3 1 - 3 * +10 2 / +

C代码如下：

//中缀表达式转后缀表达式
//中缀表达式存储在字符串中，为便于表示，代码使用9+(3-1)*3+8/2为例子

#include "stack.h"
#include <stdio.h>

int main()
{
    Stack s;
    InitStack(&s);

    const char mid[] = "9+(3-1)*3+8/2";  //中缀表达式
    char back[14];  //后缀表达式
    int i = 0;
    int j = 0;
    char useless;

    for (i = 0; i < 13; i++)
    {
        if (mid[i] <= '9'&&mid[i] >= '0')  //是数字，直接输出
        {
            back[j] = mid[i];
            j++;
        }
        else if (mid[i] == '(')  //是左括号，直接入栈
        {
            Push(&s, mid[i]);
        }
        else if (mid[i] == ')')  //是右括号，栈中出栈直到第一个左括号出栈
        {
            while (GetTop(&s) != '(')
            {
                Pop(&s, &back[j]);
                j++;
            }
            Pop(&s, &useless);            
        }
        else if (mid[i] == '*' || mid[i] == '/')  //是*/，出栈，直到栈空或者栈中遇到左括号或+-，当前符号入栈
        {
            while (!IsEmpty(&s) && (GetTop(&s) != '+' && GetTop(&s) != '-'))
            {
                Pop(&s, &back[j]);
                j++;
            }
            Push(&s, mid[i]);
        }
        else if (mid[i] == '+' || mid[i] == '-')  //是+-，出栈，直到栈空或者左括号当前符号入栈
        {
            while (!IsEmpty(&s)&&GetTop(&s) != '(')
            {
                Pop(&s, &back[j]);
                j++;
            }
            Push(&s, mid[i]);
        }
    }
    //中缀表达式遍历结束，要将栈中剩余符号依次弹出
    while (!IsEmpty(&s))
    {
        Pop(&s, &back[j]);
        j++;
    }
    back[j] = '\0';

    printf("中缀表达式： %s\n\n", mid);
    printf("后缀表达式： %s\n\n", back);

    return 0;
}

代码运行结果：
在这里插入图片描述