Анализ в RPN двух уравнений дает одинаковые обозначения, но имеет разные ответы

Question

Я написал синтаксический анализатор на PHP, который преобразует строковое представление уравнения в RPN на основе обратной связи от предыдущий вопрос.Во время тестирования я обнаружил два разных уравнения, которые анализируют одно и то же в RPN.Поскольку в RPN они заканчиваются одним и тем же, когда вы решаете их, вы получаете один и тот же ответ.

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

Оба заканчиваются как 348*15-/+ , который при решении дает ответ -5, который является правильным для первого, но ответ на второй должен быть 30.

Итак, я неправильно понял, как конвертировать в RPN?Код к моему анализатору можно найти по приведенной выше ссылке на предыдущий вопрос.

Answer 1

Я нашел ошибку в вашем анализаторе.В твоем последнем большом else блок, который необходимо заменить

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

с

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

После этого изменения ваши два тестовых примера здесь работают нормально.(Я использовал эта ссылка чтобы исправить ваш код.Я перестал проверять ваш код после устранения проблемы в вашем вопросе, так что внутри может быть больше ошибок - я не все вычитал!)

Редактировать:Важно заменить "==" на ">=".Если у вас всегда будет только два уровня приоритета, замените if с циклом это строго необязательно.