Дана последовательность из N круглых, квадратных и фигурных скобок. Узнайте, можно ли добавить числа и арифметические операции, чтобы получить правильное арифметическое выражение.

Вход
Первая строка содержит количество скобок-N (1 ≤ N ≤ 100 000).
Второй содержит последовательность из N символов из множества (,) [,] {,}.
Выход
Отображает слово "Да", если вы можете получить правильное арифметическое выражение, или" нет", если вы не можете.

Логично, что мы всегда можем добавить числа и арифм. операции чтобы получить правильное арифм. выражение, если скобки в выражении расставлены верно. Задача сводится к проверке "баланса скобок" в строке.

Воспользуемся структурой данных стек. Она добавляет и забирает элементы с конца. Если мы встретим открывающую скобку, добавим её тип в стек. Если мы встретим закрывающую скобку, то верхний элемент в стеке должен быть такой же по типу открывающей скобкой, иначе последовательность неправильная. Если же всё ок, удалим последний элемент из стека.

Для удобства заведём map, чтобы мы могли не парясь определить для каждой закрывающей скобки соответствующую открывающую.

#include <bits/stdc++.h>

using namespace std;

int main() {

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   int n;

   string s;

   cin >> n >> s;

   stack<char> st;

   map<char, char> ma;

   ma[')'] = '(';

   ma[']'] = '[';

   ma['}'] = '{';

   for (int i = 0; i < s.size(); ++i) {

       if (s[i] == '(' || s[i] == '[' || s[i] == '{')

           st.push(s[i]);

       else if (!st.empty() && st.top() == ma[s[i]])

           st.pop();

       else {

           cout << "No" << endl;

           return 0;

       }

   }

   if (!st.empty()) cout << "No" << endl;

   else cout << "Yes" << endl;

   return 0;

}

В Java и stack, и map тоже уже есть. Алгоритм тот же.

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

import java.util.Stack;

public class Main {

   public static void main(String[] args) {

       int n;

       String s;

       try (Scanner in = new Scanner(System.in)) {

           n = Integer.parseInt(in.nextLine());

           s = in.nextLine();

       }

       Stack<Character> st = new Stack<>();

       Map<Character, Character> ma = new HashMap<>();

       ma.put(')', '(');

       ma.put(']', '[');

       ma.put('}', '{');

       for (char c : s.toCharArray()) {

           if (c == '(' || c == '[' || c == '{')

               st.push(c);

           else if (!st.isEmpty() && st.peek() == ma.get(c))

               st.pop();

           else {

               System.out.println("No");

               return;

           }

       }

       if (!st.isEmpty()) System.out.println("No");

       else System.out.println("Yes");

   }

}

Насчёт нового не знаю, но в классическом стека как структуры данных нет, приходится писать через массив. Не страшно, заведём массив на 100000 символов, будем хранить текущий индекс вершины нашего стека в массиве. Для удобства вынесем эти операции в процедуры и функции.

var

 st: array[1..100000] of char;

 i, n, v: longint;

 s: string;

// Добавление элемента в конец стека

// Ставим в конец стека x, увеличиваем конец стека.

procedure push(x: char);

begin

 st[v] := x;

 v := v + 1;

end;

// Удаление элемента из стека

// Уменьшаем конец стека.

procedure pop();

begin

 v := v - 1;

end;

// Получение вершины стека

function top(): char;

begin

 top := st[v - 1];

end;

// Проверка стека на пустоту

// Если индекс конца стека равен 1, стек пустой.

function empty(): boolean;

begin

 empty := v = 1;

end;

begin

 readln(n);

 v := 1;

 readln(s);

 for i := 1 to n do

   if (s[i] = '(') or (s[i] = '[') or (s[i] = '{') then

     push(s[i])

   else if (not empty()) and (((s[i] = ')') and (top() = '(')) or ((s[i] = ']') and (top() = '[')) or ((s[i] = '}') and (top() = '{'))) then

     pop()

   else

   begin

     writeln('No');

     exit;

   end;

 if empty() then writeln('Yes')

 else writeln('No');

end.