Подтверждение инфиксной записи возможно с использованием регулярных выражений - PullRequest
Новая
       20

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

0 голосов
/ 27 апреля 2011

Я думаю о проверке инфиксной записи, которая состоит из алфавитов в качестве операндов и +-*/$ в качестве операторов [например: A+B-(C/D)$(E+F)] с использованием регулярных выражений в Java.Есть ли лучший способ?Есть ли шаблон регулярных выражений, который я могу использовать?

Ответы [ 3 ]

0 голосов
/ 27 апреля 2011

Вы, вероятно, могли бы сделать это с помощью рекурсивного PCRE ... но это может быть PITA.

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

определяют некоторые правила, например:

  • оператор допускается только в том случае, если на нем есть алфавитвершина стека
  • алфавит или круглые скобки допускаются только в том случае, если на вершине стека есть оператор
  • все разрешено, если стек пуст

затем:

  • если вы встретите закрывающие скобки, удалите все до открывающих скобок.
  • если вы встретите алфавит, удалите выражение

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

или что-то в этом роде.

0 голосов
/ 27 апреля 2011

Я не знаком с синтаксисом языка infix, но вы, безусловно, можете выполнить проверку первого прохода, которая просто проверяет, что все символы в строке являются действительными (т.е. допустимые символы = A-Z, +, -, *, /, $, ( и )). Вот Java-программа, которая проверяет допустимые символы, а также включает функцию, которая проверяет несбалансированные (возможно, вложенные) скобки: 

import java.util.regex.*;
public class TEST {
    public static void main(String[] args) {
        String s = "A+B-(C/D)$(E+F)";
        Pattern regex = Pattern.compile(
            "# Verify that a string contains only specified characters.\n" +
            "^                # Anchor to start of string\n" +
            "[A-Z+\\-*/$()]+  # Match one or more valid characters\n" +
            "$                # Anchor to end of string\n",
            Pattern.COMMENTS);
        Matcher m = regex.matcher(s);
        if (m.find()) {
            System.out.print("OK: String has only valid characters.\n");
        } else {
            System.out.print("ERROR: String has invalid characters.\n");
        }
        // Verify the string contains only balanced parentheses.
        if (checkParens(s)) {
            System.out.print("OK: String has no unbalanced parentheses.\n");
        } else {
            System.out.print("ERROR: String has unbalanced parentheses.\n");
        }
    }
    // Function checks is string contains any unbalanced parentheses.
    public static Boolean checkParens(String s) {
        Pattern regex = Pattern.compile("\\(([^()]*)\\)");
        Matcher m = regex.matcher(s);
        // Loop removes matching nested parentheses from inside out.
        while (m.find()) {
            s = m.replaceFirst(m.group(1));
            m.reset(s);
        }
        regex = Pattern.compile("[()]");
        m = regex.matcher(s);
        // Check if there are any erroneous parentheses left over.
        if (m.find()) {
            return false;   // String has unbalanced parens.
        }
        return true;        // String has balanced parens.
    }
}

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

0 голосов
/ 27 апреля 2011

Возможно, это слишком много, но вы можете рассмотреть возможность использования полноценного генератора синтаксического анализатора, такого как ANTLR (http://www.antlr.org/).. С помощью ANTLR вы можете создавать правила, которые будут автоматически генерировать для вас код Java. Предполагая, что во входных данных есть только действительные символы, является проблемой синтаксического анализа, в противном случае вы захотите сначала проверить поток символов с помощью лексического анализа.

Для синтаксического анализа у вас могут быть такие правила, как: 

PLUS : '+' ;
etc...

expression:
         term ( ( PLUS | MINUS | MULTIPLY | DIVIDE )^ term )*
      ;
term:
    constant
  | OPENPAREN! expression CLOSEPAREN!
  ;

С постоянными целыми числами / действительными значениями. Если сгенерированный ANTLR код синтаксического анализатора не может сопоставить ввод с вашими правилами синтаксического анализа, он выдаст исключение, чтобы вы могли определить, является ли код действительным.

...