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

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

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

Код (C++)

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

include lt;bits/stdc++.hgt;

using namespace std;

int main()

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   int n;

   string s;

   cin gt;gt; n gt;gt; s;

   stacklt;chargt; st;

   maplt;char, chargt; ma;

   ma[')'] = '(';

   ma[']'] = '[';

   ma[''] = '';

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

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

           st.push(s[i]);

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

           st.pop();

       else

           cout lt;lt; "No" lt;lt; endl;

           return 0;

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

   else cout lt;lt; "Yes" lt;lt; endl;

   return 0;

Код (Java)

В 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();

       Stacklt;Charactergt; st = new Stacklt;gt;();

       Maplt;Character, Charactergt; ma = new HashMaplt;gt;();

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

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

       ma.put('', '');

       for (char c : s.toCharArray())

           if (c == '(' c == '[' c == '')

               st.push(c);

           else if (!st.isEmpty() amp;amp; 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");

Код (Pascal)

Насчёт нового не знаю, но в классическом стека как структуры данных нет, приходится писать через массив. Не ужасно, заведём массив на 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.