Как определить максимальную глубину вложенности скобок
Перейти к содержимому

Как определить максимальную глубину вложенности скобок

  • автор:

Проверка вложенности скобок

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

Зачем нужно проверять вложенность скобок

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

Первое, что приходит в голову, это подсчитать количество открывающих и количество закрывающих скобок в строке и если эти числа равны, то считать, что последовательность скобок правильная. Возможно, это и будет работать в самых простых случаях, однако последовательность «(())» будет правильной, а последовательность «())(» – неправильной. При этом количество открывающих и закрывающих скобок у них одинаковы. Кроме того, скобки могут быть разных типов (круглая, фигурная, квадратная и т.п.) и скобки должны соответствовать ещё и по типу. Поэтому в основе такой проверки должна лежать работа со стеком.

Стек

Стек – это такая коллекция объектов, в которой первым извлекается последний добавленный объект (т.н. LIFO – «last in, first out»). В Java есть такой класс как Stack, однако это класс, а не интерфейс, а программировать нужно на уровне интерфейсов, поэтому использовать его не рекомендуется. Вместо этого возьмём интерфейс Deque – коллекцию, которая поддерживает удаление и вставку с обоих концов. В качестве реализации этого интерфейса возьмём LinkedList.

Реализация

Теперь перейдём к реализации нашего метода проверки isValidBrackets(). Метод принимает строку, содержащую скобки и возвращает true – если вложенность скобок правильная. Сначала определим соответствие каждой открывающей и закрывающей скобки.

private static boolean isValidBrackets(String input) <
Map brackets = new HashMap<>();
brackets.put( ‘)’ , ‘(‘ );
brackets.put( ‘>’ , ‘ brackets.put( ‘]’ , ‘[‘ );

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

Далее создаём наш стек на базе LinkedList.

Deque stack = new LinkedList<>();
for ( char c : input.toCharArray()) if (brackets.containsValue(c)) // одна из открывающих скобок
stack.push(c);
> else if (brackets.containsKey(c)) // одна из закрывающих скобок
if (stack.isEmpty() || stack.pop() != brackets.get(c)) return false ;
>
>
>
// в конце стек должен быть пустым
return stack.isEmpty();

Затем в цикле проходимся по каждому символу строки и проверяем, если это это открывающая скобка (метод мапы containsValue()), то просто добавляем его в стек с помощью метода push(). Если же это закрывающая скобка (метод containsKey()), то стек должен быть не пустым и последним добавленным в него элементом должна быть открывающая скобка такого же типа.

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

Проверка

Теперь проверим работу нашего метода на конкретных примерах:

public static void main(String[] args) <
System.out.println(isValidBrackets( «» )); // 1 — true
System.out.println(isValidBrackets( «(abc)» )); // 2 — true
System.out.println(isValidBrackets( «((<>[()]))» )); // 3 — true
System.out.println(isValidBrackets( «(()» )); // 4 — false
System.out.println(isValidBrackets( «((]» )); // 5 — false
System.out.println(isValidBrackets( «]» )); // 6 — false
>

  1. true – т.к. входная строка вообще не содержит никаких символов.
  2. true – в строке содержатся помимо скобок и другие символы, но вложенность правильная
  3. true – несколько разных видов скобок, но вложенность правильная
  4. false – не хватает ещё одной круглой закрывающей скобки
  5. false – встретили закрывающую квадратную скобку, но ожидаем круглую
  6. false – в строке сразу встретили закрывающую квадратную скобку

При обработке слишком длинной строки имеет смысл обрабатывать её в буферизованном потоке.

Баланс скобок, нужно определить номер строки с лишней скобкой

В текстовом файле, содержащем текст программы на языке Си, проверить соответствие открывающихся и закрывающихся фигурных скобок < и >. Во входном потоке в в виде набора строк задан текст, состоящий из букв, цифр и специальных символов, таких как точка, тире, точка с запятой, скобки и др. Размер файла не превышает 1МБ, а длина строки — 1000 символов. Пример:

int main() < while (true) < if (true) < >else < printf("Hello!"); >> > 

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

YES 3 

Есть идеи как определить номер первой строки со скобкой, которой не хватило пары? Нужен кратчайший путь, пусть примитивный, по возможности без стеков, в рамках существующего решения. Как задать переменной error нужное значение line? Мой код:

#include #include using namespace std; int main() < char sim,last='0'; int q=0,max=0,error=0,line=1; ifstream text("input.txt"); while ((sim=text.get())!=EOF) < if ((int)sim==10) < line++; >if (sim=='<') < q++; if (q>=max) max=q; last=' else if (sim=='>') < if (q) < q--; if (last!='') < break; >last='>'; > > > if (!q) cout

Проверить правильность расстановки скобок

Совсем не могу понять как это реализовать.Для введённой пользователем с клавиатуры строки (максимальная длина строки — 80 символов) программа должна определить, корректно ли расставлены скобки (круглые, фигурные, квадратные) или нет. Перемешивание скобок (пример: «<[>]») считается некорректным вариантом.

Отслеживать

задан 26 дек 2020 в 20:20

bruhmomentum bruhmomentum

59 1 1 серебряный знак 10 10 бронзовых знаков

26 дек 2020 в 21:08

2 ответа 2

Сортировка: Сброс на вариант по умолчанию

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

// g++ -std=c++11 -pedantic -Wall -Wextra parens.cpp #include #include bool balanced(const std::string &s) < std::stackstack; for (char c : s) < switch (c) < case '(': stack.push(')'); break; case '[': stack.push(']'); break; case ''); break; case ''); break; case ')': case ']': case '>': case '>': if (stack.empty() || stack.top() != c) < return false; >stack.pop(); break; default: break; > > return stack.empty(); > void test(const std::string& s) < std::cout int main()
"" yes "a(b[c]d)e" yes "a(b[c)d]e" no "a(b[c]d" no "b[c]d)e" no 

Sampay8 / Определить максимальную глубину вложенности скобок

Save Sampay8/11905b0f56c0256807f14d5edb0f468f to your computer and use it in GitHub Desktop.

Определить максимальную глубину вложенности скобок

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

//Задача
//Дана строка из символов '(' и ')'. Определить, является ли она корректным скобочным выражением. Определить максимальную глубину вложенности скобок.
//Пример “(()(()))” -строка корректная и максимум глубины равняется 3.
//Пример не верных строк: "(()", "())", ")(", "(()))(()"
//Для перебора строки по символам можно использовать цикл foreach, к примеру будет так foreach (var symbol in text)
//Или цикл for(int i = 0; i < text.Length; i++) и дальше обращаться к каждому символу внутри цикла как text[i]
//Цикл нужен для перебора всех символов в строке.
using System;
namespace ConsoleApp2
class Program
static void Main(string[] args)
Run();
>
private static void Run()
bool isRun = true;
while (isRun)
Console.Clear();
ShowMenu();
GetInput(out string command);
switch (command)
case "1":
GetInput(out string stringToCheck);
CheckString(stringToCheck);
break;
case "2":
isRun = false;
break;
default:
Console.WriteLine("Команда не распознана, попробуйте снова");
Console.ReadKey();
break;
>
>
>
private static void CheckString(string text)
bool isCorrect = true;
int openBracket = 0;
int maxDepth = 0;
foreach (char symbol in text)
if (symbol == '(')
openBracket++;
if(openBracket > maxDepth)
maxDepth =openBracket ;
>
else if (symbol == ')')
openBracket--;
>
else if (maxDepth < 0)
isCorrect = false;
return;
>
>
isCorrect = openBracket == 0;
if (isCorrect)
Console.WriteLine("глубина скобок ",maxDepth);
else
Console.WriteLine("Строка не корректна, повторите попытку");
Console.ReadKey();
>
private static void GetInput(out string input)
Console.WriteLine("Введите значение");
input = Console.ReadLine();
>
private static void ShowMenu()
Console.WriteLine("1 - Проверить строку");
Console.WriteLine("2 - Выйти");
>
>
>

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *