【题解】NowCoder AB5 点击消除

题目来源：牛客

AB5 点击消除

题目描述：

牛牛拿到了一个字符串。

他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。

但相同而不相邻、不相同的相邻字母都是不可以被消除的。

牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？

输入描述：

一个字符串，仅由小写字母组成。（字符串长度不大于300000）

输出描述：

一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。

示例1

输入： abbc

输出： ac

示例2

输入： abba

输出： 0

示例3

输入： bbbbb

输出： b

解析

本题跟括号匹配题简直一个模子里刻出来的，很容易联想到栈。没错，这题就是使用栈的特性来解决问题，两两相同的元素进行消除。在元素入栈的时候跟栈顶元素比较一下，相同的话说明能匹配上，则该元素不入栈，并且弹出栈顶元素，不相同就正常入栈。

不过注意的是，最后将栈内所有元素提取的时候，是跟答案相反的，所以没必要一定使用栈，用其他的模拟栈即可，例如 vector 或 string 。

代码实现

#include<iostream>
// 使用string需要导入此头文件
#include<string>
using namespace std;
int main()
{
    string input;
    string ans;
    cin >> input;
    // 遍历输入的字符串
    for (auto e : input)
    {
      // 只有当我们的答案字符串非空，并且与下一个值匹配上了才能进行’消除‘
        if (ans.size() && e == ans.back())
        {
          // 弹出消除的字符串
            ans.pop_back();
        }
        // 没匹配上就入栈
        else
        {
            ans.push_back(e);
        }
    }
    // 注意，字符串为空时题目要求返回 “0”
    cout << (ans.size() ? ans : "0");
    return 0;
}