Hướng giải của Kiểm tra dãy ngoặc đúng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

lời giải: Kiem tra dãy ngoac dung

Phan tich

Su dung ngan xep (stack). Duyet tung ky tu trong xau:

  • Neu la ngoac mo \((\), \([\), \({\): dãy vao stack.
  • Neu la ngoac dong: kiem tra stack co rong khong hoac ngoac o dinh stack co tuong ung khong. Neu khong hop le thi in NO.
  • Sau khi duyet xong, kiem tra stack co rong khong.

Do phuc tap: \(O(n)\).

Ma nguon C++

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

int main() {
    string s;
    cin >> s;
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) { cout << "NO\n"; return 0; }
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                cout << "NO\n"; return 0;
            }
        }
    }
    cout << (st.empty() ? "YES\n" : "NO\n");
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.