OJ2-3_游戏_括号匹配
思路
夹带一点私货，这个问题是小编觉得非常有意思的一个问题。小编了解到这个题大家都会用两个栈解决，但其实只要作一个转换，就可以一个栈都不用。
两个栈的解法
用两个栈一个装A球一个装C球，若遇到A/C球则把它们压入相应的栈中，若遇到B球则优先弹出A球进行匹配，若A栈为空则弹出C球进行匹配，若C栈也为空则这是一个不合规序列，可以直接结束程序。
若对所有球都执行完操作还是没有结束程序，则将所有在栈里的A球和C球排列出来，若还剩n个球，则将后n个C球变成B球（若C球个数小于n直接判断为不合规），其他C球拿掉，再进行匹配，若匹配成功则合规，否则不合规。
不用栈的解法
私货来了！
先考虑这样一个问题：如果这个题没有C球，那么是不是就变得好解了？
只需要从头扫一遍，在任意位置前面的A球都不少于B球的数目，且AB球数目相等就行。
那么我们能不能把C球按照一种规则转化成A球或者B球或者拿掉，然后再进行判断呢？
可以的！
概念：转化
为了更好的说明，先引入一个概念——转化。
比如我们有序列AACCC，则其变为AABB就是一种转化。
一个序列合规当且仅当它的一种转化合规。
接下来我们引入两个引理：
引理1
若一个序列的一种转化
……C……C……变成……B……A……
合规，则其另一种转化
……C……C……变成……A……B……
合规。
证明：
若……B……A……合规，则一定存在A‘与B配对，B’与A配对，如下
……A‘……B……A……B'……
那么另一种转化
……A‘……A……B……B'……
也可以如此匹配
引理2
若一个序列的一种转化
……C……C……变成……拿掉……拿掉……
合规，则其另一种转化
……C……C……变成……A……B……
合规。
证明
若……拿掉……拿掉……合规，则我们可以让两个C相互匹配，如下
……A……B……
定理
一个序列合规当且仅当其按照这样一种转化完仍合规：将前一半C球转化成A球，后一半转化成B球，若C球总共为奇数个则拿掉最中间的一个C球。
充分性：
易得
必要性：
若这个序列合规，则其一定存在一个转化合规
将这个转化的所有拿掉的C球按照引理2产生A,B球，直到最后只剩1个或者不剩C球了
再将所有转化得到的A,B球应用引理1交换次序，直到所有转化得到的A球在所有转化得到的B球前面
由此这个操作完之后的序列也合规
所以我们只需要应用此定理将其进行转化就可以转化为只有A，B球的问题。
伪代码
i=0
j=n-1
//应用定理转化C球
while True:
keep i++ until find array[i]=C or i=n
keep j-- until find array[j]=C or j=-1
array[i]=A
array[j]=C
if i==j:
pick out array[i]
break
if i==n:
break
//计算只含有A,B球的序列
judge array with only A and B