Поиск подходящих скобок

Question

Так что мой опыт не CS, и я воспринял программирование как хобби. В любом случае мне нужно решить эту проблему: учитывая выражение типа "([])", проверьте, имеет ли это выражение соответствующий стиль скобок, то есть соответствие "[" и соответствие "(".

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

/* Program to check if parens are balanced */

#include <stdio.h>
#include <string.h>

int main(){

  char expr[100] = "[)";

  int roundcounter = 0, squarecounter = 0, i = 0;

  while (expr[i] != '\0') {
    if (expr[i] == '(') {
      roundcounter++;
    }
    else if (expr[i] == ')') {
      roundcounter--;
      if (roundcounter < 0) {
    break;
      }
    }


    if (expr[i] == '[') {
      squarecounter++;
    }
    else if (expr[i] == ']') {
      squarecounter--;
      if (squarecounter < 0) {
    break;
      }
    }

    i++;
  }

  if (roundcounter == 0 && squarecounter == 0) {
    printf("Balanced parenthesis !\n");
  }

  else {
      printf("Unbalaced !\n");      

      /* Error for [ ] */
      if (squarecounter > 0) {
    printf("Missing right square bracket\n");
      }
      else if (squarecounter < 0) {
    printf("Missing left square bracket\n");
      }

      /* Error for ( ) */
      if (roundcounter > 0) {
    printf("Missing right round bracket\n");
      }
      else if (roundcounter < 0) {
    printf("Missing left round bracket\n");
      }
  }
  return 0;
}

В основном, есть два счетчика и каждый ответственный для сравнения () и [] и увеличения (+1), если слева, или уменьшения (-1), если справа. Если счетчики = 0, то у нас есть выражение баланса.

Есть ли лучший способ сделать это «Я думал о создании массива закрытых и открытых символов:

char openarr[] = {'[', '('};
char closenarr[] = {']', ')'};

Но тогда я не уверен, как поступить. Я могу l oop через openarr и сказать, совпадает ли expr [i] с openarr затем увеличьте счетчик и сделайте то же самое для closearr.

Однако нам все еще нужно более 1 счетчика из-за следующего случая. Скажем, у нас есть expr = "[)" и только 1 счетчик, скажем, x.

For loop for openarr will pass because: expr[i] has [ element, counter = 1
For loop for closearr will pass because: expr[i] has ) element, counter = 0

Это, конечно, не так для expr = "[)"

Пожалуйста, дайте мне знать, как это улучшить.

Answer 1

Это не возможно сделать это правильно без стека в той или иной форме. То, как вы это делаете, неправильно справляется с вложениями. Например, он неправильно примет «[(])»

Answer 2

Проблема, с которой вы столкнулись при решении, заключается в том, что вам нужно запомнить порядок, с которым вы столкнулись, в открытых скобках и скобках. Я рекомендую, чтобы у вас был только один счетчик, который вы увеличиваете при встрече с [ или (, и уменьшаете при встрече с ] или ), и у вас есть массив, в котором записывается тип скобок, с которыми вы столкнулись, когда количество было любым ,

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

    char expr[100] = "[([)][]]";
    char brackets[100]; // In a real application, allocate dynamically to the same length as the string
    int bracketCount = 0;
    for (int i = 0 ; i < 100 || expr[i] == '\0' ; ++i)
    {
        if (expr[i] == '[' || expr[i] == '(') 
        {
            // Record the type of *closing* bracket we expect when we get back
            // down to this bracket count
            brackets[bracketCount] = expr[i] == '[' ? ']' : ')';
            bracketCount++;
        }
        else if (expr[i] == ']' || expr[i] == ')')
        {
            bracketCount--;
            if (bracketCount < 0 || brackets[bracketCount] != expr[i] )
            {
                printf("Unmatched\n");
                return 1;
            }
        }
    }
    if (bracketCount > 0)
    {
        printf("Unmatched\n");
        return 1;
    }
    printf("matched\n");
    return 0;

Вот вам: решение без стека в поле зрения ¹ .

¹ ОК Я солгал, он использует стек , Массив brackets и int bracketCount образуют стек.

Answer 3

Как уже было сказано, вам нужен стек, чтобы можно было сопоставить скобки. Идея состоит в том, чтобы поставить sh скобки в ставку, когда их оставляют (если вы получаете [ вы пу sh это, или если вы встречаете левый ( вы пу sh это) Когда вы найдите правильное значение ] или ), затем вы вставляете символ в всплывающее окно стека и смотрите, соответствует ли он тому же типу, который вы встречали ... если они того же типа, то они совпадают, и вы бросаете оба и переходите к следующему. Если в какой-то момент вы попытаетесь выскочить из стека, а стек пуст, или вы дойдете до конца ввода, а в стеке все еще есть какое-то содержимое ... тогда ваши круглые скобки не сбалансированы, и вы получили ошибку. Давайте проверим этот алгоритм со следующим вводом:

[(])

ваш первый символ слева [, так что вы наберете sh его, что даст вам этот стек:

[

когда вы читаете следующий символ, как левый (, вы набираете sh его, получая этот стек:

[(

когда приходит следующий символ, ], вы нажимаете последний символ и получите (, и они не совпадают ... у вас произошел сбой в тот момент ... действительно, это первый символ, который не соответствует.

Давайте попробуем другой пример :

[()]]

сначала вы pu sh [, затем pu sh (, затем вы получаете ) и вы нажимаете (, получая подходящую пару. На этом этапе содержимое стека:

[

, затем вы получаете следующий символ, ], который совпадает с вершиной статка (вы получаете [, оставляя стек пустым). Когда следующий символ прибывает (]), вы выталкиваете стек для совпадения [, но вы получаете, что стек пуст, поэтому вы сигнализируете об ошибке, сообщающей, что на входе есть непарное право ].