Analizzando in RPN due equazioni danno la stessa notazione ma hanno risposte diverse
Domanda
Ho scritto un parser in PHP che converte una rappresentazione di stringa di un'equazione in RPN in base al feedback di un domanda precedente . Durante il test ho trovato due diverse equazioni che analizzano la stessa cosa in RPN. Perché finiscono per essere la stessa cosa in RPN quando li risolvi ottieni la stessa risposta.
- 3 + 4 * 8 / (1 -5)
- 3 + 4 * 8/1 -5
Entrambi finiscono con 348 * 15 - / + che una volta risolto dà una risposta di -5 che è corretta per la prima, ma la risposta alla seconda dovrebbe essere 30.
Quindi ho capito male come convertire in RPN? Il codice per il mio parser può essere trovato nel link sopra alla domanda precedente.
Soluzione
Ho trovato l'errore nel tuo parser. Nel tuo ultimo grande blocco else
, devi sostituire
$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];
Dopo questa modifica, i tuoi due casi di test funzionano bene qui. (Ho usato questo riferimento per correggere il tuo codice. Ho smesso di controllare il tuo codice dopo risolvendo il problema nella tua domanda, quindi potrebbero esserci più bug all'interno - non ho riletto tutto!)
EDIT: l'importante è sostituire " == " con " > = " ;. Se avrai sempre solo due livelli di precedenza, la sostituzione del if
con un loop non è strettamente necessaria.