Seminar5

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <forward_list>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

typedef long long ll;
using namespace std;

struct Node {
  int Data;
  Node* Next;

  explicit Node(int data) : Data(data), Next(nullptr) {}
};

// head = 0, tail = 0
//
// head -> * -> * -> * -> * -> tail -> 0
int main1() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  Node* head = nullptr;
  Node* tail = nullptr;
  int value = 0;
  while (cin >> value, value != 0) {
    Node* new_node = new Node(value);
    if (!tail) head = tail = new_node;
    else tail = tail->Next = new_node;
  }
  // Выводим.
  for (Node* cur = head; cur; cur = cur->Next)
    cout << cur->Data << " ";

  // Удаление.
  for (Node* cur = head; cur;) {
    Node* next = cur->Next;
    delete cur;
    cur = next;
  }
  return 0;
}

// То же на базе forward_list
int main2() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  forward_list<int> flist;
  int value = 0;
  auto it = flist.before_begin();
  while (cin >> value, value != 0) {
    it = flist.insert_after(it, value);
  }
  // Выводим.
  for (auto v : flist) cout << v << " ";

  return 0;
}

// Вразнобой в дек
int main3() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  deque<int> d;
  bool move_to_end = true;
  int value = 0;
  while (cin >> value, value != 0) {
    if (move_to_end) d.push_back(value);
    else d.push_front(value);
    move_to_end = !move_to_end;
  }
  // Выводим.
  for (auto v : d) cout << v << " ";

  return 0;
}

// Проверка ПСП для круглых скобок
int main4() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int opened = 0;
  string s;
  cin >> s;
  for (char c : s) {
    if (c == '(') ++opened;
    else if (c == ')') --opened;
    if (opened < 0) break;
  }
  cout << (opened == 0 ? "YES" : "NO") << endl;

  return 0;
}

// Проверка ПСП для разного типа скобок
// Проверка парности двух скобок
bool IsPair(char open, char close) {
  if (open == '(') return close == ')';
  if (open == '[') return close == ']';
  if (open == '{') return close == '}';
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  stack<char> opened_braces;
  string s;
  cin >> s;
  for (char c : s) {
    if (c == '(' || c == '[' || c == '{') opened_braces.push(c);
    else if (c == ')' || c == ']' || c == '}') {
      if (opened_braces.empty() || !IsPair(opened_braces.top(), c)) {
        cout << "NO" << endl;
        return 0;
      }
      opened_braces.pop();
    }
  }
  cout << (opened_braces.empty() ? "YES" : "NO") << endl;

  return 0;
}