Рекурсивная замена регулярным выражением Java?

Question

я могу заменить ABC(10,5) с (10)%(5) помощью:

replaceAll("ABC\\(([^,]*)\\,([^,]*)\\)", "($1)%($2)") 

, но я не могу понять, как это сделать для ABC(ABC(20,2),5) или ABC(ABC(30,2),3+2).

Если я могу конвертировать в ((20)%(2))%5, как я могу преобразовать обратно в ABC(ABC(20,2),5)?

Спасибо, J

Answer 1

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

String termString = "([0-9+\\-*/()%]*)"; 
    String pattern = "ABC\\(" + termString + "\\," + termString + "\\)"; 
    String [] strings = {"ABC(10,5)", "ABC(ABC(20,2),5)", "ABC(ABC(30,2),3+2)"}; 
    for (String str : strings) { 
     while (true) { 
      String replaced = str.replaceAll(pattern, "($1)%($2)"); 
      if (replaced.equals(str)) { 
       break; 
      } 
      str = replaced; 
     } 
     System.out.println(str); 
    } 

Я предполагаю, что вы пишете для синтаксического анализа числовых выражений, таким образом, определение термина termString = "([0-9+\\-*/()%]*)". Он выводит это:

(10)%(5) 
((20)%(2))%(5) 
((30)%(2))%(3+2) 

EDIT По желанию ОП я добавить код для декодирования строк.Это немного больше, чем Hacky вперед сценария:

String [] encoded = {"(10)%(5)", "((20)%(2))%(5)", "((30)%(2))%(3+2)"}; 
    String decodeTerm = "([0-9+\\-*ABC\\[\\],]*)"; 
    String decodePattern = "\\(" + decodeTerm + "\\)%\\(" + decodeTerm + "\\)"; 
    for (String str : encoded) { 
     while (true) { 
      String replaced = str.replaceAll(decodePattern, "ABC[$1,$2]"); 
      if (replaced.equals(str)) { 
       break; 
      } 
      str = replaced; 
     } 
     str = str.replaceAll("\\[", "("); 
     str = str.replaceAll("\\]", ")"); 
     System.out.println(str); 
    } 

И выход:

ABC(10,5) 
ABC(ABC(20,2),5) 
ABC(ABC(30,2),3+2) 

Answer 2

Вы можете попытаться переписать строку, используя польскую нотацию, а затем заменить любой % X Y с ABC (X, Y).

Here - ссылка на wiki для польской нотации.

Проблема в том, что вам нужно выяснить, какая переписывание ABC (X, Y) произошло первым, когда вы рекурсивно заменили их в своей строке. Польская нотация полезна для «расшифровки» порядка, в котором эти перезаписи встречаются и широко используется в оценке выражений.

Вы можете сделать это, используя стек и запись, которые были заменены в первую очередь: найдите самый внутренний набор скобок, нажмите только это выражение в стек, а затем удалите это из своей строки. Если вы хотите восстановить оригинальное выражение выражения, просто запустите его в верхней части стека и примените обратное преобразование (X)% (Y) ->ABC (X, Y).

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

Короче говоря, при замене начинайте с самых внутренних терминов (те, у которых в них нет скобок) и примените обратную замену.

Это может быть полезно использовать (X)% (Y) ->АВС {X, Y} в качестве промежуточного правила перезаписи, а затем переписать фигурные скобки в круглых скобках. Таким образом, будет легче определить, что является самым внутренним термином, поскольку новые термины не будут использовать круглые скобки. Также его проще реализовать, но не так элегантно.

Answer 3

Вы можете начать оценивать внутренние наиболее reducable выражения первых, пока не более перевождь не существует. Однако вам нужно позаботиться о других ,, ( и ). Решение @BorisStrandjev лучше, более пуленепробито.

String infix(String expr) { 
    // Use place holders for '(' and ')' to use regex [^,()]. 
    expr = expr.replaceAll("(?!ABC)\\(", "<<"); 
    expr = expr.replaceAll("(?!ABC)\\)", ">>"); 
    for (;;) { 
     String expr2 = expr.replaceAll("ABC\\(([^,()]*)\\,([^,()]*)\\)", 
       "<<$1>>%<<$2>>"); 
     if (expr2 == expr) 
      break; 
     expr = expr2; 
    } 
    expr = expr.replaceAll("<<", ")"); 
    expr = expr.replaceAll(">>", ")"); 
    return expr; 
} 

Answer 4

Вы можете использовать эти регулярные выражения библиотеки https://github.com/florianingerl/com.florianingerl.util.regex, что также поддерживает рекурсивные регулярные выражения.

Преобразование ABC (ABC (20,2), 5) к ((20)% (2))% (5) выглядит следующим образом:

Pattern pattern = Pattern.compile("(?<abc>ABC\\((?<arg1>(?:(?'abc')|[^,])+)\\,(?<arg2>(?:(?'abc')|[^)])+)\\))"); 
    Matcher matcher = pattern.matcher("ABC(ABC(20,2),5)"); 
    String replacement = matcher.replaceAll(new DefaultCaptureReplacer() { 
     @Override 
     public String replace(CaptureTreeNode node) { 
      if ("abc".equals(node.getGroupName())) { 
       return "(" + replace(node.getChildren().get(0)) + ")%(" + replace(node.getChildren().get(1)) + ")"; 
      } else 
       return super.replace(node); 
     } 

    }); 
    System.out.println(replacement); 
    assertEquals("((20)%(2))%(5)", replacement); 

Преобразование обратно, т.е. из ((20)% (2))% (5) - ABC (ABC (20,2), 5) выглядит следующим образом:

Pattern pattern = Pattern.compile("(?<fraction>(?<arg>\\(((?:(?'fraction')|[^)])+)\\))%(?'arg'))"); 
    Matcher matcher = pattern.matcher("((20)%(2))%(5)"); 
    String replacement = matcher.replaceAll(new DefaultCaptureReplacer() { 
     @Override 
     public String replace(CaptureTreeNode node) { 
      if ("fraction".equals(node.getGroupName())) { 
       return "ABC(" + replace(node.getChildren().get(0)) + "," + replace(node.getChildren().get(1)) + ")"; 
      } else if ("arg".equals(node.getGroupName())) { 
       return replace(node.getChildren().get(0)); 
      } else 
       return super.replace(node); 
     } 

    }); 
    System.out.println(replacement); 
    assertEquals("ABC(ABC(20,2),5)", replacement);