1.预备知识：

栈，可以用来存放数据，好比是一个有底的容器，先放进去的数据存在于栈底，最后放进去的数据放在栈顶，取数据时先取出栈顶的数据，也就是所谓的“后进先出”“先进后出”。

(资料图片仅供参考)

我们也可以用数组模拟栈，实现一些操作，这样有利于我们更好的理解栈的操作原理（虽然我们也可以直接调用栈容器）。

2.来个例题

3.解题代码：

以上使我们使用数组来模拟栈调用。下面，我们调用栈来实现表达式的计算。

2.调用栈来实现表达式计算

1.调用栈需要的头文件

2.相关的操作

3.例题（来源于www.acwing.com  T3302)

4.解题思路

首先，我们要弄清楚运算的表达式，这里输入的中缀表达式。

比如，a+b,这就是一个中缀表达式，那么既然有中缀表达式，那就有后缀表达式，将a+b转换为后缀表达式就是ab+。再举个栗子，（a+b)*((c+d)/e)是中缀表达式，转换为后缀表达式就是ab+cd+e/ *。这样看起来非常费解，好好的中缀表达式，为什么非得改成后缀表达式呢，因为对于人来说，中缀表达式非常好理解，但是对于计算机来说，中缀表达式就非常难理解了。但是计算机可以无脑的计算后缀表达式。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。

我们来看一下，栈首先存入a，再存入b，这时接收到了+指令，计算出a+b的值，并清空a，b，把计算之后的和sum1存入栈中。这时，计算机接着接收，将c存入栈中，再将d存入栈中，这之后又接收到+指令，由于从栈中取出元素时，是后进先出，这时，先取出d，再取出c，两个元素均取出来之后，执行加法，再将和sum2存入栈中。这时栈中有两个元素，栈底sum1，栈顶sum2。继续接收，接收到e，存入栈中。之后接收到/指令。取出e，取出sum2，执行sum2/e的操作，并将结果ans1，存入栈中。此时，栈中一共两个元素，栈底sum1，栈顶ans1，接着接收，接收到*指令，取出这两个元素，执行 *操作，最后结果ans2存入栈中。

这就是后缀表达式的优势。不需要过多的判断条件，直接交给计算机执行就可以了。

我们今天要处理的是中缀表达式，对于a+b*c+d/e+(f/g+h) *(i *k-l)-m来说的话，我们通过模拟计算机运算过程，来理清并判断优先级，以及何时计算一个子表达式（比如b *c就是一个子表达式，a+b就是一个错误的子表达式，不可以计算）。我们从左向右进行（这里我们建立两个不同的栈容器，一个int用以存放数字，一个char容器，用以存放操作符），a入栈< int>，‘+’入栈< char>,b入栈，这时，我们还不可以计算，我们不知道下一运算符的优先级。于是，我们接着录入数据， ‘ * ’ 入栈，这时我们发现 + 小于 *优先级，这时我们无法执行a+b，所以我们接着读入 * 右边的操作数，c入栈，这时我们可能会想b * c总能执行了吧！别慌，一个操作可不可以执行，不取决于它本身，而取决于它和它后边一位操作符的优先级关系，如果当前运算符优先级>或=下一个运算符，那么当前表达式就是可以执行的。于是b * c能否执行取决于后一位运算符，读到 + 时（我们先不让这个+入栈，因为入栈之后，栈顶元素就不是 * 了）发现 * > +这时我们把b*c的结果运算出来，存入int栈中，假如发现 *  后面不是+，而是^（乘方运算符）,这时，b*c就不可以执行了。执行完b * c=mul1之后,我们把让b,c出栈，把mul1入栈。我们发现char栈顶元素是最开始的+ ，+的优先级等于+，所以表达式还可以接着执行，所以我们接着执行a+mul1=sum1。之后，我们让a,mul1出栈，让sum1 入栈。这时，int栈只有一个sum1，char栈是空的。所以我们让+入栈。

读到这里，有的朋友可能有疑问，为什么我非得执行完a+mul1 再让+ 入栈，不可以让+先入栈吗？我们这样想，假如我先让+入栈，这时候我们还需要读入+右边的操作数d。假设，我们的表达式就是a+b*c+d，这时候，我们已经录入完毕。所以我们开始看char栈，这时候+先弹出，d和mul1也弹出，我们执行d+mul1=sum0，这时候我们char栈再弹出最开始的+，sum0和a也弹出，我们执行a+sum0操作。这看似没有什么问题，但是@！，你想，假如第一个+是- ，第二个+ 也是 - 呢，我会先执行mul1-d=sum0,再执行a-sum0，这就把运算顺序搞错了。所以说，我们同一级运算一定要从左向右运算，能算的时候一定要算完，不然最后堆到一起，从char向外弹出的时候，可能会违反同一优先级从左向右的运算顺序。把所有的都录入之后，char栈中可能还会有剩余的没有进行计算的运算符，但是这时候，一定是高优先级的在栈顶，低优先级的在栈底。所以这时候，在从char栈中弹出运算符的运算就相当于表达式从右向左进行，但是这就是对的，优先级决定的。

对于有括号的情况，我们只需要正常接收‘（’  左括号（不用管，直接存入char栈就行），接着进行上述的运算，当接受到‘）’右括号时，一部分运算符已经计算完了，这时，将左括号和有括号之间的还没有进行运算符全部弹出执行即可。

经过上面的讨论，我们现在已经解决了核心问题。

5.解题代码：

如有错误，还望指正。