Логично, что мы всегда можем добавить числа и арифм. операции чтобы получить правильное арифм. выражение, если скобки в выражении расставлены верно. Задача сводится к проверке "баланса скобок" в строке.
Воспользуемся структурой данных <em>стек</em>. Она добавляет и забирает элементы с конца. Если мы встретим открывающую скобку, добавим её тип в стек. Если мы встретим закрывающую скобку, то верхний элемент в стеке должен быть такой же по типу открывающей скобкой, иначе последовательность неправильная. Если же всё ок, удалим последний элемент из стека.
<h3 /><h3>Код (C++)</h3>
Для удобства заведём <em>map</em>, чтобы мы могли не парясь определить для каждой закрывающей скобки соответствующую открывающую.
#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;
}
<h3>Код (Java)</h3>
В 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");
}
}
<h3>Код (Pascal)</h3>
Насчёт нового не знаю, но в классическом стека как структуры данных нет, приходится писать через массив. Не страшно, заведём массив на 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.
