【数据结构】C语言实现表达式的转换

栈在表达式转换中的应用

导读

大家好！很高兴又和大家见面啦！！！ 经过前面的学习，我们已经了解了表达式的三种形式以及它们对应的组成结构：

• 波兰（前缀）表达式：操作符 左操作数 右操作数；
• 中缀表达式：左操作数 操作符 右操作数；
• 逆波兰（后缀）表达式：左操作数 右操作数 操作符；

在上一篇内容中，我们详细介绍了如何手动进行这些表达式的相互转换和求值以及如何通过程序完成波兰表达式与逆波兰表达式的求值。

我相信大家在阅读完上一篇内容后，对表达式之间的相互转换的基本原理和求值以及比较熟悉了。一方面是为了强化表达式之间的相互转换相关的知识点，另一方面就是为了提高咱们的动手能力，因此，在今天的内容中，我们将会详细介绍如何通过计算机来完成表达式之间的相互转换。接下来我们就正式进入咱们今天的内容吧！！！

为了更好的进行表达式之间的转换，我们首先要来重新认识一下咱们熟知的中缀表达式。

一、中缀表达式

中缀表达式从我们第一次接触数学这门学科开始，它就一直陪伴在我们的学习生涯中。对于中缀表达大家应该是非常熟悉了，我们常见的中缀表达式有以下几种情况：

1. 单一运算：a b、a - b、a * b、a / b；
2. 不带括号的混合运算：a b - c、a b * c、a b / c、a * b / c；
3. 带括号的混合运算：(a b) * c；

当我们遇到这三种不同的情况时，我们采取的运算规则是不相同的：

1. 单一运算：从左往右依次进行运算；
2. 不带括号的混合运算：先乘除后加减；
3. 带括号的混合运算：括号优先，乘除其次，加减最后；

当然，对于学习计算机的朋友而言，在我们实际进行的表达式求值时肯定不止' '、'-'、'*'、'/'这四种运算符，这时我们就需要根据不同操作符的优先级来进行运算，当两个操作符之间的优先级相同时，我们则需要根据操作符的结合性来进行运算，操作符的优先级与结合性如下所示：

【数据结构】C语言实现表达式的转换_表达式转换_02

如果大家有对这些操作符的优先级与结合性不太了解的可以查询上表。在这些操作符中，"()"是需要我们关注的对象，当它作为操作符时，它是函数调用操作符，而当它出现在操作符与操作数中间a * (b c)，它则是作为界限符。我们在进行运算时，需要优先运算界限符中的内容。

！！！这里有一点需要注意：

操作符的优先级与结合性是对于同一个操作数两边的操作符而言，而对于不同操作数两边的操作符无法进行比较，如下所示：

【数据结构】C语言实现表达式的转换_栈_03

因此我们在进行运算时的最基本的原则是从左往右依次运算，当遇到具体的操作符时再根据操作符的结合性来进行具体的运算方向。

在了解了中缀表达式的不同情况之后，下面我们就要来看一下对于不同情况下的中缀表达式而言，我们又应该如何来区分表达式的各个组成部分；

二、表达式的组成部分

2.1 单一运算符

当中缀表达式为单一运算符组成的表达式时，我们只需要从左往右对表达式进行扫描就能很容易的找到表达式的各个组成部分，如下所示：

【数据结构】C语言实现表达式的转换_表达式转换_04

在这种情况下，我们从左往右进行运算的话，得到的结果就是下一个操作符的左操作数，因此如果要进行改写的话我们只需要在遇到操作符时将操作符进行移动即可完成；

2.2 不带括号的混合运算符

当中缀表达式为不带括号的混合运算符时，我们同样还是从左往右扫描，但是我们不能直接对扫描到的对象进行改写，如下所示：

【数据结构】C语言实现表达式的转换_C语言_05

在这个例子中我们可以看到表达式中存在4中运算符——' '、'-'、'*'、'/'。在这种情况下，我们从左往右扫描时就需要判断右操作数两边的运算符的优先级，具体步骤如下所示：

