题解

遇到左括号就压栈。

遇到右括号时，它必须和当前栈顶的左括号类型对应；匹配成功后弹栈。

如果遇到右括号时栈已经为空，或者类型不对应，则一定不合法。

最后栈也必须为空。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

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

bool match(char l, char r) {
    return (l=='('&&r==')') || (l=='['&&r==']') || (l=='{'&&r=='}');
}

int main() {
    string s;
    cin >> s;
    stack<char> st;

    for (char c : s) {
        if (c=='(' || c=='[' || c=='{') {
            st.push(c);
        } else {
            if (st.empty() || !match(st.top(), c)) {
                cout << "No\n";
                return 0;
            }
            st.pop();
        }
    }

    cout << (st.empty() ? "Yes" : "No") << '\n';
    return 0;
}