Stack ашиглан хаалт бүр зөв хаагдсан эсэхийг шалгана. Stack-д сүүлд орсон нь эхэлж гардаг.

Pre-IntermediateХугацаа: O(n)Санах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

s = "([]{})" string-ийн хаалт бүр хостой юу? Нээх хаалтыг Stack-д хийгээд, хаах хаалт ирэх бүрт Stack-ийн оройтой тулгая.

"(" ба "[" Stack-д орно. "]" ирэхэд орой дээр "[" байгаа тул хос болж гарна. "{" орж, "}" ирээд гарна. Сүүлийн ")" ирэхэд орой дээр "(" байна. Stack хоосорсон тул хариу YES.

Энгийн аргаас санаа руу

Энгийн арга бол хажуу хажуудаа байгаа "()", "[]", "{}" хосыг олж устгах. Ингэснээр string хоосорвол зөв. Гэтэл устгах бүрт string-ийг дахин гүйж хардаг тул n = 100 000 үед O(n²) болж удаан.

Гол санаа: хамгийн сүүлд нээсэн хаалт хамгийн түрүүнд хаагдах ёстой. "Сүүлд орсон нь эхэлж гарна" гэдэг нь яг Stack. Тиймээс нээх хаалтыг Stack-д хийнэ. Хаах хаалт ирэхэд Stack-ийн орой дээр түүний хос байх ёстой.

Нэр томьёо ба тэмдэглэгээ

