План курса / Все задачи / Алгоритмы и структуры данных
Сбалансированные скобки
легко
# решено
Дана строка s, содержащая символы (, ), {, }, [, ] и символы латинского алфавита. Нужно определить, является ли строка sправильной.
Строка считается правильной, если:
Каждая открытая скобка имеет соответствующую закрывающую скобку того же типа.
Скобки закрываются в правильном порядке.
Символы латинского алфавита не влияют на правильность строки.
Пример 1:
Ввод: s = "Algo[[(C)od]]{e}the({Best}{[Pla]t}f)orm"
Вывод: true
Пример 2:
Ввод: s = "[]()))"
Вывод: false
Пример 3:
Ввод: s = "((()"
Вывод: false
Ограничения:
len(s) >= 1
public class Solution
{
public static bool IsBalanced(string s)
{
Stack<char> stack = new Stack<char>();
Dictionary<char, char> pairs = new Dictionary<char, char>
{
{ '{', '}' },
{ '(', ')' },
{ '[', ']' }
};
foreach (char charElem in s)
{
if (charElem != '{' && charElem != '[' && charElem != '(' &&
charElem != '}' && charElem != ']' && charElem != ')')
{
// Пропускаем все латинские символы, потому что они не влияют на результат
continue;
}
if (pairs.ContainsKey(charElem))
{
// Если скобка открытая - просто добавляем в стек
stack.Push(charElem);
continue;
}
// Перед нами закрывающаяся скобка, но стек пуст
if (stack.Count == 0)
{
return false;
}
// Удаляем последний элемент из стека
char lastChar = stack.Pop();
// Проверяем, что последний элемент в стеке и текущий образуют пару
// Если пару не образуют, то возвращаем false
if (pairs[lastChar] != charElem)
{
return false;
}
}
// Если стек пуст, значит все скобки сбалансированы
return stack.Count == 0;
}
}
#include <stack>
#include <unordered_map>
#include <string>
using namespace std;
bool isBalanced(const string& s) {
stack<char> stack;
unordered_map<char, char> pairs = {{'{', '}'}, {'(', ')'}, {'[', ']'}};
for (char charElem : s) {
if (charElem != '{' && charElem != '[' && charElem != '(' && charElem != '}' && charElem != ']' && charElem != ')') {
// Пропускаем все латинские символы, потому что они не влияют на результат
continue;
}
if (pairs.count(charElem)) {
// если скобка открытая - просто добавляем в стек
stack.push(charElem);
continue;
}
// перед нами закрывающаяся скобка, но стек пуст
if (stack.empty()) {
return false;
}
// удаляем последний элемент из стека
char lastChar = stack.top();
stack.pop();
// проверяем, что последний элемент в стеке и текущий образуют пару
// если пару не образуют, то вернем False
if (pairs[lastChar] != charElem) {
return false;
}
}
return stack.empty();
}
package main
func isBalanced(s string) bool {
stack := []rune{}
pairs := map[rune]rune{'{': '}', '(': ')', '[': ']'}
for _, char := range s {
if char != '{' && char != '[' && char != '(' && char != '}' && char != ']' && char != ')' {
// Пропускаем все латинские символы, потому что они не влияют на результат
continue
}
if _, exists := pairs[char]; exists {
// если скобка открытая - просто добавляем в стек
stack = append(stack, char)
continue
}
// перед нами закрывающаяся скобка, но стек пуст
if len(stack) == 0 {
return false
}
// удаляем последний элемент из стека
lastChar := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// проверяем, что последний элемент в стеке и текущий образуют пару
// если пару не образуют, то вернем False
if pairs[lastChar] != char {
return false
}
}
return len(stack) == 0
}
import java.util.Stack;
import java.util.HashMap;
class Solution {
public boolean isBalanced(String s) {
Stack<Character> stack = new Stack<>();
HashMap<Character, Character> pairs = new HashMap<>();
pairs.put('{', '}');
pairs.put('(', ')');
pairs.put('[', ']');
for (char charElem : s.toCharArray()) {
if (charElem != '{' && charElem != '[' && charElem != '(' && charElem != '}' && charElem != ']' && charElem != ')') {
// Пропускаем все латинские символы, потому что они не влияют на результат
continue;
}
if (pairs.containsKey(charElem)) {
// если скобка открытая - просто добавляем в стек
stack.push(charElem);
continue;
}
// перед нами закрывающаяся скобка, но стек пуст
if (stack.isEmpty()) {
return false;
}
// удаляем последний элемент из стека
char lastChar = stack.pop();
// проверяем, что последний элемент в стеке и текущий образуют пару
// если пару не образуют, то вернем False
if (pairs.get(lastChar) != charElem) {
return false;
}
}
return stack.isEmpty();
}
}
from typing import *
def is_balanced(s: str) -> bool:
stack = []
pairs = {'{':'}', '(':')', '[':']'}
for char in s:
if char not in {'{','[','(','}',']',')'}:
# пропускаем все латинские символы, потому что они не влияют на
# результат
continue
if char in pairs:
# если скобка открытая - просто добавляем в стек
stack.append(char)
continue
# перед нами закрывающаяся скобка, но стек пуст
if len(stack) == 0:
return False
# удаляем последний элемент из стека
lastChar = stack.pop()
# проверяем что последний элемент в стеке и текущий образуют пару
# если пару не образуют, то вернем False
if pairs[lastChar] != char:
return False
return len(stack) == 0
export function isBalanced(s) {
let stack = [];
const pairs = {'{': '}', '(': ')', '[': ']'};
for (let char of s) {
if (!('{}[]()'.includes(char))) {
// пропускаем все латинские символы, потому что они не влияют на
// результат
continue;
}
if (char in pairs) {
// если скобка открытая - просто добавляем в стек
stack.push(char);
continue;
}
// перед нами закрывающаяся скобка, но стек пуст
if (stack.length === 0) {
return false;
}
// удаляем последний элемент из стека
let lastChar = stack.pop();
// проверяем что последний элемент в стеке и текущий образуют пару
// если пару не образуют, то вернем False
if (pairs[lastChar] !== char) {
return false;
}
}
return stack.length === 0;
}