1. 对于操作数b来说，左边的操作符优先级低于右边的操作符，因此右边的操作符先进行运算，此时运算的第一部分为b * c；
2. 运算完的结果为新的操作数，该操作数左边的操作符与右边的操作符优先级相同，按照操作符的结合性，从左往右进行计算，此时运算的第二部分为a b * c；
3. 运算完后的结果为新的操作数，但此时对于操作符'-'来说它是左操作数，因此我们要找到右操作数d；
4. 对于操作数d来说，左边的操作符优先级低于右边的操作符，因此右边的操作符先进行运算，此时运算的第三部分为d / e；
5. 运算后的结果作为新的操作数，对于操作符'-'来说，第二部分的运算结果作为左操作数，第三部分的运算结果作为右操作数，最后再进行运算，此时运算的第四部分为a b * c - d / e；

在确定了各个分部以及组成部分后我们再进行操作符的移动就能完成改写；

2.3 带括号的混合运算符

当中缀表达式中带括号时，此时我们不仅要判断操作符的优先级，还需要处理括号，如下所示：

【数据结构】C语言实现表达式的转换_表达式转换_06

运算时，我们同样还是从左往右扫描，在这种情况下，我们在进行运算时的逻辑如下所示：

1. 扫描到左界限符时，继续往右进行扫描，当遇到右操作数时对操作数左右两侧的内容进行判断：

• 右侧是运算符：进行左右运算符的优先级判定，并根据优先级进行相应的运算；
• 右侧是右界限符：对两个界限符中间的内进行运算；

1. 扫描到操作符时，需要继续往右扫描，当遇到右操作数时对操作数的左右两侧的内容进行判断：

• 右侧是运算符：进行左右运算符的优先级判定，并根据优先级进行相应的运算；
• 右侧是左界限符：重复步骤1的内容；

可以看到，当表达式中存在括号时，我们在进行运算的过程中做的最多的就是对括号与操作符之间的判断与相应的处理。如果需要将表达式进行改写，那我们同样也是先从界限符内进行表达式的改写。如果处理好界限符与操作符，那实际上我们在运算或者改写时的步骤就是前面两种情况中的任意一种。

因此，对于这三种情况下的表达式，我们不管是进行运算还是改写，我们都需要处理好运算符与界限符以及运算符与运算符之间的关系。处理好了这些问题，我们才能正确的划分表达式的各个分部以及各个分部的组成部分，之后我们才能正常进行相应的操作；

三、表达式改写

通过前面的介绍，我们现在对表达式的改写有了一个大致的思路：

1. 扫描表达式
2. 处理界限符
3. 处理操作符
4. 改写表达式

这个思路具体可不可行，我们目前还是不清楚的，因此在实现表达式的改写之前，我们还需要理顺实现表达式改写的思路，然后根据具体的思路来设计表达式改写的算法，最后才是通过代码来实现算法。接下来我们就来通过对上述步骤进行一一的分析，进一步完善咱们的改写思路；

3.1 问题分析

1. 扫描表达式

当我们对表达式进行扫描时，我们需要思考两个问题——扫描的方向和扫描对象的处理。

在上一篇内容中我们在探讨前缀表达式的实现时有对表达式扫描的方向进行过探讨，最后得到的结论是从操作数的一端进行扫描。但是对于中缀表达式而言，不管是从左往右还是从右往左，我们扫描时肯定是先扫描到操作数再扫描到操作符，既然这样那是不是说中缀表达式从左往右和从右往左都是一样的呢？

从理论上来讲，中缀表达式的扫描方向是不影响操作结果的，因此我们从哪个方向开始进行扫描都是可以的。但是不同方向扫描对扫描对象的处理是有些许区别的，就比如界限符"()"。当我们从左往右扫描时，肯定是先扫描到左界限符，而我们从右往左扫描时，则是先扫描到右界限符。

在前面介绍栈在括号匹配问题中的应用时，我们就介绍过了，可以在进行括号匹配时通过从左往右扫描，对左括号的入栈和右括号的出栈来进行对应括号的匹配。那如果我们从右往左扫描则是刚好相反，需要对右括号进行入栈对左括号进行出栈来进行匹配。我个人是比较倾向前者的，因为在匹配的过程中我们得到的匹配结果为"()"，而通过后者进行匹配的话我们得到的匹配结果则是")("，总感觉哪里怪怪的。

