L'analyse syntaxique de deux équations RPN donne la même notation mais les réponses sont différentes

Question

J'ai écrit un analyseur syntaxique en PHP qui convertit la représentation sous forme de chaîne d'une équation en RPN en fonction des commentaires d'un question précédente . En le testant, j'ai trouvé deux équations différentes qui analysent la même chose dans RPN. Parce qu’ils se retrouvent dans la même situation dans RPN, lorsque vous les résolvez, vous obtenez la même réponse.

1. 3 + 4 * 8 / (1 -5)
2. 3 + 4 * 8/1 -5

Les deux se terminent par 348 * 15 - / + qui, une fois résolus, donne une réponse de -5 qui est correcte pour le premier, mais la réponse pour le second devrait être 30.

Alors, ai-je mal compris comment convertir en RPN? Le code de mon analyseur se trouve dans le lien ci-dessus à la question précédente.

Answer 1

J'ai trouvé l'erreur dans votre analyseur. Dans votre dernier grand else , vous devez remplacer

$current = end($stack);
if($operators[$tokens[$i]] == $operators[$current]) {
  $rpn .= array_pop($stack);
  $stack[] = $tokens[$i];
} else {
  $stack[] = $tokens[$i];
}

avec

while(!empty($stack) && end($stack) != '(' && $operators[$tokens[$i]] >= $operators[end($stack)]) {
  $rpn .= array_pop($stack);
}
$stack[] = $tokens[$i];

Après ce changement, vos deux cas de test fonctionnent bien ici. (J'ai utilisé cette référence pour corriger votre code. J'ai arrêté de vérifier votre code après. résoudre le problème dans votre question, donc il pourrait y avoir plus de bugs à l'intérieur - je n'ai pas tout relire!)

EDIT: l’important est de remplacer " == " avec " > = " ;. Si vous n’avez toujours que deux niveaux de priorité, remplacer le si par une boucle n’est pas strictement nécessaire.