Полномасштабный синтаксический анализатор для такой маленькой грамматики может быть излишним, особенно когда ОП, очевидно, не имеет опыта с ними. Даже использование генераторов парсеров, таких как ANTLR или JavaCC, кажется хорошей идеей.
Непросто разработать более подробную информацию. OP, просьба предоставить информацию, запрошенную в качестве комментариев к вашему вопросу.
Ориентировочная грамматика:
maxExpr ::= maxExpr '|' '(' minExpr ')'
maxExpr ::= '(' minExpr ')'
minExpr ::= minExpr '&' ITEM
minExpr ::= ITEM
ITEM ::= 'DDT\d{4}'
Поняла, что, правда, грамматика является чрезмерной для RegEx, но для одного RegEx. Никто не говорит, что мы не можем использовать больше одного. На самом деле даже простейшая замена RegEx можно рассматривать как шаг на машине Тьюринга, и, следовательно, проблема разрешима с их использованием.Итак ...
str= str.replaceAll("\\s+", "") ;
str= str.replaceAll("&", ",") ;
str= str.replaceAll("\\([^)]+\\)", "-$0") ;
str= str.replaceAll("\\|", ",") ;
str= str.replaceAll(".+", "+($0)") ;
str= str.replaceAll("\\w+", "x($0)") ;
str= str.replaceAll("\\+", "max") ;
str= str.replaceAll("-", "min") ;
Я не принимал много ярлыков. Общая идея состоит в том, что «+» соответствует произведению maxExpr и «-» на один из minExpr.
Я проверил это с входом
str= "(DDT1453 & DDT1454 & DDT1111) | (DDT3524 & DDT3523 & DDT3522 & DDT3520)" ;
Выход:
max(min(x(DDT1453),x(DDT1454),x(DDT1111)),min(x(DDT3524),x(DDT3523),x(DDT3522),x(DDT3520)))
Вернуться к идее грамматики, легко признать, что существенные элементы его действительно ПУНКТЫ и «| ' , Все остальное (круглые скобки и «&») - это просто украшение.
Упрощенная грамматика:
maxExpr ::= maxExpr '|' minExpr
maxExpr ::= minExpr
minExpr ::= minExpr ITEM
minExpr ::= ITEM
ITEM ::= 'DDT\d{4}'
Отсюда очень простой конечный автомат:
<start>
maxExpr= new List() ;
minExpr= new List() ;
"Expecting ITEM" (BEFORE_ITEM):
ITEM -> minExpr.add(ITEM) ; move to "Expecting ITEM, |, or END"
"Expecting ITEM, |, or END" (AFTER_ITEM):
ITEM -> minExpr.add(ITEM) ; move to "Expecting ITEM, |, or END"
| -> maxExpr.add(minExpr); minExpr= new List(); move to "Expecting ITEM"
END -> maxExpr.add(minExpr); move to <finish>
... и соответствующая реализация:
static Pattern pattern= Pattern.compile("(\\()|(\\))|(\\&)|(\\|)|(\\w+)|(\\s+)") ;
static enum TokenType { OPEN, CLOSE, MIN, MAX, ITEM, SPACE, _END_, _ERROR_ };
static enum State { BEFORE_ITEM, AFTER_ITEM, END }
public static class Token {
TokenType type;
String value;
public Token(TokenType type, String value) {
this.type= type ;
this.value= value ;
}
}
public static class Lexer {
Scanner scanner;
public Lexer(String input) {
this.scanner= new Scanner(input) ;
}
public Token getNext() {
String tokenValue= scanner.findInLine(pattern) ;
TokenType tokenType;
if(tokenValue == null) tokenType= TokenType._END_ ;
else if(tokenValue.matches("\\s+")) tokenType= TokenType.SPACE ;
else if("(".equals(tokenValue)) tokenType= TokenType.OPEN ;
else if(")".equals(tokenValue)) tokenType= TokenType.CLOSE ;
else if("&".equals(tokenValue)) tokenType= TokenType.MIN ;
else if("|".equals(tokenValue)) tokenType= TokenType.MAX ;
else if(tokenValue.matches("\\w+")) tokenType= TokenType.ITEM ;
else tokenType= TokenType._ERROR_ ;
return new Token(tokenType,tokenValue) ;
}
public void close() {
scanner.close();
}
}
public static String formatColl(String pre,Collection<?> coll,String sep,String post) {
StringBuilder result= new StringBuilder() ;
result.append(pre);
boolean first= true ;
for(Object item: coll) {
if(! first) result.append(sep);
result.append(item);
first= false ;
}
result.append(post);
return result.toString() ;
}
public static void main(String... args) {
String str= "(DDT1453 & DDT1454) | (DDT3524 & DDT3523 & DDT3522 & DDT3520)" ;
Lexer lexer= new Lexer(str) ;
State currentState= State.BEFORE_ITEM ;
List<List<String>> maxExpr= new LinkedList<List<String>>() ;
List<String> minExpr= new LinkedList<String>() ;
while(currentState != State.END) {
Token token= lexer.getNext() ;
switch(currentState) {
case BEFORE_ITEM:
switch(token.type) {
case ITEM:
minExpr.add("x("+token.value+")") ;
currentState= State.AFTER_ITEM ;
break;
case _END_:
maxExpr.add(minExpr) ;
currentState= State.END ;
break;
default:
// Ignore; preserve currentState, of course
break;
}
break;
case AFTER_ITEM:
switch(token.type) {
case ITEM:
minExpr.add("x("+token.value+")") ;
currentState= State.AFTER_ITEM ;
break;
case MAX:
maxExpr.add(minExpr) ;
minExpr= new LinkedList<String>() ;
currentState= State.BEFORE_ITEM ;
break;
case _END_:
maxExpr.add(minExpr) ;
currentState= State.END ;
break;
default:
// Ignore; preserve currentState, of course
break;
}
break;
}
}
lexer.close();
System.out.println(maxExpr);
List<String> maxResult= new LinkedList<String>() ;
for(List<String> minItem: maxExpr) {
maxResult.add(formatColl("min(",minExpr,",",")")) ;
}
System.out.println(formatColl("max(",maxResult,",",")"));
}
Остерегайтесь уязвимостей к инъекциям. – SLaks
Ваш желаемый результат не соответствует вашему описанию. Вы случайно заменили «max» и «min» на первые два экземпляра, или ваше описание не так? –
Да, спасибо, просто изменил его – kjm