因此，在本篇内容中，我将通过从左往右扫描的方式来实现表达式的转换。而对扫描对象的处理我们需要通过后续的问题来进行解答；

1. 对界限符的处理

当我们从左往右扫描时，如果我们遇到界限符，那肯定是左界限符，而界限符中的内则是从左界限符与其匹配的右界限符中间的所有内容。而在处理界限符中的内容时，实际上就是在处理操作符的优先级。而对于界限符的匹配我们则可以通过栈来实现。现在问题来了，我们如何来处理优先级不同的操作符；

1. 对操作符的处理

在今天的内容中，我们主要是以处理加减乘除这四种操作符为例来介绍表达式之间的转换。在处理操作符的过程中我们主要会遇到两种情况：

• 在没有界限符的影响时，它们之间的运算规则是先乘除后加减。因此如果我们先遇到' '和'-'时我们则需要判断下一个操作符是否为'*'或者'/'，如果不是则可以正常进行运算，如果是则需要先运算'*'和'/'；
• 在有界限符的影响时，运算规则则变成了先括号，再乘除，后加减。因此如果我们先遇到的是操作符，我们则需要对下一个对象进行判断，如果是操作数，则需要根据没有界限符时的处理方式来对操作符进行处理，如果是界限符，则需要继续扫描界限符中的内容，并根据具体的内容选择对操作符的处理方式；

1. 改写表达式

在确定好对操作符的处理后，接下来我们就需要通过操作符来对表达式进行拆分。对于中缀表达式而言，不管有没有界限符的影响，操作符的左边与右边一定是对应的操作数，也就是：左操作数 操作符 右操作数。因此当我们遇到操作符时，位于操作符左边的部分一定是该操作符的左操作数，如果我们要将其转化为前缀表达式，我们只需要将操作符提前就行；而操作符的右边的部分一定是该操作符的右操作数，如果我们要将其转化为后缀表达式，我们只需要将操作符置后即可。也就是说在改写表达式的过程中对左右操作数的判定就及其重要了；

改写表达式的原理我们已经明确了，接下来就是如何来区分操作符的左右操作数。我们以表达式"a * (b - c / d) e"为例，当我们对其进行扫描时，我们需要先确定表达式的运算顺序。当我们从左往右依次扫描的话，我们不难得到下面的扫描结果：

【数据结构】C语言实现表达式的转换_数据结构_07

在这个例子中，我们的整个操作流程如下所示：

• 可以看到当我们在遇到操作符1时我们不能直接进行操作，还需要往后扫描来确定是否存在界限符；
• 当扫描到操作符2时，我们也不能进行操作，还需要与操作符3的优先级进行判断，来确定运算的先后顺序；
• 当扫描到操作符3时，我们需要先于操作符2的优先级进行判断，此时操作符3的优先级高于操作符2，因此我们需要再与操作数4的右侧对象进行判断，此时操作数4的右侧为界限符2，而界限符1与界限符2刚好匹配，因此我们需要对操作符3进行相应的操作，而操作数3和操作数4则分别是操作符3的左操作数和右操作数，
• 在完成对操作符3的操作之后，得到的整体是作为操作符2的右操作数，而操作数2则是操作符2的左操作数，因此我们可以对该操作符进行相应的操作；
• 完成操作符2的操作后，这时我们就完成了界限符内的操作，此时我们需要判断操作符4与操作符1的优先级。此时操作符1的优先级是高于操作符4的，因此操作数1和界限符内的全部内容分别为操作符1的左右操作数，此时我们就可以对操作符1进行相应的操作；
• 完成操作符1的操作后，我们需要判断操作数5之后的内容，此时得到的是结束标志，我们可以得到操作符4的左侧的全部内容为其左操作数，而操作数5则是其右操作数，因此我们可以对操作符4进行相应的操作。

经过上述流程，从逻辑上来看，完成表达式的改写是完全没问题的。现在如何选择合适的数据结构来完成整个算法则是成了重点内容了。

