#21293. 消消乐

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jvan

题目描述

现在给一个字符串,你要做的就是当这个字符串中存在两个挨着的字符是相同的时就将这两个字符消除。需要注意的是,当把这两个字符消除后,可能又产生一对新的挨着的字符是相同的。比如,初始的字符串是abcddc,dd是两个挨着的相同的字符,当把"dd"消除后,得到的字符串是abcc,这时cc又是两个挨着的相同的字符,所以又应该把cc消除。重复以上操作直到剩下的串中不存在两个挨着的字符是相同的为止,输出最终剩下的串。另外需要注意的是,多对相同字符的消除顺序是不会对答案产生影响的,可以证明最后他们都会达到唯一的结果,比如,对于初始字符串adccdeed,无论是adccdeed->addeed->aeed->ad还是adccdeed->adccdd->adcc->ad,最终的输出结果都是ad。

输入格式

输入的第一行,包含一个字符串,为初始字符串,所有的字符均为小写字母。

输出格式

输出为一行,包含一个字符串,为执行多次消除操作后最终剩下的字符串。

样例

adccdeed

ad

数据范围与提示

对于100%的数据,字符串的长度在1到200000之间。 【分析】本题也可通过栈结构来解决,因为在list的使用中通过在头或尾的插入,也可以实现队和栈的功能。利用链表,每次将数据与表尾的值进行判断是否相等,相等则将表尾元素删除,不相等则从表尾插入。