Analisando a RPN duas equações dar mesma notação mas têm respostas diferentes
Pergunta
Eu escrevi um analisador em PHP que converte uma representação em cadeia de uma equação para RPN com base no feedback de um anteriormente questão . Enquanto testá-lo eu encontrei duas equações diferentes que analisam a mesma coisa em RPN. Porque eles acabam como a mesma coisa em RPN quando você resolvê-los você recebe a mesma resposta.
- 3 + 4 * 8 / (1 -5)
- 3 + 4 * 8/1 -5
Ambos acabar como 348 * 15 -. / + Que quando resolvido dá uma resposta de -5 qual é correcto para a primeira, mas a resposta para o segundo deve ser 30
Eu também mal interpretado como converter a RPN? O código para meu analisador pode ser encontrada no link acima para a pergunta anterior.
Solução
Eu encontrei o erro no seu analisador. Em sua última grande bloco else
, você precisa substituir
$current = end($stack);
if($operators[$tokens[$i]] == $operators[$current]) {
$rpn .= array_pop($stack);
$stack[] = $tokens[$i];
} else {
$stack[] = $tokens[$i];
}
com
while(!empty($stack) && end($stack) != '(' && $operators[$tokens[$i]] >= $operators[end($stack)]) {
$rpn .= array_pop($stack);
}
$stack[] = $tokens[$i];
Depois que a mudança, os dois casos de teste funcionar bem aqui. (Eu usei este referência para corrigir o seu código. Eu parei de verificar o seu código depois corrigir o problema na sua pergunta, então pode haver mais erros dentro - Eu não fiz tudo à prova de leitura)
EDIT: O importante é substituir "==" com "> =". Se você sempre terá apenas dois níveis de prioridade, substituindo o if
com um laço não é estritamente necessário.