文章

27

粉丝

0

获赞

80

访问

2.4k

头像
括号匹配问题 题解:栈里同时存括号和下标
P1296 北京大学机试题
发布于2026年2月24日 16:46
阅读数 48

#include <iostream>
#include <stack>
using namespace std;
int main(){
	string str;
  while(cin>>str){
    stack<pair<char,int>> sta;
    string res(str.size(),' ');
    //判断右括号能不能被匹配
    for(size_t i=0;i<str.size();i++){
      if(str[i]=='(') sta.push(pair<char,int>(str[i],i));//左括号入栈,字母不管
      if(str[i]==')'){
        //如果当前未空,弹出左括号
        if(!sta.empty()) sta.pop();
        else res[i]='?';//空了说明匹配不到左括号
      }
    }
    //剩下这些左括号直接标记$即可
    while(!sta.empty()){
      int idx=sta.top().second;
      res[idx]='$';
      sta.pop();
    }
    cout<<str<<"\n"<<res<<"\n";
  }
	return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发