文章

74

粉丝

0

获赞

98

访问

8.9k

头像
括号匹配问题 题解(stack容器):
P1296 北京大学机试题
发布于2025年8月11日 18:04
阅读数 129

#include<bits/stdc++.h>
using namespace std;

void test(string s){
	stack<char> st;
	int len = s.size();
	char flag[105] = {0};
	
	// 正向遍历字符串
	for(int i = 0; i < len; i ++){
		char now = s[i];
		if(now == '(') st.push(now);
		else if(now == ')'){
			if(!st.empty() && st.top() == '(') st.pop();
			else flag[i] = '?';
		}
	}
	
	while(!st.empty()) st.pop();
	
	// 反向遍历字符串
	for(int i = len - 1; i >= 0; i --){
		char now = s[i];
		if(now == ')') st.push(now);
		else if(now == '('){
			if(!st.empty() && st.top() == ')') st.pop();
			else flag[i] = '$';
		}
	}
		
	for(int i = 0; i < len; i ++) cout << (flag[i] == 0 ? ' ' : flag[i]);
	
	cout << '\n';
}

int main(){
	
	string s;
	while(cin >> s){
		cout << s << '\n';
		test(s);
	}
	
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发