moley
BAN USERI don't know if this is the best way, but you could write this as a simple recursive descent parser. The trick is getting the write grammar.
This is the simplese grammar I could come up with:
EXPRLIST ::=
EXPR |
EXPR "," EXPR
EXPR ::=
STRINGEXPR |
EXPANSIONEXPR |
EXPR EXPR
STRINGEXPR ::=
"[A-Z][a-z]"
EXPANSIONEXPR ::=
"(" EXPRLIST ")"
Then translating this into a javascript like pseudo code, gives you this:
var input = "" // some input string;
var pointer= 0; // pointer to position in the input
function Run(strInput){
input = strInput;
pointer=0;
return ReadExprList();
}
function Curr(){
if(position < input.length-1)
return input[position];
else
return null; // EOF
}
function ReadExpr() {
var ctx = [""];
While(Curr().isAlphaNumericChar() || Curr() == "("){
if(Curr().isAlphaNumericChar()){
var str = ReadString();
for(i=0 to ctx.length-1){
ctx[i] += str;
}
}
else{
var expanded = ReadExpansion();
var newctx = [];
for(i in ctx){
for(j in expanded){
newctx.push(ctx[i]+expanded[j]);
}
}
ctx = newctx
}
}
return ctx;
}
function ReadExprList(){
var ctx = [];
do{
ctx = ctx + ReadExpr();
} while (Curr() == ",")
}
function ReadString(){
str = "";
while(Curr().isAlphaNumericChar){
str += ReadChar()
}
return str;
}
function ReadExpansion(){
Read("(");
var result = ReadExprList();
Read(")");
return result;
}
function Read(var char){
var c = Curr();
if(char != c){
error("Expected: " + char +" actual: " +c);
}
pointer++;
return c;
}
function Read() {
var c = Curr();
pointer++;
return c;
}
The coloring approach that is the top answer works, but can be made more efficient. This JavaScript code will typically take less than n comparisons, and at most n.
- moley March 19, 2015