Рубрики

Структуры данных | Разное | Вопрос 4

Лучшей структурой данных для проверки того, имеет ли арифметическое выражение сбалансированные скобки, является (GATE CS 2004)

(A) очередь
(B) стек
(С) дерево
(D) список

Ответ: (Б)
Объяснение: в скобках есть три типа [] {} (). Ниже приведен сегмент кода произвольного c, который содержит круглые скобки всех трех типов.

void func(int c, int a[])

{

   return  ((c +2)  + arr[(c-2)]) ; 

}

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

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

bool areParenthesesBalanced(expression )

   for each character in expression

   {

      if(character == ’(’ || character == ’{’ || character == ’[’) 

        push(stack, character);

      if(character == ’)’ || character == ’}’ || character == ’]’) 

      {

         if(isEmpty(stack))  

           return 0; / * Мы видим правильную скобку

                       без левой пары * /

  

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

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

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

         else if (! isMatchingPair(pop(stack), character) ) 

           return 0;   

      }

   }

    

   if(isEmpty(stack))

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

   else  

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

} / * Конец функции для проверки скобок * /

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

   и правильные скобки * /

bool isMatchingPair(character1, character2)

{

   if(character1 == ‘(‘ && character2 == ‘)’)

     return 1;

   else If(character1 == ‘{‘ && character2 == ‘}’)

     return 1;

   else If(character1 == ‘[‘ && character2 == ‘]’)

     return 1;

   else 

     return 0;

}

Тест на этот вопрос

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

Структуры данных | Разное | Вопрос 4

0.00 (0%) 0 votes