题解 | #BD8 完成括号匹配#(栈)

解题思路

1.使用栈存储未匹配的左右括号,当当前括号为右括号,栈顶元素为左括号时,两括号匹配,将栈顶元素出栈;否则,将当前括号入栈;遍历完字符串后,遍历栈,统计栈中左右括号的数量,即为需要在字符串开头或结尾添加的右左括号数量;

代码

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

int main(){
    string s;
    while(cin >> s){
        stack<char> sk;
        for(auto& ch : s){
            if(ch == ']' && !sk.empty() && sk.top() == '['){
                sk.pop(); //当前元素与栈顶元素匹配,栈顶元素出栈
            }
            else{
                sk.push(ch);
            }
        }
        int l = 0, r = 0; //分别表示左右括号的个数
        while(!sk.empty()){
            if(sk.top() == '['){
                l++;
            }
            else{
                r++;
            }
            sk.pop();
        }
        cout << string(r, '[') + s + string(l, ']') << endl;
    }
    return 0;
}