Рубрики

Проверьте наличие сбалансированных скобок в выражении

Учитывая строку выражения exp, напишите программу для проверки правильности пар и порядков {, }, (, ), [, ] в exp.

Пример :

Input: exp = “[()]{}{[()()]()}”
Output: Balanced

Input: exp = “[(])”
Output: Not Balanced

Алгоритм:

  • Объявите стек символов S.
  • Теперь пройдитесь по строке выражения exp.
    1. Если текущий символ является стартовой скобкой ( '(' или '{' или '[' )), поместите его в стек.
    2. Если текущий символ является закрывающей скобкой ( ')' или '}' или ']' ), тогда извлекается из стека, и если извлеченный символ является совпадающей стартовой скобкой, то в противном случае круглые скобки не сбалансированы.
  • После полного обхода, если в стеке остается какая-то начальная скобка, то «не сбалансировано»

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C ++

// Программа CPP для проверки сбалансированных скобок.
#include<bits/stdc++.h>

using namespace std;

  
// функция для проверки сбалансированности парантеза

bool areParanthesisBalanced(string expr)

{

    stack<char> s;

    char x;

  

    // Обход выражения

    for (int i=0; i<expr.length(); i++)

    {

        if (expr[i]=='('||expr[i]=='['||expr[i]=='{')

        {

            // Вставить элемент в стек

            s.push(expr[i]);

            continue;

        }

  

        // Если текущий текущий символ не открывается

        // скобка, то она должна закрываться Так укладывают

        // не может быть пустым в этой точке.

        if (s.empty())

           return false;

  

        switch (expr[i])

        {

        case ')':

  

            // Сохраняем верхний элемент в

            x = s.top();

            s.pop();

            if (x=='{' || x=='[')

                return false;

            break;

  

        case '}':

  

            // Сохраняем верхний элемент в b

            x = s.top();

            s.pop();

            if (x=='(' || x=='[')

                return false;

            break;

  

        case ']':

  

            // Сохраняем верхний элемент в c

            x = s.top();

            s.pop();

            if (x =='(' || x == '{')

                return false;

            break;

        }

    }

  

    // Проверяем пустой стек

    return (s.empty());

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    string expr = "{()}[]";

  

    if (areParanthesisBalanced(expr))

        cout << "Balanced";

    else

        cout << "Not Balanced";

    return 0;

}

С

#include<stdio.h>
#include<stdlib.h>
#define bool int

  
/ * структура стекового узла * /

struct sNode

{

   char data;

   struct sNode *next;

};

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data);

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref);

  
/ * Возвращает 1, если символ 1 и символ 2 совпадают слева

   и правая скобка * /

bool isMatchingPair(char character1, char character2)

{

   if (character1 == '(' && character2 == ')')

     return 1;

   else if (character1 == '{' && character2 == '}')

     return 1;

   else if (character1 == '[' && character2 == ']')

     return 1;

   else

     return 0;

}

  
/ * Вернуть 1, если выражение сбалансировано. * /

bool areParenthesisBalanced(char exp[])

{

   int i = 0;

  

   / * Объявить пустой стек символов * /

   struct sNode *stack = NULL;

  

   / * Пройдите указанное выражение, чтобы проверить соответствие круглых скобок * /

   while (exp[i])

   {

      / * Если exp [i] является начальной скобкой, нажмите ее * /

      if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')

        push(&stack, exp[i]);

  

      / * Если exp [i] является конечной скобкой, то выскочить из стека и

          проверить, совпадает ли совпавшая скобка с парой * /

      if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')

      {

              

          / * Если мы видим завершающую скобку без пары, тогда возвращаем false * /

         if (stack == NULL)

           return 0; 

  

         / * Вытолкнуть верхний элемент из стека, если это не пара

            скобка символа, то есть несоответствие.

            Это происходит для выражений типа {(}) * /

         else if ( !isMatchingPair(pop(&stack), exp[i]) )

           return 0;

      }

      i++;

   }

     

   / * Если в выражении что-то осталось, то есть начало

      скобка без закрывающей скобки * /

   if (stack == NULL)

     return 1; / * * Сбалансирован /

   else

     return 0;  / * не сбалансировано * /

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * программа драйвера для проверки вышеуказанных функций * /

int main()

{

  char exp[100] = "{()}[]";

  if (areParenthesisBalanced(exp))

    printf("Balanced \n");

  else

    printf("Not Balanced \n");  

  return 0;

}    

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data)

