регулярное выражение для схемы вида ввода

Question

Я пишу Java-программу, которая будет действовать на входе, который будет иметь вид схемы

языка.

Что-то вроде

(+ (+ a b))

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

Answer 1

Регулярные выражения не могут соединять скобки на произвольную глубину. Синтаксис схемы не является регулярным.

http://en.wikipedia.org/wiki/Regular_language#The_number_of_words_in_a_regular_language

Таким образом, нерегулярность некоторого языка L 'может быть доказана путем подсчета слов в L'. Рассмотрим, например, язык Дейка для строк сбалансированных скобок. Количество слов длины 2n в языке Дейка равно каталонскому числу ..., которое не имеет формы p (n) λn, что свидетельствует о нерегулярности языка Дейка.

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

Для простого языка с пробелами в скобках и идентификаторами, сделанными из повторений буквы «а», вы можете сделать

Patter token = Pattern.compile("[() ]|a+|.", Pattern.DOT_ALL);
Matcher m = token.matcher(sourceCode);
int parenDepth = 0;
while (m.find()) {
  char ch = m.group().charAt(0);
  switch (ch) {
    case '(':
      ++parenDepth;
      break;
    case ')':
      if (parenDepth == 0) {
        fail("Too many close parens");
      }
      --parenDepth;
      break;
  }
}
if (parenDepth != 0) {
  fail(parenDepth + " unclosed lists");
}