字符串处理 - 栈

问题描述

有一个字符串 X，该串包含偶数个字符，一半是 S 字符，一半是 T 字符
可以对该字符串执行10^10000次操作：如果存在 ST 是该串的子串，则删除掉最左边的 ST。
即 TSTTSS⇒TTSS、SSSTTT⇒SSTT⇒ST⇒空

Input

(2 ≦ |X| ≦ 200,000)

Output

输出最终串的长度

Sample

Input: 
TSTTSS

Output: 
4

Limitation

Time limit		1000 ms
Memory limit	262144 kb

解题思路

从头开始扫字符串：
若栈空，则该位置字符入栈；
若栈顶为 ‘S’ 且 该字符为 ‘T’，则弹栈，否则该字符入栈。

最后返回栈大小即可。

源代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int solve(string s) {
	stack<char> st;
	for (int i = 0; i != s.length(); i++) {
		if (st.empty()) {
			st.push(s[i]);
			continue;
		}

		char temp = st.top();
		if (temp == 'S' && s[i] == 'T')
			st.pop();
		else
			st.push(s[i]);
	}
	return st.size();
}

int main() {
	string s;
	while (!(cin >> s).eof()) {
		int ans = solve(s);
		cout << ans << endl;
	}

	return 0;
}