Операции со строками в STL

В этом листке мы снова будем работать со строками, активно используя стандартную библиотеку языка C++ STL (Standard template library).

Для прочтения рекомендуется следующий раздел сайта www.cppreference.com.

Считывание строк

Напомним, что строки можно считывать двумя способами: до пробельного символа (пробела, конца строки, символа табуляции) при помощи конструкции cin >> S, и до конца строки при помощи функции getline(cin, S).

Арифметические операторы

Со строками можно выполнять следующие арифметические операции:
= - присваивание значения.
+= - добавление в конец строки другой строки или символа.
+ - конкатенация двух строк, конкатенация строки и символа.
==, != - посимвольное сравнение.
<, >, <=, >= - лексикографическое сравнение.

Подробней об операторах для строк читайте здесь.

Конструкторы

Строки можно создавать с использованием следующих конструкторов:
string() - конструктор по умолчанию (без параметров) создает пустую строку.
string(string & S) - копия строки S
string(int n, char c) - повторение символа c заданное число n раз.
string(char c) - строка из одного символа c.
string(string & S, int start, int len) - строка, содержащая не более, чем len символов данной строки S, начиная с символа номер start.

Конструкторы можно вызывать явно, например, так:

S += string(10, 'z');

В этом примере явно вызывается конструктор string для создания строки, состоящей из 10 символов 'z'.

Неявно конструктор вызывается при объявлении строки с указанием дополнительных параметров. Например, так:

string S(10, 'z');

Подробней о конструкторах для строк читайте здесь.

Методы для строк

Методом называется функция, которая применяется к объекту, например, строке. При вызове метода его имя пишется после идентификатора объекта через точку, например, у объекта типа string есть метод size, возвращающий длину строки. Если S — это строка, то метод вызывается так: S.size(). Другой пример: метод substr возвращает подстроку заданной строки:

string S = "Hello, world!";
cout << S.substr(6, 5) << endl;

В данном случае будет выведен текст world.

Вот список полезных методов, применяемых к строкам:

append	добавляет строку или символы к строке
assign	присваивает строке значение строк символов или других строк C++
clear	удаляет все символы из строки
compare	сравнивает две строки
empty	возвращает true если в строке нет символов
erase	удаляет символы из строки
find	ищет символы в строке
find_first_not_of	находит первый символ, отличный от
find_first_of	находит первый символ схожий с
find_last_not_of	находит последний символ, отличный от
find_last_of	находит последний символ, схожий с
insert	вставляет символы в строку
length	возвращает длину строки
npos	специальное значение, означающее «не найдено» или «все оставшиеся символы»
push_back	добавляет символ в конец строки
replace	заменяет символы в строке
resize	меняет размер строки
rfind	находит последнее вхождение подстроки
size	возвращает количество символов в строке
substr	возвращает определённую подстроку
swap	меняет две строки содержимым

Для обозначения того, что запрашиваемая последовательность символов не найдена, многие методы (например, find) возвращают специальную константу string::npos.

A: Есть ли символ @

Дана строка (считывается при помощи getline). Если в этой строке есть символ @, то выведите YES, иначе выведите NO.

Используйте метод find, для поиска символа в строке.

Ввод	Вывод
email@179.ru	YES

B: Есть ли гласная

Дана строка (считывается при помощи getline). Если в этой строке есть заглавная или строчная гласная буква (A, O, I, U, E, Y) то выведите YES, иначе выведите NO.

Используйте метод find_first_of, для поиска гласной в данной строке.

Ввод	Вывод
Hmmm...	NO

C: Подсчитайте количество символов @

Подсчитайте, сколько раз в данной строке встречается символ @.

Указание: используйте метод find, запоминая последнюю позицию найденного символа @ и продолжая поиск только с этой позиции. Подсчитывайте количество успешно завершенных поисков.

Примечание: решения, в которых на каждом шаге метод find вызывается дважды, приниматься не будут.

Ввод	Вывод
email@179.ru	1

D: Подсчитайте количество гласных

Подсчитайте количество заглавных и строчных гласных букв в данной строке. Воспользуйтесь предыдущей задачей, заменив метод find на find_first_of.