从我们目前已学过的算法来看，我们可以选择的右顺序表、链表、栈、队列。当表达式中存在界限符时，我们之前有通过栈来实现括号匹配，在上一个篇章中我们同样也通过栈实现了表达式的求值，那是不是说明在表达式的转换中我们也可以通过栈来实现呢？我们接着往下看；

3.2 算法设计

在前面对表达式"a * (b - c / d) e"进行改写的流程中不知道大家有没有注意一个点——先被扫描的操作符和操作数都无法作为进行改写的依据，我们想要确认表达式的分部和组成部分只能通过后面的操作符来确定，这种操作方式很符合LIFO的操作特性，具体是不是呢？我们还是通过这个例子来按照我们之前的逻辑进行一次演示：

从演示中我们可以看到，我们确实可以通过栈来实现表达式的转换，但是还是存在几个问题：

1. 出栈后的元素如何存放？
2. 当遇到需要进行两个操作符之间优先级的比较时如何获取前一个操作符？

对于第一个问题，相信大家都已经想到了改进的方案——通过字符数组来进行存储。对于出栈的这些元素而言，它们实际上就是一个一个的字符，并且它们在进行出栈后，需要做的事情无非就是改变操作符的位置，我们完全可以通过字符数组来对其进行存储。

而对于第二个问题，相信也有朋友有了一个改进方案——通过字符变量来记录前一个操作符。在增加一个字符变量之后，那我们则可以对操作符进行如下操作：

• 当遇到操作符时，通过字符变量对字符进行存放；
• 当遇到优先级更高的操作符时，我们则可以将字符变量存放的内容进行更换；
• 当遇到括号时，清除字符变量中存放的内容；

上述的这种改进方案是一种方式，那还有没有其它的方式呢？

在上一篇内容中，我们在实现对前缀表达式和后缀表达式求值时，是通过存放操作数的栈来实现的，在前缀和后缀表达式中，因为操作符和操作数是分离的，并且同一个操作符的两个操作数在栈中也是相邻的，那我们可不可以仿照这个思路来完成表达式的改写呢？

在这个思路中，我们需要做到让操作符和操作数进行分离，那么则需要两个栈来进行操作，一个存放操作符，另一个存放操作数，该算法的具体的思路，如下所示：

1. 从左往右对表达式进行扫描；
2. 通过两个栈来分别存放操作符和操作数，这里我们假设栈1存放操作符，栈2存放操作数；
3. 当遇到操作数时，将操作数存放入栈2；
4. 当遇到界限符和操作符时将界限符和操作符放入栈1；
5. 需要对操作符进行优先级判断时，在入栈前完成判断和相关操作；
6. 进行表达式改写时，将操作符作为操作数压入栈2；

为了验证该思路的可行性，这里我们还是通过表达式"a * (b - c / d) e"为例来说明：

1. 第一次扫描的对象为左操作数a，此时将a压入栈2；
2. 第二次扫描的对象为操作符'*'，此时将'*'压入栈1；
3. 第三次扫描的对象为左界限符，此时将左界限符压入栈1；
4. 第四次扫描的对象为左操作数b，此时将左操作数压入栈2；
5. 第五次扫描的对象为操作符'-'，此时将'-'压入栈1；
6. 第六次扫描的对象为右操作数c，此时将右操作数c压入栈2；
7. 第七次扫描的对象为操作符'/'，通过与栈1的栈顶元素'-'进行比较，'/'的优先级更高，因此将'/'压入栈1，此时栈2的栈顶元素c为'/'的左操作数；
8. 第八次扫描的对象为右操作数d，此时将右操作数d压入栈2；
9. 第九次扫描的对象为右界限符，开始对界限符中的内容进行操作：

• 将栈1的栈顶元素'/'出栈，若表达式改写为后缀则直接压入栈2；若表达式改为前缀则对栈2进行两次出栈后再将操作符'/'压入栈2，之后重新按照c和d的先后顺序将其压回栈2；
• 将栈1的栈顶元素'-'出栈，若表达式改写为后缀则直接压入栈2；若表达式改为前缀则对栈2进行4次出栈后再将操作符'-'压入栈2，之后按照原先的顺序依次将元素压回栈2；
• 将左界限符进行出栈，以此作为操作结束的标志；

