HA22_2

coloriot

Sep 6th, 2024

Never

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 2.12 KB | None | 0 0

raw download clone embed print report

#include <iostream>
#include <string>
using namespace std;
// Решение задачи ПСП стэком
// Структура стэка - ноды и список (из предыдущих задач)
struct Node {
char value;
Node* next;
};
struct List {
Node* start;
int size;
// Конструктор
List() {
start = nullptr;
size = 0;
}
};
// Добавление и удаление элементов (из прошлых задач)
void push(List& list, char new_value) {
Node* new_node = new Node;
new_node->value = new_value;
new_node->next = list.start;
list.start = new_node;
++list.size;
}
void pop(List& list) {
if (list.size == 0) {
return;
}
Node* temp = list.start;
list.start = list.start->next;
delete temp;
--list.size;
}
// Возвращает верхний элемент стэка
bool peek(List& list, char& topValue) {
if (list.size == 0) {
return false;
}
topValue = list.start->value;
return true;
}
bool isEmpty(List& list) {
return list.size == 0;
}
// Проверка последовательности - здесь используются вещи из библиотеки string
bool isCorrectSequence(const string& sequence) {
List stack;
for (int i = 0; i < sequence.length(); ++i) {
char ch = sequence[i];
if (ch == '(' || ch == '[' || ch == '{') {
push(stack, ch);
} else if (ch == ')' || ch == ']' || ch == '}') {
char top;
if (!peek(stack, top)) {
return false;
}
if ((ch == ')' && top == '(') ||
(ch == ']' && top == '[') ||
(ch == '}' && top == '{')) {
pop(stack);
} else {
return false;
}
}
}
return isEmpty(stack);
}
int main() {
string test;
while (cin >> test) {
cout << test << " " << (isCorrectSequence(test) ? "yes" : "no") << endl;
}
return 0;
}

Add Comment

Please, Sign In to add comment