Determine if given string is generated by fibmorse substitution

solvefib.r

prev.value = function(str){
  if(str == "01") return("0")
  if(str %in% c("0","10")) return("1")
  return(NULL)
}



tokenize = function(str,prev.tokens=c("")){
  if(str == "") return("");
  new.tokens = c()
  
  new.token = NULL
  pop1 = substr(str,1,1)
  prev = prev.value(pop1)
  if(!is.null(prev)){
    if(nchar(str) > 1){
      new.token = tokenize(substr(str,2,nchar(str)),prev)
    } else {
      new.token = prev
    }
  }
  if(!is.null(new.token)) new.tokens = c(new.tokens,new.token)
  
  if(nchar(str) > 1) {
    pop2 = substr(str,1,2)
    prev = prev.value(pop2)
    if(!is.null(prev)){
      if(nchar(str) > 2){
        new.token = tokenize(substr(str,3,nchar(str)),prev)
      } else {
        new.token = prev
      }
    }
  }
  if(!is.null(new.token)) new.tokens = c(new.tokens,new.token)
  
  if(length(new.tokens) == 0){
    return(NULL)
  }
  
  new.prev.tokens = c()
  for(prev.token in prev.tokens){
    new.prev.tokens = c(new.prev.tokens,paste(prev.token,new.tokens,sep=""))
  }
  return(new.prev.tokens)
}

balance = function(str){
  n = nchar(str)
  num.ones = 0
  for(i in 1:n){
    s = substr(str,i,i)
    if(s == "1") num.ones = num.ones + 1
  }
  return(n - num.ones)
}

solve.fibmorse = function(strs){
  while(!any(nchar(strs) == 1) & !all(is.null(strs))){
    new.strs = c()
    for(str in strs){
      possibles = tokenize(str)
      new.strs = c(new.strs,possibles)
    }
    strs = new.strs
  }
  return(unique(strs))
}

####

solve.fibmorse("01001")