парсинг с рекурсией - скобки

Не могли бы некоторые подсказать мне эту проблему: выражение правильно, только если оно содержит правильно закрытые круглые и фигурные скобки и не содержит других символов, даже пробела. Например, () ({} () ({})) является правильным выражением, тогда как ({)} не является правильным выражением или {} ({})). Пустое выражение (не содержащее ни одного символа) является правильным. Учитывая строковое выражение, определите, являются ли выражения правильными, и если да, то определите максимальный уровень вложенности. Максимальный уровень вложенности скобок равен максимальному количеству друг друга.

Примеры {}({}){{((({}))}} ответ : 5

{}({})) -1 (поскольку выражение неверно)

Это то, что я сделал до сих пор.

#include <stdio.h>
#include <stdlib.h>

FILE *fi, *fo;
int first, er;

void X();
void Y();

void S() {
    X();
    Y();
}
void X() {
    if(first=='{') {
        first=fgetc(fi);
        X();
        if(first=='}')
            first=fgetc(fi);
        else
            er=1;
        S();
    }
}
void Y() {
    if(first=='(') {
        first=fgetc(fi);
        Y();
        if(first==')')
            first=fgetc(fi);
        else
            er=1;
        S();
    }
}
int main()
{
    fi = fopen("brackets.in","r");
    fo = fopen("brackets.out","w");
    first=fgetc(fi);
    S();
    if(first!='\n')
        er=-1;
    fprintf(fo,"%d",er);
    fclose(fi);
    fclose(fo);
    return 0;
}

c parsing recursion brackets
person riic2000    schedule 16.12.2014    source источник
comment
Используйте переменную stack data structure и max_nesting. Продолжайте нажимать все открытые скобки, пока не найдете закрывающие скобки. Как только вы получите закрывающую скобку, обновите max_nesting. Если она больше, чем предыдущее значение, обновите max_nesting.   -  person Ankur    schedule 16.12.2014
comment
Я не могу использовать дополнительную память. Память должна быть O (1). Решение должно быть с разбором   -  person riic2000    schedule 16.12.2014
comment
@riic2000 riic2000 мы собирались собрать O(n) решение для динамического программирования.   -  person IdeaHat    schedule 16.12.2014
comment
riic2000, я скептически отношусь к тому, что вам нужно решать это за O(1) дополнительной памяти. Насколько я могу судить, это невозможно сделать, потому что вам нужно каким-то образом поддерживать состояние, а состояние должно отслеживать, в каком порядке были открыты фигурные скобки, чтобы проверить порядок закрытия, и это O (n). Даже если вы используете для этого саму строку, это все равно O(n) памяти.   -  person OmnipotentEntity    schedule 16.12.2014
comment
Вот что он говорит, память должна быть O (1)...   -  person riic2000    schedule 16.12.2014
comment
Я с @OmnipotentEntity - я не верю, что это можно сделать только с O(1) памятью. Даже решение типа синтаксического анализатора с рекурсивным спуском должно будет использовать дополнительную память, линейно связанную с максимальным уровнем вложенности, даже если она не выделена явно (т.е. рекурсивные вызовы требуют дополнительных кадров стека)... Теперь, может быть, если бы ввод пришел в виде строки , а не по символу, вы можете использовать саму строку и стирания, чтобы избежать дополнительной памяти, но, похоже, это не так...   -  person twalberg    schedule 16.12.2014
comment
Я не понимаю ограничение и никаких других символов, даже пробел. Ваш пример () ({} () ({})) содержит пробелы во втором наборе ().   -  person Weather Vane    schedule 16.12.2014

Ответы (1)


arrow_upward
2
arrow_downward

Во-первых, это помогает думать о вашей проблеме как о формальной грамматике.

S = The Language you are testing for

S->
  NUL    // Empty   
  SS     // S followed by itself.   
  [ S ]  // Case 1   
  ( S )  // Case 2   
  { S }  // Case 3

Так как эта грамматика имеет только один символ (S), вам нужен только один метод синтаксического анализа.

Следующий код неполный, но, надеюсь, он передает идею.

char curr_char;

int main (void)
{
  curr_char = getc();
  result = parse_s();
  return 0;
}

// Parse the S pattern off input.  When this method completes, curr_char points to the character AFTER S.
// Returns recursion count or -1 on fail.
int parse_s()
{
  max_count = 0;
  while(true)
  {
    int curr_count = 0;
    switch 'curr_char':
    {
      case '[': // [
        int count = parse_s(); // S
        if (count == -1) return -1;  // The S must be valid
        if (curr_char != ']') return -1;  // ]
        curr_char = getc();  // Advance past the ]
        curr_count = count + 1;  // This expression is 1 nest greater than its contained S
      break;

      case '(':
        // XXX
      break;

      case '{':
        // XXX
      break;

      default:
        // This is either the SS (find the max of the two), the NUL case (return 0), or an error (return -1)
      break;
    }
    // In the SS case you're gonna have to loop and do something here.
  }
  return max_count;
}
person QuestionC    schedule 16.12.2014
comment
Эй, я вернулся. Я использовал вашу модель, но не могу найти, как изменить следующий код, потому что он отображает количество скобок и скобок вместо максимальной степени имбрикации. Я вставлю код в пост, чтобы вам было лучше видно - person riic2000; 21.12.2014