Ввод	Вывод
We All Live In The Yellow Submarine!	13

E: Поиск подстроки

Даны две строки (с пробелами). Выведите YES, если вторая строка встречается внутри первой, иначе выведите NO.

Ввод	Вывод
We All Live In The Yellow Submarine low	YES

F: Сколько раз одна подстрока находится внутри другой?

Даны две строки. Подсчитайте, сколько раз вторая строка встречается в первой, как ее подстрока. “Пересекающиеся” вхождения считаются несколько раз.

Ввод	Вывод
ABABA ABA	2

G: Вычеркнуть буквы

Даны две строки. Определите, можно ли из первой строки удалить несколько символов так, чтобы получилась вторая строка. Выведите YES или NO.

Ввод	Вывод
Program ram	YES
Program prog	NO

H: Пробелы после запятой

После запятой в тексте должен строять пробел. Дана строка, вставкой пробелов в неё добейтесь выполнения этого правила. Не надо вставлять пробел, если он там уже есть.

Ввод	Вывод
Question of Life,The Universe, and Everything	Question of Life, The Universe, and Everything

I: Продублировать гласные буквы

Дана строка. Продублируйте в ней все гласные буквы.

Ввод	Вывод
Question of Life, The Universe, and Everything	Quueestiioon oof Liifee, Thee UUniiveersee, aand EEveeryythiing

J: Удалите все символы @

Дана строка (считывается при помощи getline). Удалите из нее все символы @, находя их при помощи метода find и удаляя их при помощи метода erase.

Не забывайте, что поиск нужно продолжать с места последнего нахождения данного символа, а не с начала строки!

Ввод	Вывод
Bilbo.Baggins@bagend.hobbiton.shire.me	Bilbo.Bagginsbagend.hobbiton.shire.me

K: Удалите все гласные буквы

Удалите из заданной строки все гласные буквы.

Ввод	Вывод
We All Live In The Yellow Submarine!	W ll Lv n Th llw Sbmrn!

L: Удалить все вхождения слова

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

Ввод	Вывод
AABCBC ABC	ABC

M: Удалить все внутри скобок

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

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