1. 第十次扫描的对象为操作符' '，通过与栈1的栈顶元素'*'进行比较，'*'的优先级更高，因此将'*'进行出栈，并将' '进行入栈，之后对'*'进行相应操作：

• 若将表达式改写为后缀则直接压入栈2；若将表达式改为前缀则对栈2进行6次出栈操作后再将操作符'*'压入栈2，之后重新按照原先的顺序依次将元素压回栈2；

1. 第十一次扫描的对象为右操作数e，此时将右操作数压入栈2；
2. 第十二次扫描的对象为字符串终止符''，此时将栈1的栈顶元素' '进行出栈，并对其进行具体的操作：

• 若表达式改写为后缀，则直接压入栈2；若表达式改写为前缀，则将栈2进行8次出栈后将操作符' '压入栈2，之后重新按照原先的顺序依次将元素压回栈2；

通过该步骤，我们可以看到，当我们从左往右扫描时，如果是将表达式改写为后缀，我们会发现通过两个栈来进行操作完全可行，而且在改写的过程不需要对栈2中的元素进行任何的移动，只需要将栈1的栈顶出栈并压入栈2即可。

那其实我们可以大胆的推测一下，如果是改为前缀表达式，我们则需要对原表达式从右往左进行扫描。为什么会因为我们改写的形式不同而导致出现这样的问题呢？

现在有朋友已经反应过来了，没错就是因为中缀表达式的形式决定的，对于中缀表达式而言，从左往右扫描时，肯定是左操作数先入栈，右操作数后入栈。而我们想要将其改写为后缀表达式的话，对于后缀表达式而言操作符是位于右操作数的后面的；从右往左扫描时，肯定是右操作数先入栈，左操作数后入栈。而我们想要将其改写为前缀表达式的话，对于前缀表达式而言，操作符是位于左操作数前面的；

现在我们已经完全理清了整个算法的改写思路，下面我们通过改写后的思路来进行一次中缀转后缀的算法演示：

可以看到，在这一次的演示中，我们并没有对元素的位置进行更改，唯一进行的操作就是将元素从栈1出栈并压入栈2。通过两个栈来实现表达式的修改，比通过1个栈来实现会更加高效。

但是如果是两个栈的话，还是会存在一个问题——对结果进行输出时不太友好。因为栈的特性——只能从栈顶进行入栈和出栈，这就导致我们如果想访问栈底元素，只能将栈顶元素一个一个的出栈。那应该如何完善呢？

从整个演示过程中，我们可以看到，我们并未对栈2中的元素位置进行修改，目前我们需要的也仅仅是能够自由的访问栈底元素。那有没有能够快速访问栈底元素的数据结构呢？有朋友很快就想到了，没错就是顺序表和链表。

对于栈2而言，我们实际上只是做了一个存放数据的功能，并且能够保证这些数据能够像栈一样进行线性的存储，而顺序表和链表作为操作不受限的线性表，那在这里就非常适合。当然还有一种操作受限的线性表也是可以满足咱们的需求的。没错就是队列。因此对表达式进行转换时，我们可以通过使用栈和顺序表、栈和链表或者栈和队列来共同完成。接下来我们就来通过代码实现表达式之间的相互转换；

3.3 算法实现

通过前面的算法设计，我们已经明确了我们的实现思路，如下所示：

1. 对中缀表达式的扫描方向的选择：

• 中缀转后缀：从左往右扫描；
• 中缀转前缀：从右往左扫描

1. 对数据结构的选择：

• 通过栈来存放操作符；
• 通过顺序表/链表/队列来存放操作数；
• PS：在今天的实现中，我通过栈和数组来共同实现；

1. 改写时的算法功能：

• 将扫描到的操作数存放入数组内；
• 将扫描到的操作符和界限符存放入栈内；
• 判断操作符之间的优先级
• 匹配界限符
• 对操作符进行出栈并存入数组内；
• 对界限符进行出栈并舍弃

