這樣一個小語法的成熟的解析器可能是一個矯枉過正的問題,特別是當OP顯然沒有先前的經驗時。甚至不使用像ANTLR或JavaCC這樣的解析器生成器似乎是一個好主意。
用當前信息來闡述更多信息並不容易。 OP,請提供所需信息作爲對您問題的評論。
暫定語法:
maxExpr ::= maxExpr '|' '(' minExpr ')'
maxExpr ::= '(' minExpr ')'
minExpr ::= minExpr '&' ITEM
minExpr ::= ITEM
ITEM ::= 'DDT\d{4}'
意識到,true,則語法是過度用於正則表達式,但是對於單個正則表達式。沒有人說我們不能使用多於一個。事實上,即使是最簡單的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