【OJ】相同字母相遇相消（stack的使用例子）

电玩女神 2024-04-19 13:29 44阅读 0赞

## 1437: 无题 ##

### 题目描述 ###

tc在玩一个很无聊的游戏：每一次电脑都会给一个长度不超过10^5的字符串，tc每次都从第一个字符开始，  
如果找到两个相邻相一样的字符，就会把它们删除掉，然后再重新从第一个字符开始，直到不能找到这样的字符，  
这样tc就得胜了。 你能帮助tc吗？

### 输入 ###

多组数据，每组一行字符。

### 输出 ###

输出最后的字符串,占一行。

### 样例输入 ###

`abccbad`

### 样例输出 ###

`d`

### 解题代码 ###

#include <iostream>
    #include <stack>
    using namespace std;
    
    int main()
    { 
        int i;
        char str[100002];
        while(cin>>str)
        { 
            stack<char> data;
            stack<char> result;
            data.push(str[0]);
            for(i=1; str[i]!='\0'; i++)
            { 
            	// 如果已经消没了
                if(data.empty()==true)
                { 
                    data.push(str[i]);
                    continue;
                }
                char ch = data.top();		
                if(ch == str[i])
                { 
    	            // 如果相等，消
                    data.pop();
                }
                else
                { 
                	// 写入
                    data.push(str[i]);
                }
            }
    		
    		// 逆序
            while(data.empty()==false)
            { 
                char r = data.top();
                data.pop();
                result.push(r);
            }
    		
    		// 输出
            while(result.empty()==false)
            { 
                char r = result.top();
                cout<<r;
                result.pop();
            }
    
            cout<<endl;
        }
        return 0;
    }

### 补充 ###

如果不使用现成的stack类，怎么实现呢？  
思路是一样的，使用一个字符串就可以模拟stack，代码如下：(已经提交验证过了)

#include <iostream>
    using namespace std;
    char str[100002];
    char myStack[100002];
    
    int main()
    { 
        int i;
        while(cin>>str)
        { 
            int stackTop=-1;
            for(i=0; str[i]!='\0'; i++)
            { 
                if(stackTop==-1)
                { 
                    // 入栈
                    myStack[++stackTop] = str[i];
                    continue;
                }
                // 出栈
                if(myStack[stackTop]==str[i])
                    stackTop--;
    			// 入栈
                else
                    myStack[++stackTop] = str[i];
            }
            for(i=0; i<=stackTop; i++)
            { 
                cout<<myStack[i];
            }
            cout<<endl;
        }
        return 0;
    }

### 总结 ###

善于选择容器，比如这个题可以选择stack，因为都是对最后一个字母进行操作，即stack的top。

> Smileyan  
> 2019年9月18日 20:46