Ввод	Вывод
(1+(2*3))+(	)+(

N: Замените 1 на one везде

В некоторой строке замените все символы 1 на слово one. Используйте методы find и replace.

Ввод	Вывод
1+1=2	one+one=2

O: Заменить все вхождения слова

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

Ввод	Вывод
Hello, world! Hello Hi	Hi, world!
MooMoo Mo Mooo	MooooMoooo

P: Удалите лишние пробелы

Дана строка. Удалите все лишние пробелы: из начала строки, из конца строки и повторяющиеся пробелы внутри строки.

Обязательно выводите конец строки после вывода самой строки!

Ввод	Вывод
Hello, world!	Hello, world!

Q: Поменять два слова местами

Программа получает на вход строку, состоящую из двух слов, разделенных пробелом (слово любая последовательность непробельных символов). Создайте строку, полученную из данной перестановкой слов и выведите ее.

Код, подобный такому, приниматься не будет:

string S1, S2;
cin >> S1 >> S2;
cout << S1 << " "<< S2 << endl;

Не забывайте выводить символ конца строки!

Ввод	Вывод
Hello, world!	world! Hello,

R: Пословное обращение строки

Строка состоит из слов, разделенных пробелами. Создайте строку, полученную из данной перестановкой всех слов в обратном порядке и выведите результат.

Ввод	Вывод
One two three	three two One

S: Смайлики

Напишите программу, которая посчитает количество смайликов в заданном тексте.

Смайликом будем считать последовательность символов, удовлетворяющую условиям:

первым символом является либо ; (точка с запятой) либо : (двоеточие) ровно один раз
далее может идти символ – (минус) сколько угодно раз (в том числе символ минус может идти ноль раз)
в конце обязательно идет некоторое количество (не меньше одной) одинаковых скобок из следующего набора: (, ), [, ].
внутри смайлика не может встречаться никаких других символов.

Например, нижеприведенные последовательности являются смайликами:

:)
;---------[[[[[[[[

в то время как эти последовательности смайликами не являются (хотя некоторые из них содержат смайлики):

:-)]
;--
-)
::-(
:-()

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

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

Выведите одно число — количество смайликов, которые встречаются в тексте.

Ввод	Вывод
:);------[[[[[]	2
:-)];----;	1
-)(---:---	0
hello :-)	1

T: Выравнивание по левому краю

Первая строка входного файла содержит целое число N. Далее (начиная со следующей строки) идет текст, который может содержать много строк. Необходимо данный текст разбить на строки, длина которых не превосходит N и вывести его в файл. В каждой выведенной строке не должно быть пробелов в начале строки, пробелов в конце строки, слова в строке должны разделяться одним пробелом. При этом каждая строка должна быть максимально длинной, то есть строки формируются по “жадному” принципу: добавляем слова из входного файла до тех пор, пока длина полученной строки не превышает N, после этого ставим разрыв строки. Гарантируется, что во входном файле нет слов длиннее N символов.

Ввод	Вывод
15 We all live in the yellow submarine	We all live in the yellow submarine

U: Выравнивание по ширине

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

Последняя строка в выводе должна быть выровнена по левому краю.

Ввод	Вывод
15 We all live in the yellow submarine	We all live in the yellow submarine

V: Правила оформления программ

Дана строка, содержащее арифметическое выражение на языке C. Строка может содержать только следующие символы: пробелы, цифры, латинские буквы, знаки +, -, *, /, %, =, (, ), , (запятая).

Гарантируется, что записанное арифметическое выражение синтаксически корректно и может содержать следующие лексемы:

Целочисленные константы
Идентификаторы переменных
Бинарные операции +, -, *, /, %, =.
Унарные операции +, -.
Скобки, меняющие порядок выполнения операций.
Вызовы функций от 0, 1, 2 и большего числа аргументов.

Расставьте в этом выражении пробелы в соответствии с правилами оформления программ:

Бинарные операции отделяются пробелами с двух сторон.
Унарные операции пишутся слитно с последующим операндом.
С внутренней стороны скобочек пробелы не ставятся.
Имя функции пишется слитно с последующей скобкой.
Запятая пишется слитно с предыдущим текстом, после запятой ставится пробел.
В строке не должно быть начальных и конечных пробелов.

После вывода выражения не забудьте вывести символ конца строки.

Ввод	Вывод
a=2+2	a = 2 + 2
Var1( Var2+( 12-3 )/x+f( x,2(a+b),-1))/(-4- - x)	Var1 * (Var2 + (12 - 3) / x + f(x, 2 * (a + b), -1)) / (-4 - -x)

W: Действительное число

Вещественное число задается следующим образом (форма Бэкуса-Наура):

<Number> ::= [<Sign>] <digit> {<digit>}[<Separator> <digit> {<digit>}]
           [<Exponent> [<Sign>] <digit> {<digit>}]
	   <digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
	   <Sign> ::= '+' | '-'
	   <Separator> ::= '.'
	   <Exponent> ::= 'E' | 'e'

В форме Бэкуса-Наура знак ::= означает определение, например, <Sign> ::= '+' | '-' означает, что понятие Sign — это один из двух символов + или +.

Значение в квадратных скобках означает, что это значение может встречаться, а может и не встречаться, а значение в фигурных скобках означает, что это выражение может быть записано 0, 1 или большее количество раз подряд. Например, записать [<Sign>] <digit> {<digit>} означает Sign, который может присутсвовать или отсутствовать, за которым идет digit, повторенная 1 или более раз.

Программа получает на вход одну строку, содержащащей не более 200 символов.

Выведите YES, если эта строка является корректной записью действительного числа в соответствии с данным определением, или NO, в противном случае.

Ввод	Вывод
-8.1e+1	YES
e+1	NO

X: Значение выражения

Задано числовое выражение. Необходимо вычислить его значение или установить, что оно содержит ошибку. В правильном выражении могут встречаться знаки сложения, вычитания, умножения, скобки и пробелы (пробелов внутри чисел быть не должно). Приоритет операций стандартный. Все числа в выражении целые и принадлежат диапазону int. Также гарантируется, что все промежуточные вычисления умещаются в этот тип.

Формат входных данных

В первой строке вводится выражение. Его длина не превосходит 100 знаков. После выражения идет переход на новую строчку.

Формат выходных данных

Выведите значение этого выражения или слово WRONG, если значение не определено.

Пример

Ввод	Вывод
1+(2*2 - 3)	2
1+a+1	WRONG
1 1 + 2	WRONG

Y: Словарь

Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.

К сожалению, для полноценного изучения языка недостаточно только одного словаря: кроме англо-латинского необходим латинско-английский. За неимением лучшего он решил сделать второй словарь из первого.

Как известно, словарь состоит из переводимых слов, к каждому из которых приводится несколько слов-переводов. Для каждого латинского слова, встречающегося где-либо в словаре, Вася предлагает найти все его переводы (то есть все ангийские слова, для которых наше латинское встречалось в его списке переводов), и считать их и только их переводами этого латинского слова.

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

Формат входных данных

В первой строке содержится единственное целое число N (1≤N≤100) — количество английских слов в словаре. Далее следует N описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число K≥1 — количество переводов. В следующих K строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.

Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает 100. Длина каждого слова не превосходит 15 символов.

Формат выходных данных

Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число N — количество латинских слов в словаре. Далее выведите N описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.

При этом порядок английских слов внутри перевода одного латинского может быть каким угодно. Кроме того, порядок следования латинских слов для перевода в словаре также не важен.

Пример

Ввод	Вывод
3 apple 3 malum pomum popula fruit 3 baca bacca popum punishment 2 malum multa	7 baca - fruit bacca - fruit malum - apple, punishment multa - punishment pomum - apple popula - apple popum - fruit

Z: EuroEnglish

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

Первоочередной задачей будет избавление от буквы c, которая в сочетаниях сi и сe будет изменяться на s, в сочетании ck — опускаться, а в остальных случаях заменяться на k. При этом все замены будут производиться в строгом порядке слева направо. То есть, например, в слове success сначала первая из двух букв c заменится на k, а затем вторая — на s, то есть получится suksess. А слово cck превратится в kk.

На второй год из английских слов изымут все удвоенные буквы: ee изменят на i, oo - на u, a в остальных комбинациях будут просто писать одну букву вместо двух одинаковых. Такие замены также будут делать строго в порядке слева направо. Так, слово ooo превратится в uo, а oou — просто в u (в нем сначала oo заменится на u, а затем uu — на u), слово iee превратится в i (в нем сначала ee заменится на i, а затем ii — на i).

На третий год на конце слова станут опускать букву е, если эта буква не является единственной буквой в слове.

Наконец, завершением реформы станет отмена артиклей (в английском языке три артикля: а, an и the). При этом удаляться эти артикли будут только тогда, когда они в исходном тексте были словами a, an, the. То есть, например, текст the table после реформ первых трех лет превратиться в th tabl, а после реформы четвертого года — просто в tabl. А слово aaaaa после реформы первых лет станет словом a, но поскольку изначально оно не было словом a (артиклем), то оно в итоге так и останется словом a.

Напишите программу, которая будет переводить классический английский текст на Eвроинглиш.

Формат входных данных

Во входном файле записана одна строка текста, состоящая не более чем из 200 символов: латинских строчных и заглавных букв, пробелов и знаков препинания (в тексте могут встречаться: точка, запятая, вопросительный и восклицательный знаки, двоеточие, тире, точка с запятой, открывающаяся и закрывающаяся скобки, апострофы, кавычки). Заглавные буквы могут встречаться только в начале слова. Нигде подряд не могут стоять два пробела. В начале и в конце строки не может стоять пробел. Слова отделяются друг от друга пробелами и/или знаками препинания.

Формат выходных данных

В выходной файл нужно выдать преобразованную строку с учетом следующих требований:

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

Пример

Ввод	Вывод
cacao and coffee	kakao and kofi
Cinderella! Where Is The Dress???	Sinderela! Wher Is Dres???
'A' is a letter	'' is leter
!!!Hello!!!A-the-"word"	!!!Helo!!!--"word"
Aaaa then the ckckck	A then k
"A"-the an	""-
A the an
success	sukses