Al analizar RPN, dos ecuaciones dan la misma notación pero tienen respuestas diferentes

Question

Escribí un analizador en PHP que convierte una representación de cadena de una ecuación a RPN basada en los comentarios de un pregunta anterior . Mientras lo probaba, encontré dos ecuaciones diferentes que se analizan en RPN. Debido a que terminan como lo mismo en RPN cuando los resuelves, obtienes la misma respuesta.

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

Ambos terminan como 348 * 15 - / + que cuando se resuelven dan una respuesta de -5 que es correcta para la primera, pero la respuesta a la segunda debe ser 30.

Entonces, ¿he entendido mal cómo convertir a RPN? El código de mi analizador se puede encontrar en el enlace anterior a la pregunta anterior.

Answer 1

Encontré el error en tu analizador. En su último gran bloque else , debe reemplazar

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

con

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

Después de ese cambio, sus dos casos de prueba funcionan bien aquí. (Utilicé esta referencia para corregir su código. Dejé de revisar su código después de solucionando el problema en su pregunta, por lo que podría haber más errores en el interior, ¡no revisé todo!)

EDITAR: Lo importante es reemplazar " == " con " > = " ;. Si siempre tendrá solo dos niveles de precedencia, no es estrictamente necesario reemplazar si con un bucle.