RPN에 구문 분석 두 방정식은 동일한 표기법을 제공하지만 다른 답변이 있습니다.

Question

PHP에 파서를 썼는데, 이는 방정식의 문자열 표현을 이전 질문. 테스트하는 동안 RPN에서 동일한 것을 구문 분석하는 두 가지 다른 방정식을 발견했습니다. 그들은 당신이 그들을 해결할 때 RPN에서 똑같은 일로 끝나기 때문에 당신은 같은 대답을 얻습니다.

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

둘 다 348*15 -/+로 끝납니다. 해결할 때 해결할 때 첫 번째 대답에 맞는 대답을 제공하지만 두 번째 답변은 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 루프를 사용하는 것은 엄격하게 필요하지 않습니다.