표현식 평가

Question

this처럼 표현식 평가 프로그램을 진행하고 있습니다. 내 문제는 내가 작업 우선 순위를 처리하는 방법을 알아낼 수 없다는 것입니다. 이 때문에, 지금

Evaluate("3 * 5") 

:

Evaluate("2 + (3 * 5)") 

자체가이 방법을 다시 호출합니다 : 나는하고, 발견했을 때, 다음과 같이 그 내부의 발현을 해결 괄호의 안쪽 부부를 찾기 위해 재귀를 사용 괄호가 아닌 경우 결과를 계산하고 다른 시간을 호출합니다.

Evaluate("2 + 15") 

Ok, 반환 값은 예상대로 17입니다. 그러나 Evaluate("2 + 3 * 5")으로 전화하면

Evaluate("2 + 3 * 5") 
Evaluate("5 * 5") 

분명히 잘못되었습니다.
기본적으로 왼쪽에서 오른쪽으로 작업을 해결하고 있습니다. 먼저 수행해야하는 작업을 어떻게 선택할 수 있습니까? 나는 모든 작업을 둘러싼 두 개의 괄호를 추가하려고 생각했지만 너무 좋아 보이지 않는다.
그래서 전체 식을 먼저 구문 분석해야합니까? 다른 방법이 있습니까?

Answer 1

우선 순위가 가장 높은 연산자를 검색하고 먼저 수행 한 다음 계속 진행하십시오. 따라서 +와 * 만 있으면 *의 인스턴스를 검색하고 aaaa * bbbb 부분 문자열을 aaaa * bbbb 값으로 바꿉니다. 그러한 인스턴스가 남아 있지 않으면 +에서 작업하십시오.

주어진 연산자 내에서의 순서가 중요 할 경우 (예를 들어 ^를 포함하는 경우) 해당 연산자로 시작할 위치를 결정해야합니다.

Answer 2

Antlr을 .net과 함께 사용하여 이런 종류의 작업을 수행하는 방법을 보여주는 멋진 기사입니다. 당신이 당신의 파서를 작성 손하려면 같은

http://www.codeproject.com/KB/recipes/sota_expression_evaluator.aspx

는 소리가 난다, 그러나 이것은 당신이 제대로이 작업을 수행하는 방법을 볼 필요가 모든 줄 것이다.

기본적으로 표현식을 각 작업이 다음 레벨에서 작동하는 가능한 작업 시퀀스로 정의하여 우선 순위를 구현합니다. 작업의 우선 순위는이 순서의 순서로 인코딩됩니다.

예. '+'와 '*'가 포함 된 매우 간단한 예제

additiveExpression: multiplicativeExpression '+' multiplicativeExpression 
multiplicativeExpression: number '*' number 

손으로 작성된 재귀 적 하향 파서는 맨 위 규칙에서 시작하여 작동합니다.

Antlr을 사용하여 매우 간단한 문법을 ​​작성한 다음 생성하는 코드를 확인할 수 있습니다.이 경우 매우 짧은 코드이므로 따라 가기가 쉽습니다.

문법이 복잡해지면 어쨌든 Antlr과 같은 도구를 사용하는 것이 좋습니다. 파싱 코드에서 무거워지는 것을 많이 제거합니다. 전에 수 백 번 행해졌 고 매우 기계적입니다. 표현으로 할 수있는 흥미로운 부분에 집중할 수 있습니다.

Answer 3

어쨌든 재발행해야합니다. 그래서 심지어 당신이 +를 볼 때 당신은 재발해야합니다. 본질적으로 괄호가없는 모든 이진 연산자를 처리해야합니다.

2 + 3 * 5는 실제로 2 + (3 * 5)입니다.

Answer 4

폴란드어 표기법을 사용하면 도움이 될만한 것 : http://en.wikipedia.org/wiki/Polish_notation#Computer_programming. 이 표기법을 사용하면 괄호를 사용하지 않아도되고 작업 순서에 도움이됩니다.

이 사용법에 대해 좋은 점은 이러한 종류의 표현식을 평가하는 알고리즘이 있다는 것입니다. 중위 표현식을 접두사 또는 접미사 표현식으로 변환하는 것도 가능합니다.

여기에 그것을 할 수있는 방법의 예 - 귀하의 예를 들어 "2 + 3 * 5"걸릴 수 있습니다 :

2 + 3 * 5 
b = 3 * 5 
    -convert b- 
b = * 3 5 
2 + b 
    -convert expression- 
+ 2 b 
    -expand b- 
+ 2 * 3 5 

나는 이러한 변환을 한 번 첫 번째 부부, 나는 매우 그들에 의해 혼동되었다. 그것이 당신을 위해서라면, 협박하지 말고 계속 연습하십시오. 좋은 점은이 변환을 수행하는 데 도움이되는 알고리즘을 찾을 수 있으므로 약간 도움이된다는 것입니다.

이 변환을 수행하는 것이 큰 이점은 왼쪽에서 오른쪽으로 수정 된 표현식을 평가할 수 있다는 것입니다. 알고리즘은 다음과 같이 실행됩니다.

운영자 용과 운영자 용의 두 스택을 유지 관리합니다. 평가에서 왼쪽에서 오른쪽으로 : 당신이 운영자로 실행하면

1. , 당신과 피연산자 (수)로 실행하면 운영자 스택
2. 에 밀어
3. 일단 피연산자 스택에 밀어 최상위 연산자 (대부분의 경우 2 개)에 대해 충분한 피연산자를 찾았으며 연산자를보고 두 피연산자에 대해 해당 연산을 수행했습니다.
4. 3 단계 결과를 피연산자 스택에 푸시합니다.

일부 작업을 간소화했으며 일부 단계를 빠뜨린 경우가 있으므로 시작 지점으로 만 사용하십시오. 내가 건너 뛴/톤을 기억하지 않는 세부 사항이 있습니다. 그 중 일부는 연산자 바이너리 또는 단항 연산자, 괄호를 처리하는 방법, 권력 평가를 처리하는 방법 등을 포함합니다.

희망이 도움이 행운을 빕니다 :)