1. 改写完成后对新表达式的输出

在实现算法之前，我们需要完成准备工作。首先肯定是先创建新的项目，老规矩三个项目文件：Stack.c、Stack.h、test.c；

• Stack.c——顺序栈基本操作的实现

在上一篇内容中我们是通过链栈来实现的表达式求值，那在今天的实现中我们就来通过顺序栈来实现表达式的转换，顺便复习一下顺序栈的基本功能的实现：

【数据结构】C语言实现表达式的转换_C语言_10

可能有朋友看到我这里的形参会觉得有点奇怪，明明判空、判满以及获取栈顶元素的操作都不会修改栈，还有入栈时也不会修改入栈元素，为什么这些操作要传入指针？ 这是因为为了保持函数接口的一致性，因为在正式工作后，正常的一个工程会有好几个人同时完成，为了保证大家在对函数接口进行调用时不会出错，所以会选择将函数接口的参数类型保持一致。

• Stack.h——顺序栈的类型与基本操作的实现声明以及头文件引用

从前面的演示中我们可以看到，在对表达式进行转换时，我们实际上是要判断到字符串结束标志，因此我们在扫描的过程中可以通过字符串的长度来控制扫描的执行，而且我们在扫描的过程中还需要对操作数进行判断，所以我们需要引用头文件<string.h>和<ctype.h>：

【数据结构】C语言实现表达式的转换_表达式转换_11

在头文件中定义的MAXSIZE是相对于栈而言，而我们在实现中是通过数组来操作数进行存放，因此数组的大小最少也是需要MAXSIZE 2的空间大小。 因为对一个表达式来说，操作数的数量比操作符的数量要多1，而对于字符串而言，我们还需要预留一个位置给字符串结束标志，因此存放操作数的数组大小最少也需要MAXSIZE 2的空间大小。

• test.c——用来实现表达式的转换。

【数据结构】C语言实现表达式的转换_栈_12

为了减少文章篇幅，这里对原中缀表达式的获取我就不再赘述，在后面的内容中我们主要来实现的是中缀转后缀的算法。

现在我们已经完成了所有的准备工作了，接下来就可以开始进行算法的实现了。

1. 遍历中缀表达式

这里因为需要从字符串首元素一直遍历到字符串结束标志，因此我们可以通过字符串的长度来作为遍历的判断条件，如下所示：

代码语言：javascript复制

for (int j = 0; j < strlen(s)   1; j  ) 
//strlen求出的是字符串的长度，不包含，因此我们需要加上的长度
{

}

我们现在实现的是中缀转后缀，因此我们是从左往右进行的遍历；

1. 对操作数的判断与操作

在判断扫描的对象是否为操作数时，我们可以通过字符类型函数来完成判断。而对操作数我们需要做的事情很简单，只需要将其放入数组内就行，因此具体实现代码如下所示：

代码语言：javascript复制

if (isalnum(s[j]))//判断字符串的元素类型是否为数字或字母
			ch[i  ] = s[j];//将操作数放入数组

因为我们本次的任务主要是实现表达式形式的转换，对表达式的操作数是数字还是字母并不需要要求的特别苛刻，所以在判断时我们选择的库函数为判断是否为数字和字符的函数——isalnum：

1. 对左边界符的判断与处理

当扫描对象为左边界符时，我们需要将其压入栈内，对应代码如下所示：

代码语言：javascript复制

else if (s[j] == '(')//当扫描对象为左边界符时
			Push(&S, &s[j]);//将其压入栈内

1. 对操作符的判断与处理

当扫描对象为操作符时，会有多种情况，对于不同的情况我们则需要进行不同的处理：

• 当栈为空栈或者栈顶元素为左边界符时，将操作符压入栈中：

代码语言：javascript复制

else if (Empty(&S) || GetTop(&S, &e) == '(')//当栈为空栈或栈顶元素为左界限符时
			Push(&S, &s[j]);//将元素入栈

• 当栈非空且栈顶元素为操作符时，我们需要执行操作符优先级的判断，并根据优先级执行不同的操作，这里我们直接将对操作符优先级判断这一过程封装成一个函数，如下所示：

