1.3：栈在各类表达式中的应用

一：书上原题1.3.9

编写一段程序，从标准输入得到一个缺少左括号的表达式并打印出补全括号之后的中序表达式，例如，给定输入： 1+2)3-4) 5-6))) 你的程序应该输出： ((1+2) ((3-4) (5-6)))

这道题跟前面介绍的很类似我们还是用两个栈分三种情况来处理：

遇到数，入数栈
遇到运算符，入符栈
遇到右括号，弹出两个数（注意顺序），一个符，拼成字符串（加上括号），入数栈``` string left(vector &a) { stack vals, ops; for (int i = 0; i < a.size(); ++i) {
```
 if (a[i] != ")")
 {
     if (a[i] == "+" || a[i] == "-" || a[i] == "*" || a[i] == "/")
     //运算符
     {
         ops.push(a[i]);
     }
     else //数值
     {
         vals.push(a[i]);
     }
 }
 else //右括号
 {
     string first = vals.top();
     vals.pop();
     string exp = "(" + vals.top() + ops.top();        
     ops.pop();
     exp += first + ")";
     vals.pop();
     vals.push(exp);
 }        
```
} return vals.top(); } ```我们来考虑下，为啥栈在这种地方这么好用呢如果我们直接做这个题，给 1+2)3-4) 5-6))) 添加左括号，那我们的做法是，从左到右看过去，1+2不变，然后右括号，这时候我们在最左边添加左括号(1+2)，然后看到*3-4，再看到右括号，这时候要注意了，我们有两种选择：
((1+2)*3-4)
(1+2)*(3-4) 很明显按照每个子表达式都要有括号的原则我们应该选第二种，那么在程序中怎么表达呢？是不是就是靠近右括号最近的操作数，那我们就可以通过栈来实现，后入先出，后面进来更靠近当前要处理的括号，这个准则就注定了我们在处理类似问题的时候，栈是优选

以前序表达式 +/ 23-213-41 为例，将其转换为中序表达式：还是老方法，准备一个栈就够了，由于前序表达式的特殊性，我们从右到左扫描：

以后序表达式 ab+cde+** 为例，将其转换为中序表达式：准备一个栈，我们从左到右扫描：

这个就稍微难一点了，毕竟是反推，但是原理还是类似的，首先确定优先级( 大于 */ 大于+-我们准备一个栈：

遇到数，直接输出
遇到运算符，在入栈之前先要和栈顶元素比较：
1. 输出大于等于当前运算符优先级的运算符（左括号例外）
2. 遇到左括号直接入栈（因为它的优先级最高啊），遇到右括号就一直弹出，直到遇到左括号为止

我们来找个例子试试： a+bc+(d e+f)*g 我们从左到右扫描：

a，输出，栈为空，输出为a
+，此时栈为空，肯定没有优先级大于等于它的，入栈，栈为+，输出为a
b，输出，栈为+，输出为ab
，栈顶元素+优先级小于它，不输出，直接入栈，栈为 +（这么写表示 *是栈顶），输出为ab
c，输出，栈为*+，输出为abc
+，栈顶元素 的优先级大于它，一直输出到+，然后把这个+入栈，此时栈为+，输出为abc+
(，入栈，栈为(+，输出为abc*+
d，输出，栈为(+，输出为abc*+d
，优先级小于(，入栈，栈为 (，输出为 abc *+d
e，输出
+，*出栈，+入栈
f输出
)，一直出栈到左括号（括号不显示），此时栈为+，输出为abc+def+
, 入栈，栈为+，输出为abc+def+
g，输出，再出栈所有的，输出为abc+def+g*+ 这样一来就清楚了，我们的前半部分分析可以用来写代码，因为逻辑已经理清楚了，后半部分是单步运行的调试，你可以试试