algoritmo padrão para tokenize uma seqüência, manter delimitadores (em PHP)
Pergunta
Eu quero dividir uma expressão aritmética em tokens, convertê-lo em RPN.
Java tem o StringTokenizer, que pode, opcionalmente, manter os delimitadores. Dessa forma, eu poderia usar os operadores como delimitadores. Infelizmente, eu preciso fazer isso em PHP, que tem strtok, mas que joga fora os delimitadores, então eu preciso para preparar algo de mim.
Isso soa como um exemplo clássico livro-texto para Compiler Projeto 101, mas eu tenho medo que eu estou faltando alguma educação formal aqui. Existe um algoritmo padrão que você pode apontar-me a?
As minhas outras opções são para ler sobre Análise Lexical ou para rolar até algo rápido e sujo com as funções de string disponível.
Solução
Como muitas vezes, gostaria apenas de usar uma expressão regular para fazer isso:
$expr = '(5*(7 + 2 * -9.3) - 8 )/ 11';
$tokens = preg_split('/([*\/^+-]+)\s*|([\d.]+)\s*/', $expr, -1,
PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
$tts = print_r($tokens, true);
echo "<pre>x=$tts</pre>";
Ela precisa de um pouco mais de trabalho para aceitar números com expoente (como -9.2e-8).
Outras dicas
Isto pode ajudar.
OK, graças a PhiLho, meu código final é isso, alguém deveria precisar dele. Não é mesmo muito sujo. : -)
static function rgTokenize($s)
{
$rg = array();
// remove whitespace
$s = preg_replace("/\s+/", '', $s);
// split at numbers, identifiers, function names and operators
$rg = preg_split('/([*\/^+\(\)-])|(#\d+)|([\d.]+)|(\w+)/', $s, -1, PREG_SPLIT_DELIM_CAPTURE | PREG_SPLIT_NO_EMPTY);
// find right-associative '-' and put it as a sign onto the following number
for ($ix = 0, $ixMax = count($rg); $ix < $ixMax; $ix++) {
if ('-' == $rg[$ix]) {
if (isset($rg[$ix - 1]) && self::fIsOperand($rg[$ix - 1])) {
continue;
} else if (isset($rg[$ix + 1]) && self::fIsOperand($rg[$ix + 1])) {
$rg[$ix + 1] = $rg[$ix].$rg[$ix + 1];
unset($rg[$ix]);
} else {
throw new Exception("Syntax error: Found right-associative '-' without operand");
}
}
}
$rg = array_values($rg);
echo join(" ", $rg)."\n";
return $rg;
}