代码语言：javascript复制

//操作符优先级判断
int Priority_Judgment(char ch1, char ch2) {
	if (ch1 - ch2 == 0 || ch1 == ' ' && ch2 == '-' || ch1 == '-' && ch2 == ' ' || ch1 == '*' && ch2 == '/' || ch1 == '/' && ch2 == '*')//优先级相同
		return 0;//返回0
	else if (ch1 == ' ' && ch2 == '*' || ch1 == ' ' && ch2 == '/' || ch1 == '-' && ch2 == '*' || ch1 == '-' && ch2 == '/')//扫描元素优先级更高
		return 1;//返回1
	else//栈顶元素优先级更高
		return -1;//返回-1
}

在完成了优先级的判定后，我们就可以根据返回值来进行对应的操作了，如下所示：

代码语言：javascript复制

else if (!Empty(&S) && GetTop(&S, &e) != '(')
		{
			switch (Priority_Judgment(GetTop(&S, &e), s[j])) {
			case -1://当栈顶元素优先级更高
			case 0://优先级相同时
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将栈顶元素放入数组
				Push(&S, &s[j]);//将扫描元素入栈
				break;
			case 1://当扫描元素优先级更高
				Push(&S, &s[j]);//将扫描元素入栈
				break;
			}
		}

对操作符的操作无非就两种结果：

1. 将扫描元素入栈
2. 先将栈顶元素出栈并放入数组后将扫描元素入栈。

因此，我们可以通过Switch语句来对返回值进行判断：

• 当返回值为-1或者0时，也就表示此时我们需要优先对栈顶元素进行操作，因此执行的内容都为先出栈栈顶元素并放入数组，入栈扫描元素；
• 当返回值为1时我们才只对扫描元素进行入栈操作；

1. 对右界限符的处理

当遇到右界限符时，我们需要将左界限符之后的元素全部出栈并放入数组内，因此我们可以通过循环来实现连续出栈，如下所示：

代码语言：javascript复制

else if (s[j] == ')') {
			while (GetTop(&S, &e) != '(') {
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将元素存入数组
			}
			Pop(&S, &e);//将左界限符出栈并舍弃
		}

1. 对字符串结束标志的处理

当遇到字符串结束标志时，我们只需要将栈内的全部元素依次出栈并放入数组即可，如下所示：

代码语言：javascript复制

else if (s[j] == '') {
			while (!Empty(&S)) {
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将元素存入数组
			}
		}

1. 对其他字符的处理

为了提高代码的健壮性，当字符串中的元素既不是运算符也不是字母或数字时，不管此时栈的状态如何，我们需要对用户进行提示并结束程序：

代码语言：javascript复制

else {
			printf("%c无法被识别n", s[j]);
			break;
		}

现在我们就完成了算法的整个代码，下面我们就来对代码进行测试；

3.4 算法测试

在测试前我们先看一下完整的代码，如下所示：

代码语言：javascript复制

//中缀表达式转后缀表达式
char* Infix_to_Suffix(char* s) {
	SqStack S;//创建顺序栈
	Init(&S);//对栈进行初始化
	Elemtype e = 0;//进行入栈和出栈的元素
	char ch[MAXSIZE   2] = { 0 };//存放操作数的数组
	int i = 0;//数组下标
	for (int j = 0; j < strlen(s)   1; j  ) //strlen求出的是字符串的长度，不包含，因此我们需要加上的长度
	{
		if (isalnum(s[j]))//判断字符串的元素类型是否为数字或字母
			ch[i  ] = s[j];//将操作数放入数组
		else if (s[j] == '(')//当扫描对象为左边界符时
			Push(&S, &s[j]);//将其压入栈内
		else if (Empty(&S) || GetTop(&S, &e) == '(')//当栈为空栈或栈顶元素为左界限符时
			Push(&S, &s[j]);//将元素入栈
		else if (s[j] == '') {
			while (!Empty(&S)) {
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将元素存入数组
			}
		}
		else if (s[j] == ')') {
			while (GetTop(&S, &e) != '(') {
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将元素存入数组
			}
			Pop(&S, &e);//将左界限符出栈并舍弃
		}
		else if (!Empty(&S) && GetTop(&S, &e) != '(')
		{
			switch (Priority_Judgment(GetTop(&S, &e), s[j])) {
			case -1://当栈顶元素优先级更高
			case 0://优先级相同时
				Pop(&S, &e);//将栈顶元素出栈
				ch[i  ] = e;//将栈顶元素放入数组
				Push(&S, &s[j]);//将扫描元素入栈
				break;
			case 1://当扫描元素优先级更高
				Push(&S, &s[j]);//将扫描元素入栈
				break;
			}
		}
		else {
			printf("%c无法被识别n", s[j]);
			break;
		}
	}
	return ch;
}

