Синтаксический анализ двух уравнений в RPN дает одинаковые обозначения, но дает разные ответы. - PullRequest
Новая
       15

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

1 голос
/ 27 ноября 2009

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

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

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

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

1 Ответ

1 голос
/ 27 ноября 2009

Я нашел ошибку в вашем парсере. В вашем последнем большом 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 на цикл не обязательна.

...