蓝桥杯算法训练VIP-删除多余括号

题目

题目链接

题解

实现题。

这个题比较考查代码实现能力和逻辑思维能力，如果看下面的题解云里雾里的同学可以放弃本题。

一看到括号就知道必然会用到栈。

整体思路： 先通过栈的思想实现括号匹配，将每一对括号的位置信息存下来（包括左括号和右括号所在索引），按层次关系（先看下面有层次关系的解释）对每对括号进行排序。按顺序遍历括号决定是否可以删除这对括号，对于遍历到的每一对括号，我们都去check()一下，若满足则可以删除，若不满足则不能删除。最后进行输出。

层次关系：就是某对括号内部包含着另一对括号，就说明存在层次关系，对于存在层次关系的括号，我们将内层的排在前面，外层的排在后面，对于那些不存在层次关系的括号，排序关系无所谓。如下图： 绿括号和红括号就具有层次关系，而紫括号与其他俩均不具有层次关系，因此排序可以为红 绿 紫或紫 红 绿，但不可以是红 紫 绿。

整体思路只是概述，下面将分开讲一下每一步的实现

栈实现括号匹配： 这部分大家应该比较熟悉，利用栈的思想，我们顺序遍历，遇到左括号就入栈，遇到右括号就将栈顶的左括号出栈，说明二者匹配，遍历完成就是先了括号匹配。（只入左括号，遇到右括号是判断是否进行出栈，不入右括号） 本题利用这种方式将左右括号的位置信息打包成一个pair加入vector中，之所以要将右括号的位置作为pair的first，将左括号的位置作为pair的second，是因为我们要实现层次关系排序就要通过两种比较的方式来实现：①左括号位置大的排在前面，②右括号位置小的排在前面。（这两种方式确实可以保证按照层次关系排序，你可以举几个例子试试）这里我们选择第二种，是因为对pair进行sort时默认以first作为第一比较对象，first小的在前，first一样再比较second，second小的在前。我们将右括号的位置信息放在first中就可以不用重写sort函数实现按层次关系排序。

接着我们只需要按层次关系遍历每对括号，调用check()函数判断是否可以删除，这里我们规定删除括号就是将括号改为空格。

check() 函数： 这部分是核心，即判断是否去括号。 能否去括号，由括号内外的符号决定。

如果你要去思考哪些情况可以去括号哪些情况不可以去括号，那样只会弄得自己越来越糊涂，因此，我们只找不可以去括号的情况，此时返回false，对于剩下的情况，也就是没能返回false的情况，直接返回true。

为什么要考虑不能去括号的情况，而不是考虑能去括号的情况呢？ 因为不去括号的情况好考虑。一对括号，你需要判断这对括号外面左侧相邻的符号与括号内符号的关系，还要判断这对括号外面右侧相邻的符号与括号内符号的关系。如果你要找可以去括号的情况，则需要找既满足“左侧相邻符号与括号内符号的关系“又满足”右侧相邻符号与括号内符号的关系”的情况。而你要找不满足的情况，只需要分开判断，只要左侧和右侧其中一个不满足就可以返回，而不用同时保证两边才能返回，明显要简单多了。

经过思考之后可以总结出如下规律：

1. 如果右侧符号的优先级大于括号内符号的最小优先级，则返回假；
2. 如果左侧符号为减号或者乘号，这两种情况下若括号内的符号不是乘号或除号，则返回假；
3. 如果左侧符号为除号，则返回假；
4. 其他情况均为真。

应当注意，若外层括号（层次关系中的外层括号）中存在内层括号未被删除，当判断是否删除外层括号时，应当忽略全部内层括号及其内部符号，即将内层括号当成一个字母来看待。例如下图： 红括号先被判断是否删除，很显然不被删除。再判断绿括号，绿括号内存在两个符号红括号内的加号和红括号外的乘号，但是我们要将整个红括号看成新的字母d，即(d*f)-(1/j)，再判断符号关系。同样的，若存在多个内括号也是要将未被删除的括号看成一个字母，再统计符号。

规律的思考过程： 分别考虑左侧符号和右侧符号。

右侧： ( ) +：总可以去括号 ( ) -：总可以去括号 ( ) *：括号内存在+或-时不可去括号 ( ) /：括号内存在+或-时不可去括号 左侧： + ( )：总可以去括号 - ( )：括号内存在+或-时不可去括号 * ( )：括号内存在+或-时不可去括号 / ( )：总不可去括

其实还有一点小细节，就是要将空格、左括号和右括号的优先级设置为最低。为的是保证正确（等于没说），至于详细原因大家自己思考吧。

代码

#include
using namespace std;
typedef pair PII; // right), left(

stack sta;
vector v;
string s;

map signlevel;


bool check(int a, int b) {
	stack tmp; // 若tmp栈中存在数，说明现在还处于内部括号的范围中，不能统计符号 
	vector sign;
	char leftsign = s[a-1], rightsign = s[b+1];
	int mnlv = 3; // 含义为括号内符号优先级最低是多少 
	int rslv = signlevel[rightsign]; // 右侧符号的优先级 
	
	for(int i = a+1;i