{

  / * выделить узел * /

  struct sNode* new_node =

            (struct sNode*) malloc(sizeof(struct sNode));

  

  if (new_node == NULL)

  {

     printf("Stack overflow n");

     getchar();

     exit(0);

  }           

  

  / * вставить данные * /

  new_node->data  = new_data;

  

  / * связать старый список с новым узлом * /

  new_node->next = (*top_ref);  

  

  / * переместить голову, чтобы указать на новый узел * /

  (*top_ref)    = new_node;

}

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref)

{

  char res;

  struct sNode *top;

  

  / * Если стек пуст, то ошибка * /

  if (*top_ref == NULL)

  {

     printf("Stack overflow n");

     getchar();

     exit(0);

  }

  else

  {

     top = *top_ref;

     res = top->data;

     *top_ref = top->next;

     free(top);

     return res;

  }

}

Джава

// Java-программа для проверки
// сбалансированная скобка

  

public class BalancedParan 

{

    static class stack 

    {

        int top=-1;

        char items[] = new char[100];

  

        void push(char x) 

        {

            if (top == 99

            {

                System.out.println("Stack full");

            

            else 

            {

                items[++top] = x;

            }

        }

  

        char pop() 

        {

            if (top == -1

            {

                System.out.println("Underflow error");

                return '\0';

            

            else 

            {

                char element = items[top];

                top--;

                return element;

            }

        }

  

        boolean isEmpty() 

        {

            return (top == -1) ? true : false;

        }

    }

      

    / * Возвращает true, если символ1 и символ2

       соответствуют левая и правая скобки * /

    static boolean isMatchingPair(char character1, char character2)

    {

       if (character1 == '(' && character2 == ')')

         return true;

       else if (character1 == '{' && character2 == '}')

         return true;

       else if (character1 == '[' && character2 == ']')

         return true;

       else

         return false;

    }

      

    / * Вернуть true, если выражение сбалансировано

       Круглая скобка * /

    static boolean areParenthesisBalanced(char exp[])

    {

       / * Объявить пустой стек символов * /

       stack st=new stack();

       

       / * Пройдите данное выражение к

          проверить соответствие скобок * /

       for(int i=0;i<exp.length;i++)

       {

            

          / * Если exp [i] является стартовой

            затем поставьте скобку *

          if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')

            st.push(exp[i]);

       

          / * Если exp [i] является конечной скобкой

             затем выскочить из стека и проверить, если

             попсовая скобка - это совпадающая пара * /

          if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')

          {

                   

              / * Если мы видим завершающую скобку без

                 пара затем возвращает ложь * /

             if (st.isEmpty())

               {

                   return false;

               

       

             / * Вытолкнуть верхний элемент из стека, если

                это не парная скобка символа

                тогда есть несоответствие. Это происходит для

                выражения типа {(}) * /

             else if ( !isMatchingPair(st.pop(), exp[i]) )

               {

                   return false;

               }

          }

            

       }

          

       / * Если в выражении что-то осталось

          тогда есть начальная скобка без

          закрывающая скобка * /

        

       if (st.isEmpty())

         return true; / * * Сбалансирован /

       else

         {   / * не сбалансировано * /

             return false;

         

    

      

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    / * программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) 

    {

        char exp[] = {'{','(',')','}','[',']'};

          if (areParenthesisBalanced(exp))

            System.out.println("Balanced ");

          else

            System.out.println("Not Balanced ");  

    }

  
}

python3

# Python3 программа для проверки
# сбалансированная скобка.

  
# функция, чтобы проверить, если
# парантезы сбалансированы

def areParanthesisBalanced(expr) : 

  

    s = []; 

  

    # Обход выражения

    for i in range(len(expr)) :

  

        if (expr[i] == '(' or 

            expr[i] == '[' or expr[i] == '{') :

  

            # Вставить элемент в стек

            s.append(expr[i]); 

            continue

  

        # ЕСЛИ текущий символ не открывается

        # скобка, то она должна закрываться.

        # Таким образом, стек не может быть пустым на этом этапе.

        if (len(s) == 0) :

            return False

  

        if expr[i] == ')' :

  

            # Хранить верхний элемент в

            x = s.pop();

              

            if (x == '{' or x == '[') :

                return False

  

        elif expr[i] == '}'

  

            # Хранить верхний элемент в b

            x = s.pop();

              

            if (x == '(' or x == '[') :

                return False

          

        elif x == ']'

  

            # Хранить верхний элемент в c

            x = s.pop();

              

            if (x =='(' or x == '{') :

                return False

  

    # Проверьте пустой стек

    if len(s) :

        return True

    else :

        return False

  
Код водителя

if __name__ == "__main__"

  

    expr = "{()}[]"

  

    if (areParanthesisBalanced(expr)) :

        print("Balanced"); 

    else :

        print("Not Balanced"); 

  
# Этот код предоставлен AnkitRai01

C #

// C # программа для проверки
// сбалансированная скобка

using System;

using System.Collections.Generic; 

      

public class BalancedParan 

{

    public class stack 

    {

        public int top=-1;

        public char []items = new char[100];

  

        public void push(char x) 

        {

            if (top == 99) 

            {

                Console.WriteLine("Stack full");

            

            else

            {

                items[++top] = x;

            }

        }

  

        char pop() 

        {

            if (top == -1) 

            {

                Console.WriteLine("Underflow error");

                return '\0';

            

            else

            {

                char element = items[top];

                top--;

                return element;

            }

        }

  

        Boolean isEmpty() 

        {

            return (top == -1) ? true : false;

        }

    }

      

    / * Возвращает true, если символ1 и символ2

    соответствуют левая и правая скобки * /

    static Boolean isMatchingPair(char character1, char character2)

    {

        if (character1 == '(' && character2 == ')')

            return true;

        else if (character1 == '{' && character2 == '}')

            return true;

        else if (character1 == '[' && character2 == ']')

            return true;

        else

            return false;

    }

      

    / * Вернуть true, если выражение сбалансировано

    Круглая скобка * /

    static Boolean areParenthesisBalanced(char []exp)

    {

        / * Объявить пустой стек символов * /

        Stack<char> st = new Stack<char>();

          

        / * Пройдите данное выражение к

            проверить соответствие скобок * /

        for(int i = 0; i < exp.Length; i++)

        {

                  

            / * Если exp [i] является стартовой

                затем поставьте скобку *

            if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')

                st.Push(exp[i]);

          

            / * Если exp [i] является конечной скобкой

                затем выскочить из стека и проверить, если

                попсовая скобка - это совпадающая пара * /

            if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']')

            {

                      

                / * Если мы видим завершающую скобку без

                    пара затем возвращает ложь * /

                if (st.Count == 0)

                {

                    return false;

                

          

                / * Вытолкнуть верхний элемент из стека, если

                    это не парная скобка символа

                    тогда есть несоответствие. Это происходит для

                    выражения типа {(}) * /

                else if ( !isMatchingPair(st.Pop(), exp[i]) )

                {

                    return false;

                }

            }

                  

        }

              

        / * Если в выражении что-то осталось

            тогда есть начальная скобка без

            закрывающая скобка * /

              

        if (st.Count == 0)

            return true; / * * Сбалансирован /

        else

        { / * не сбалансировано * /

            return false;

        

    

      

    / * ПОЛЕЗНЫЕ ФУНКЦИИ * /

    / * программа драйвера для проверки вышеуказанных функций * /

    public static void Main(String[] args) 

    {

        char []exp = {'{','(',')','}','[',']'};

        if (areParenthesisBalanced(exp))

            Console.WriteLine("Balanced ");

        else

            Console.WriteLine("Not Balanced "); 

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

Balanced

Сложность времени: O (n)
Вспомогательное пространство: O (n) для стека.

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в приведенных выше кодах / алгоритмах, или найдете другие способы решения той же проблемы.

Рекомендуемые посты:

Проверьте наличие сбалансированных скобок в выражении

0.00 (0%) 0 votes