Stack
Сүүлд орсон нь эхэлж гардаг бүтэц. C++-д stack<char> st;.
st.push(c), st.pop()
Орой дээр нэмэх ба оройгоос гаргах. Хоёулаа O(1).
st.top()
Орой дээрх элементийг харна. Хоосон Stack дээр дуудвал програм эвдэрнэ.
openOf(c)
Хаах хаалтын хос нээх хаалтыг буцаана: ) бол (.
s
{
0
[
1
(
2
)
3
(
4
)
5
]
6
}
7
st
хоосон

Хаалт бүр хостой юу? Нээх хаалтыг Stack-д хийнэ. Хаах хаалт ирэхэд Stack-ийн орой дээрх хаалттай тулгана.

Алхам 1 / 14
Хурд
  • Одоогийн тэмдэгт
  • Stack-д хүлээж буй
  • Stack-ийн орой
  • Хостой
  • Хос нь олдоогүй
Слайд 1 / 7

Тавагны овоо

Угаасан тавгаа овоолоход хамгийн сүүлд тавьсан нь хамгийн дээр байдаг. Авахдаа ч түүнийгээ эхэлж авна. Stack яг ийм: сүүлд орсон нь эхэлж гарна.

bracket-matching.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
stack<char> st;
char openOf(char c) {
if (c == ')') return '(';
if (c == ']') return '[';
return '{';
}
int main() {
cin >> s;
n = s.size();
for (int i = 0; i < n; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
st.push(s[i]);
} else {
if (st.empty() || st.top() != openOf(s[i])) {
cout << "NO\n";
return 0;
}
st.pop();
}
}
cout << (st.empty() ? "YES" : "NO") << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

( ) [ ] { } хаалтуудаас бүрдсэн string зөв хаагдсан бол YES, үгүй бол NO гэж хэвлэнэ. Stack-ийн "сүүлд орсон нь эхэлж гарна" гэсэн зарчмыг ойлгох сонгодог бодлого.

Яаж ажилладаг вэ?

1. String-ийн тэмдэгтүүдийг зүүнээс баруун тийш нэг нэгээр нь уншина. 2. Нээх хаалт ( [ { бол Stack-ийн орой дээр тавина: st.push(). 3. Хаах хаалт ) ] } ирвэл Stack-ийн орой дээрх хаалттай тулгана. 4. Хос нь таарвал оройн хаалтыг гаргана: st.pop(). Stack хоосон эсвэл хос нь биш бол шууд NO. 5. Бүх тэмдэгт дуусахад Stack хоосон бол YES. Хаагдаагүй хаалт үлдвэл NO. Оролт: нэг мөрөнд хаалтуудаас бүрдсэн string s.

Яагаад зөв, хэр хурдан бэ?

Stack-д үргэлж хараахан хаагдаагүй нээх хаалтууд байна, хамгийн сүүлд нээсэн нь орой дээр. Хаах хаалт зөвхөн тэр сүүлийн хаалтыг л хааж чадна. Тиймээс орой дээр хос нь байхгүй бол string буруу. Эцэст нь Stack хоосон байх ёстой, эс бол хаагдаагүй хаалт үлдсэн гэсэн үг.

Тэмдэгт бүрийг нэг л удаа харж, push, pop тус бүр O(1). Нийт хугацаа O(n), санах ой хамгийн муудаа O(n). n = 1 000 000 бол сая орчим үйлдэл хийнэ.

Түгээмэл алдаа

  • Хаах хаалт ирэхэд st.empty() шалгахаа мартах. Хоосон Stack дээр st.top() дуудвал програм унана. Кодонд st.empty() || ... гэж эхлээд шалгадаг.
  • Төгсгөлд Stack хоосон эсэхийг шалгахгүй орхих. Тэгвэл "(()" дээр буруу YES гарна.
  • Зөвхөн хаалтын тоог тоолох. "([)]"-д тоо нь таарч байгаа ч дараалал нь буруу.

Хязгаарын тохиолдол

  • Хоосон string: loop ажиллахгүй, Stack хоосон тул YES.
  • ")" шиг хаах хаалтаар эхэлбэл: Stack хоосон тул шууд NO.
  • Зөвхөн нээх хаалт "(((": Stack-д 3 хаалт үлдэж NO.
  • Сондгой урттай string хэзээ ч зөв байж чадахгүй. Код үүнийг тусад нь шалгахгүй, Stack өөрөө NO гаргана.

Өөрийгөө шалга

  1. "())(" string-ийн хариу юу вэ? Аль index дээр мэдэгдэх вэ?

    Хариу харах

    NO. Index 2 дээрх ")" ирэхэд Stack хоосон байна.

  2. "(()(()))"-г шалгахад Stack хамгийн ихдээ хэдэн хаалттай болох вэ?

    Хариу харах

    3. Index 4-ийн дараа Stack-д index 0, 3, 4 дээрх гурван "(" байна.

  3. Яагаад queue биш Stack хэрэгтэй вэ?

    Хариу харах

    Хаах хаалт хамгийн сүүлд нээсэн хаалттай хос болох ёстой. Сүүлийнхийг нь гаргадаг бүтэц бол Stack.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1."{[()]}" дээр тэмдэгт бүрийн дараа Stack ямар болохыг бич.

    Hint харах

    Эхний гурван тэмдэгт бүгд нээх хаалт.

    Хариу ба тайлбар

    { → {[ → {[( → {[ → { → хоосон. Хариу YES.

  2. 2.NO гарсан тохиолдолд алдаа хаана гарсныг (index-ийг) хэвлэдэг болго.

    Hint харах

    Хоёр газар NO гарна: loop дотор ба loop-ын дараа.

    Хариу ба тайлбар

    Loop дотор NO гарвал i-г хэвлэнэ. Loop-ын дараа Stack хоосон биш бол хаагдаагүй хаалтын index хэрэгтэй. Тиймээс Stack-д тэмдэгтийн оронд index хадгалаад, орой дээрх index-ийг хэвлэнэ.

  3. 3.Зөв хаагдсан string-ийн хамгийн гүн давхрыг ол. "(()(()))" бол 3.

    Hint харах

    Push хийх бүрт Stack-ийн хэмжээг хар.

    Хариу ба тайлбар

    st.push(s[i]);-ийн дараа best = max(best, (int)st.size()); гэж бичнэ. Хугацаа O(n) хэвээр. Хаалт ганц төрөл бол Stack ч хэрэггүй, тоолуур хангалттай.

Жишээ

Оролт

{[()()]}

Гаралт

YES

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.