Junior Proger

Готовые решения

Программа определения правильности последовательности скобок

В мире программирования и анализа текстов среди нас могут скрываться различные задачи, одной из которых является определение правильности последовательности скобок. Данная задача возникает во множестве контекстов: от проверки синтаксиса программного кода до анализа математических выражений и текстовых данных. Эффективное решение этой задачи имеет критическое значение для обеспечения корректной работы программ и безопасности данных. В этой статье мы рассмотрим реализацию программы определения правильности последовательности скобок.

Теория

Алгоритм для определения правильности последовательности скобок, таких как круглые «()», квадратные «[]» и фигурные «{}», можно реализовать с использованием стека (stack). Вот общий алгоритм проверки:

  • Создайте пустой стек, который будет служить для отслеживания открывающих скобок.
  • Перебирайте каждый символ в последовательности слева направо.
  • Если текущий символ — открывающая скобка («(«, «[«, или «{«), поместите его в стек.
  • Если текущий символ — закрывающая скобка («)«, «]«, или «}«), выполните следующие действия:
  • Проверьте, если стек пуст. Если стек пуст, это означает, что нет соответствующей открывающей скобки, и последовательность недействительна. Верните False.
  • Иначе, извлеките верхний элемент из стека и проверьте, соответствует ли он текущей закрывающей скобке. Если нет, верните False.
  • После перебора всего выражения, проверьте, пуст ли стек. Если стек пуст, то последовательность правильна, иначе она недействительна.
  • Верните True, если стек пуст, и False, если в стеке остались непарные открывающие скобки.

C++

Для определения, является ли данная последовательность правильной, содержащей только круглые, квадратные и фигурные скобки, вы можете использовать стек (stack) в C++. Стек поможет вам проверить правильность пар скобок и их вложенность. Пример программы:

#include <iostream>
#include <stack>
#include <string>

bool isBalanced(const std::string& expression) {
    std::stack<char> stack;

    for (char bracket : expression) {
        if (bracket == '(' || bracket == '[' || bracket == '{') {
            // Если это открывающая скобка, помещаем ее в стек
            stack.push(bracket);
        } else if (bracket == ')' || bracket == ']' || bracket == '}') {
            // Если это закрывающая скобка, проверяем соответствие
            if (stack.empty()) {
                return false; // Нет соответствующей открывающей скобки
            }
            char top = stack.top();
            stack.pop();
            if ((bracket == ')' && top != '(') ||
                (bracket == ']' && top != '[') ||
                (bracket == '}' && top != '{')) {
                return false; // Скобки не соответствуют друг другу
            }
        }
    }

    return stack.empty(); // Если стек пуст в конце, скобки сбалансированы
}

int main() {
    std::string expression;
    std::cout << "Введите последовательность скобок: ";
    std::cin >> expression;

    if (isBalanced(expression)) {
        std::cout << "Правильная последовательность скобок" << std::endl;
    } else {
        std::cout << "Неправильная последовательность скобок" << std::endl;
    }

    return 0;
}

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

C#

using System;
using System.Collections.Generic;

class BracketChecker
{
    public static bool IsBalanced(string expression)
    {
        Stack<char> stack = new Stack<char>();

        foreach (char bracket in expression)
        {
            if (IsOpenBracket(bracket))
            {
                stack.Push(bracket);
            }
            else
            {
                if (stack.Count == 0)
                    return false; // Нет соответствующей открывающей скобки

                char top = stack.Pop();
                if (!AreMatchingBrackets(top, bracket))
                    return false; // Скобки не соответствуют друг другу
            }
        }

        return stack.Count == 0; // Если стек пуст в конце, скобки сбалансированы
    }

    public static bool IsOpenBracket(char bracket)
    {
        return bracket == '(' || bracket == '[' || bracket == '{';
    }

    public static bool AreMatchingBrackets(char open, char close)
    {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }

    static void Main(string[] args)
    {
        Console.Write("Введите последовательность скобок: ");
        string expression = Console.ReadLine();

        if (IsBalanced(expression))
        {
            Console.WriteLine("Правильная последовательность скобок");
        }
        else
        {
            Console.WriteLine("Неправильная последовательность скобок");
        }
    }
}

Python

using System;
using System.Collections.Generic;

class BracketChecker
{
    public static bool IsBalanced(string expression)
    {
        Stack<char> stack = new Stack<char>();

        foreach (char bracket in expression)
        {
            if (IsOpenBracket(bracket))
            {
                stack.Push(bracket);
            }
            else
            {
                if (stack.Count == 0)
                    return false; // Нет соответствующей открывающей скобки

                char top = stack.Pop();
                if (!AreMatchingBrackets(top, bracket))
                    return false; // Скобки не соответствуют друг другу
            }
        }

        return stack.Count == 0; // Если стек пуст в конце, скобки сбалансированы
    }

    public static bool IsOpenBracket(char bracket)
    {
        return bracket == '(' || bracket == '[' || bracket == '{';
    }

    public static bool AreMatchingBrackets(char open, char close)
    {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }

    static void Main(string[] args)
    {
        Console.Write("Введите последовательность скобок: ");
        string expression = Console.ReadLine();

        if (IsBalanced(expression))
        {
            Console.WriteLine("Правильная последовательность скобок");
        }
        else
        {
            Console.WriteLine("Неправильная последовательность скобок");
        }
    }
}

Java

import java.util.Stack;

public class BracketChecker {
    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        String openingBrackets = "([{";
        String closingBrackets = ")]}";

        for (char bracket : expression.toCharArray()) {
            if (openingBrackets.contains(String.valueOf(bracket))) {
                stack.push(bracket);
            } else if (closingBrackets.contains(String.valueOf(bracket))) {
                if (stack.isEmpty()) {
                    return false; // Нет соответствующей открывающей скобки
                }
                char top = stack.pop();
                if (!areMatchingBrackets(top, bracket)) {
                    return false; // Скобки не соответствуют друг другу
                }
            }
        }

        return stack.isEmpty(); // Если стек пуст в конце, скобки сбалансированы
    }

    public static boolean areMatchingBrackets(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '[' && close == ']') ||
               (open == '{' && close == '}');
    }

    public static void main(String[] args) {
        System.out.print("Введите последовательность скобок: ");
        String expression = System.console().readLine();

        if (isBalanced(expression)) {
            System.out.println("Правильная последовательность скобок");
        } else {
            System.out.println("Неправильная последовательность скобок");
        }
    }
}

Pascal

program BracketChecker;

uses SysUtils;

function IsBalanced(expression: string): Boolean;
var
  stack: string;
  i: Integer;
begin
  stack := '';
  for i := 1 to Length(expression) do
  begin
    if (expression[i] = '(') or (expression[i] = '[') or (expression[i] = '{') then
      stack := stack + expression[i]
    else if (expression[i] = ')') or (expression[i] = ']') or (expression[i] = '}') then
    begin
      if Length(stack) = 0 then
      begin
        Result := False; // Нет соответствующей открывающей скобки
        Exit;
      end;
      if (expression[i] = ')') and (stack[Length(stack)] = '(') then
        Delete(stack, Length(stack), 1)
      else if (expression[i] = ']') and (stack[Length(stack)] = '[') then
        Delete(stack, Length(stack), 1)
      else if (expression[i] = '}') and (stack[Length(stack)] = '{') then
        Delete(stack, Length(stack), 1)
      else
      begin
        Result := False; // Скобки не соответствуют друг другу
        Exit;
      end;
    end;
  end;

  Result := Length(stack) = 0; // Если стек пуст в конце, скобки сбалансированы
end;

var
  expression: string;
begin
  Write('Введите последовательность скобок: ');
  ReadLn(expression);

  if IsBalanced(expression) then
    WriteLn('Правильная последовательность скобок')
  else
    WriteLn('Неправильная последовательность скобок');
end.

JavaScript

function isBalanced(expression) {
    const stack = [];
    const brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (let i = 0; i < expression.length; i++) {
        if ('([{'.includes(expression[i])) {
            stack.push(expression[i]);
        } else if (')]}'.includes(expression[i])) {
            if (stack.length === 0) {
                return false; // Нет соответствующей открывающей скобки
            }
            const top = stack.pop();
            if (brackets[expression[i]] !== top) {
                return false; // Скобки не соответствуют друг другу
            }
        }
    }

    return stack.length === 0; // Если стек пуст в конце, скобки сбалансированы
}

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question("Введите последовательность скобок: ", function (expression) {
    if (isBalanced(expression)) {
        console.log("Правильная последовательность скобок");
    } else {
        console.log("Неправильная последовательность скобок");
    }
    rl.close();
});

PHP

<?php

function isBalanced($expression) {
    $stack = [];
    $brackets = [
        ')' => '(',
        ']' => '[',
        '}' => '{'
    ];

    for ($i = 0; $i < strlen($expression); $i++) {
        $char = $expression[$i];
        if (in_array($char, ['(', '[', '{'])) {
            array_push($stack, $char);
        } elseif (in_array($char, [')', ']', '}'])) {
            if (empty($stack)) {
                return false; // Нет соответствующей открывающей скобки
            }
            $top = array_pop($stack);
            if ($brackets[$char] !== $top) {
                return false; // Скобки не соответствуют друг другу
            }
        }
    }

    return empty($stack); // Если стек пуст в конце, скобки сбалансированы
}

if (isset($_POST['expression'])) {
    $expression = $_POST['expression'];
    if (isBalanced($expression)) {
        echo "Правильная последовательность скобок";
    } else {
        echo "Неправильная последовательность скобок";
    }
}
?>

<!DOCTYPE html>
<html>
<head>
    <title>Проверка скобок</title>
</head>
<body>
    <form method="POST">
        <label>Введите последовательность скобок: </label>
        <input type="text" name="expression">
        <input type="submit" value="Проверить">
    </form>
</body>
</html>

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
Давайте поможем друг другу! Если вы нашли ошибку или хотите предложить лучшее решение, пожалуйста, напишите об этом в комментариях.

Может быть полезно

Готовые решения

База данных Access Библиотека

Готовые решения

Программа «Морской бой»

Готовые решения

Программа проверки, состоит ли число из одинаковых цифр

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

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