文章

8

粉丝

14

获赞

7

访问

635

头像
括号匹配问题 题解:
P1296 北京大学机试题
发布于2025年1月14日 16:21
阅读数 77

#include<bits/stdc++.h>

using namespace std;

int main(){
    string s;
    while(cin>>s){
        stack<int> st;
        vector<char> res(s.size());
        for(int i = 0;i <s.size();i ++){
            if(isalpha(s[i])) res[i] = ' ';
            else if(s[i] == '(') {res[i] = ' ';st.push(i);}
            else if(s[i] == ')'){
                if(!st.empty()) {res[i] = ' ';st.pop();}
                else res[i] = '?';
            }
        }
        while(!st.empty()){
            res[st.top()] = '$';
            st.pop();
        }
        cout<<s<<endl;
        for(int i = 0;i < s.size();i ++)
            cout<<res[i];
        cout<<endl;
    }
    return 0;
}

由于表达式只含一种括号,故栈只存放左括号的索引即可。遍历完字符串,当前字符为字母,则res插入空格。为左括号,暂时插入空格(暂时认为其能够正确匹配)。为右括号,则当前栈不为空,则栈顶与右括号匹配,出栈,同时设置res为空格;若当前栈为空,说明该右括号无法匹配,res设置为‘?’。

遍历完字符串后,栈中剩余的元素,均是无法正确匹配的左括号的索引,根据保存的索引,依次修改res即可。

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发