细心的朋友会发现，在完整的代码中我们是优先对单一的特殊情况进行判定的，比如左右界限符的判定，字符串结束标志的判定，然后才是对栈为非空切栈顶元素不是左界限符情况的判定。有朋友思考过为什么需要这样吗？

我相信有朋友已经明白了，没错就是因为当扫描元素为左右界限符与字符串结束标志时，也可能满足栈非空且不是栈顶元素不是左界限符的情况，如果将该情况提前，则会影响对这些情况的判定，因此需要置后。

代码已经没问题了，接下来我们就来测试一下，测试的内容为："a b"、"a b * c"、"a * b c"、"a * (b - c / d) e"，测试结果如下所示：

【数据结构】C语言实现表达式的转换_栈_13

可以看到，我们现在就很好的实现了中缀转后缀的表达式转换。对于中缀转前缀的代码的实现，有兴趣的朋友可以按照中缀转后缀的思路进行代码的编写，只不过这里我需要提醒一下大家，扫描的方向别弄错咯！

结语

现在我们就介绍完了通过代码实现表达式转换的全部内容。在今天的内容中我们详细探讨了实现表达式转换的具体过程，并最终确定了表达式转换实现的具体思路：

1. 对中缀表达式的扫描方向的选择：

• 中缀转后缀：从左往右扫描；
• 中缀转前缀：从右往左扫描

1. 对数据结构的选择：

• 通过栈来存放操作符；
• 通过顺序表/链表/队列来存放操作数；

1. 改写时的算法功能：

• 将扫描到的操作数存放入数组内；
• 将扫描到的操作符和界限符存放入栈内；
• 判断操作符之间的优先级
• 匹配界限符
• 对操作符进行出栈并存入数组内；
• 对界限符进行出栈并舍弃

1. 改写完成后对新表达式的输出

在顺着该思路编写完代码后，我们还通过部分用例对代码进行了测试，从测试结果中我们可以看到，通过该思路编写的代码能够很好的实现中缀转后缀。感兴趣的朋友如果想提高自己的动手能力，可以自己尝试着实现一下中缀转前缀。如果在实现的过程中有遇到问题，可以在文章下方留言或者私信博主哦！博主看到信息后会耐心的回复各位。

通过这段时间的博客内容，相信大家对栈的应用有了更加深刻的认知。除了这段时间我们介绍的括号问题和表达式求值外，函数递归也是栈的一种典型应用，关于递归与函数栈帧的创建与销毁，在前面的文章中我有进行详细的介绍，这里就不多加赘述了。

其实除了栈能运用在这些实际问题中，队列同样也能，比如层次遍历问题、计算机系统中解决主机与外部设备之间速度不匹配的问题以及由多用户引起的资源竞争问题。感兴趣的朋友大家可以自己下去后简单了解一下，当然随着学习的深入，对于这些问题我们都会进行进一步的介绍，所以大家目前对这些内容了解即可。

今天的内容到这里就全部结束了，希望今天的内容能帮助大家进一步强化表达式之间的相互转化的知识点，并能够提高大家的编程能力。在下一篇内容中我们将会探讨特殊矩阵以及相关操作，大家记得关注哦！如果各位朋友喜欢博主的内容，还麻烦点赞、收藏 评论，当然也可以将博主的文章分享给身边需要的朋友。最后感谢各位的支持，咱们下一篇再见！！！

数据结构 对象 数组 算法 字符串

0 人点赞