хорошо сбалансированное и правильно написанное выражение

Question

у меня есть строка (char * ch) с круглыми скобками, и я должен:

1) проверить, правильно ли написана строка и правильно ли она сбалансирована, например: "(())" правильно написанои хорошо сбалансирован, в то время как ") ()" ни хорошо написано, ни хорошо сбалансировано

2) возвращает позицию первой круглой скобки, которая отклоняется от этого правила, если строка написана плохо и плохо сбалансирована.

на первый вопрос, все в порядке.мой код, как показано ниже:

int WBalanced(char *ch)
{
    stack p; int i;

 for (i=0; i<strlen(ch);i++) 
  {

    if(ch[i] == '(')
    {
        addStack(P, ch[i]);
    else if(ch[i] == ')') 
      {
        if(stackEmpty(P) == 0) 
            unstack(P);
        else
            return (0);
       }
     }
   }



 if(stackEmpty(P)==1) 
    return (0);
 else
    return (1);

} 

, но по второму вопросу я не очень хорошо понимаю вопрос.если моей строкой является «(()», является ли позиция позицией второй скобки? и если моей строкой является «(() (« какова позиция отклоненной скобки?

спасибо запомощь

Answer 1

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

Если наступает конец строки и уровень не равен нулю, укажите на это место (возможно) как неполное выражение.

Answer 2

спасибо за ваши ответы.использование счетчика - неплохая идея, но в этом случае оно может быть функциональным "(()" и не функциональным в этом случае "((() (" ...: (

Answer 3

Используя стек в качестве реализации для проверки баланса в скобках, решение должно быть:

Сначала, при условии, что индексирование начинается с 0. Stack.top = -1 (указывает, что в стек не вставлены скобки),Мы запускаем наш алгоритм от 1-й левой круглой скобки (индекс 0) до конечной круглой скобки.fault_index = -1 (используется для вывода, какая скобка является ошибочной)

1. Если встречается '(' -> вставить в стек. Stack.top + = 1 и fault_index = индекс этой скобкив данной строке (fault_index должен быть установлен только когда стек вставлен перед вставкой этой круглой скобки)

2. Если встречается ')' -> удалить '(' из стека. Stack.top -= 1.

Мы останавливаемся, когда возникает любое из этих условий, и должны предпринять соответствующее действие:

1. Когда строка пуста:

   а. Если стек пуст -> Строковые скобки были сбалансированы.

   б. Если стек не пуст -> Ошибка находится по адресу fault_index

2. При обнаружениидополнительный ')', т. е. когда стек пуст и получил эту скобку, этот индекс является fault_index.