AL6

Андрей Яроцкий
Андрей Яроцкий

Latest posts by Андрей Яроцкий (see all)

Задача AL6

Условие

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

Тесты

Входные данные Выходные данные
1 ( NO
2 )) NO
3 [} NO
4 {} YES
5 (){}[] YES
6 ({[]}{}) YES
7 [({}())[] NO

Код программы

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

Код программы на ideone.com

Условие задачи

ML12

Условие задачи:

Даны [latex]x,y,z[/latex]. Вычислить  [latex] a = x \arctan{y} — e^{1-z}[/latex] и [latex] b = \frac{\sqrt{\left|3-x^2 \right|}- \sqrt[3]{\left|y-x \right|}}{1-\frac{x^2}{2}+\frac{y^2}{4}-\frac{z^2}{8}}.[/latex]

Алгоритм решения:

1)В условии задачи не указано какие должны быть числа [latex]x,y,z[/latex] , поэтому правильнее всего использовать диапазон long double, чтобы включить как можно больше значений.

2)Подключим библиотеку <cmath> , с помощью которой подключим математические функции и, придерживаясь правил порядка вычислений, расставим скобки.

Код программы:

Тесты:

Ввод: # Вывод: #
x 1 a 0.971813
y 2 b 1.10457
z 3
Ввод: # Вывод: #
x -9 a -16.1645
y 13 b 2.19263
z 0
Ввод: # Вывод: #
x 7 a 10.361
y 11 b -0.107389
z 21

Здесь находится код в ideone.com

e-olymp 2479. Баланс скобок

Царев Николай Александрович
Царев Николай Александрович

Latest posts by Царев Николай Александрович (see all)

Условие

(Ссылка на задачу в e-olymp)

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

  • оно является пустым
  • если A и B правильны, то AB правильно
  • если A правильно, то (A) и [A] правильны

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

Входные данные

Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

Выходные данные

Для каждого теста вывести в отдельной строке «Yes«, если выражение является правильным и «No» иначе.

Тесты

3
([])
(([()])))
([()[]()])()
Yes
No
Yes

(тесты взяты с e-olymp.com)

Изображение для задачи 2479

Результаты задачи № 2479

Алгоритм

Решение задачи состоит в последовательной обработке каждого символа. Мы читаем символ. Если это открывающая скобка — то кладем в стэк. Если закрывающая — смотрим последний элемент в стэке. Если скобка «находит пару» — то удаляем их обоих. В противном случае — это ошибка. Если же после обработки всех символов в стэке останется скобки — то значит в строке было больше открывающих скобок, и такая строка — не правильная.

Маленький костыль для этой задачи — это лишнее считывание символа в самом начале. Делается это для того, чтобы дальше, мы спокойно могли использовать функцию getline, которая читает строку до символа конца строки. Эти дополнительным вводом, мы как бы забираем на себя символ конца строки стоящий после числа, определяющее кол-во строк.

Ссылка на ideone.com

А1043

Фесенко Катерина Володимирівна
Фесенко Катерина Володимирівна

Latest posts by Фесенко Катерина Володимирівна (see all)

Задача

Построить все правильные скобочные выражения длины 10, то есть, которые содержат по 5 левых и по 5 правых скобок.

Код на языке С++:

Посмотреть программу можно здесь

Код на языке Java:

Ссылка на программу: http://ideone.com/9MjHSA

Решение:

В переменной [latex]x[/latex] мы будем хранить количество открытых ([latex]»(«[/latex]) скобок. Далее  проверяем условие, что если [latex]x>0[/latex], то можем поставить закрывающую ([latex]»)»[/latex]) скобку. Идем дальше, смотрим сколько свободных мест осталось и если мест осталось столько же, сколько открывающих, то все остальные закрывающие.

Ю12.29

Стеблинський Ігор Віталійович
Стеблинський Ігор Віталійович

Latest posts by Стеблинський Ігор Віталійович (see all)

Задача: Скобки. Текст ( например, арифметическое выражение) содержит многократно вложенные круглые скобки. Исправить его, оставив скобки первого уровня круглыми, второго — заменить на квадратные, третьего и последующих  — на фигурные. Убедиться в корректности использования скобок.

Тесты:

Введенная строка Выведенная строка
ln(sin((a+b)c-d)) ln{sin[(a+b)c-d]}
ln(sin((a+b)c-d))+ln(sin((a+b)c-d)) ln{sin[(a+b)c-d]}+ln{sin[(a+b)c-d]}
cos((a-b)c) cos[(a-b)c]

Код string

Код c-string

Ссылки на коды:

string

c-string

Ход решения:

Вводим строку. Задаем две переменные: l — уровень вложенности скобок и maxl — максимальный уровень вложенности скобок. Делаем цикл в котором заменяем все ‘(‘ , ‘)’ скобки на ‘{‘ , ‘}’. Делаем второй цикл в котором меняем скобки, которые являются последними по уровню вложенности на ‘(‘, ‘)’ и скобки, стоящие на уровень ниже меняем на ‘[‘, ‘]’, все остальные скобки оставляем без изменений.