题目

题目链接

题解

实现题。

---

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

---

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

整体思路：
先通过栈的思想实现括号匹配，将每一对括号的位置信息存下来（包括左括号和右括号所在索引），按层次关系（先看下面有层次关系的解释）对每对括号进行排序。按顺序遍历括号决定是否可以删除这对括号，对于遍历到的每一对括号，我们都去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<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII; // right), left(

stack<int> sta;
vector<PII> v;
string s;

map<char, int> signlevel;


bool check(int a, int b) {
	stack<int> tmp; // 若tmp栈中存在数，说明现在还处于内部括号的范围中，不能统计符号 
	vector<char> sign;
	char leftsign = s[a-1], rightsign = s[b+1];
	int mnlv = 3; // 含义为括号内符号优先级最低是多少 
	int rslv = signlevel[rightsign]; // 右侧符号的优先级 
	
	for(int i = a+1;i <= b-1;i ++) {
		if(s[i] == ' ') continue;
		if(tmp.empty()) { // 空了 
			if(s[i] == '(') tmp.push(1); // 若遍历到左括号，则入栈 
			else if(!isalpha(s[i])) sign.push_back(s[i]); // 不是字母，就说明是外层括号内的有效符号了 
		} else if(s[i] == ')') tmp.pop(); // 内层右括号出栈 
	}
	
	for(int i = 0;i < sign.size();i ++) mnlv = min(mnlv, signlevel[sign[i]]); 
	
	if(mnlv < rslv) return false;
	if(((leftsign == '-' || leftsign == '*') && mnlv != 2) || leftsign == '/') return false;
	return true;
}


int main()
{
	// 每个符号的优先级 
	signlevel[' '] = 0; signlevel['('] = 0; signlevel[')'] = 0;
	signlevel['+'] = 1; signlevel['-'] = 1; signlevel['*'] = 2; signlevel['/'] = 2; 
	
	while(cin>>s) {
		v.clear(); 
		int n = s.size();
		s = ' '+s+' '; // 开头和结尾加空格，就是防止越界的作用 
		for(int i = 1;i <= n;i ++) 
		if(s[i] == '(') sta.push(i); // 左括号入栈 
		else if(s[i] == ')') v.push_back(PII(i, sta.top())), sta.pop(); // 遇到右括号，左括号出栈，记录括号配对信息 
		sort(v.begin(), v.end()); // 排序 
		
//		for(int i = 0;i < v.size();i ++) cout << v[i].second << ' ' << v[i].first << endl;
		
		for(int i = 0;i < v.size();i ++) {
			int a = v[i].second, b = v[i].first;
			if(check(a, b)) s[a] = s[b] = ' '; // 去括号 
		}
		
		for(int i = 1;i <= n;i ++) if(s[i] != ' ') cout << s[i]; puts("");
	}
}