수학 파서의 스마트한 디자인?

StackOverflow https://stackoverflow.com/questions/114586

  •  02-07-2019
  •  | 
  •  

문제

수학 파서를 설계하는 가장 현명한 방법은 무엇입니까?내 말은 수학 문자열을 취하는 함수입니다(예:"2 + 3 / 2 + (2 * 5)") 계산된 값을 반환합니까?나는 오래 전에 VB6에서 하나를 작성했지만 결과적으로 너무 비대해지고 이식성이 좋지 않았습니다(또는 그 문제에 있어서는 스마트하지 않았습니다...).일반적인 아이디어, 의사 코드 또는 실제 코드를 높이 평가합니다.

도움이 되었습니까?

해결책

꽤 좋은 접근 방식에는 두 단계가 포함됩니다.첫 번째 단계에는 다음이 포함됩니다. 표현식을 중위에서 후위로 변환 (예:~을 통해 Dijkstra의 분로장) 표기법.이 작업이 완료되면 글을 작성하는 것은 매우 간단합니다. 후위 평가자.

다른 팁

나는 수학 파서 설계에 관한 몇 가지 블로그 게시물을 썼습니다.일반이 있습니다 소개,에 대한 기본 지식 문법, Ruby로 작성된 샘플 구현 그리고 테스트 스위트.아마도 이 자료가 유용할 것입니다.

몇 가지 접근 방식이 있습니다.많은 코드를 작성하지 않고도 답을 얻기 위해 동적 코드를 생성하고 실행할 수 있습니다..NET에서 런타임 생성 코드를 검색하면 주변에 많은 예제가 있습니다.

또는 실제 파서를 생성하고 표현식을 평가하는 데 사용되는 작은 구문 분석 트리를 생성할 수 있습니다.다시 말하지만 이것은 기본 표현에 있어서 매우 간단합니다.거기에 수학 파서가 있다고 믿기 때문에 codeplex를 확인하십시오.아니면 예제가 포함된 BNF를 찾아보세요.컴파일러 개념을 소개하는 모든 웹사이트에는 이를 기본 예제로 포함합니다.

Codeplex 표현식 평가기

나는 이것이 오래되었다는 것을 알고 있지만 더 큰 앱의 일부로 계산기를 개발하려고 시도하고 허용된 답변을 사용하여 몇 가지 문제를 발견했습니다.링크는 이 문제를 이해하고 해결하는 데 큰 도움이 되었으며 무시해서는 안 됩니다.저는 Java로 Android 앱을 작성 중이었고 "문자열"이라는 표현의 각 항목에 대해 실제로 사용자가 키패드에 입력할 때 ArrayList에 문자열을 저장했습니다.중위에서 접미사로의 변환을 위해 ArrayList의 각 문자열을 반복한 다음 새로 배열된 접미사 문자열의 ArrayList를 평가했습니다.이는 소수의 피연산자/연산자에게는 환상적이었지만 특히 표현식이 정수가 아닌 값으로 평가되기 시작하면서 더 긴 계산이 지속적으로 중단되었습니다.제공된 링크에서 중위에서 후위로의 변환, 스캔된 항목이 연산자이고 topStack 항목의 우선 순위가 더 높은 경우 스택을 팝할 것을 제안합니다.나는 이것이 거의 정확하다는 것을 알았습니다.검색된 연산자보다 우선 순위가 높거나 같을 경우 topStack 항목을 팝하면 마침내 내 계산이 올바르게 나왔습니다.이것이 이 문제를 해결하는 모든 사람에게 도움이 되기를 바라며, 귀중한 링크를 제공한 Justin Poliey(및 fas?)에게 감사드립니다.

"항상 켜져 있는" 애플리케이션이 있는 경우 수학 문자열을 Google에 게시하고 결과를 구문 분석하면 됩니다.간단한 방법이지만 그것이 필요한지 확실하지 않지만 어떤 면에서는 똑똑하다고 생각합니다.

관련 질문 우선순위가 있는 방정식(표현식) 파서? 이 작업을 시작하는 방법에 대한 좋은 정보도 있습니다.

-아담

입력이 문자열 형식의 중위 표현식이라고 가정하면 이를 다음으로 변환할 수 있습니다. 접미사 그리고 한 쌍의 스택을 사용하여:연산자 스택과 피연산자 스택이 있으면 거기에서 솔루션을 작동합니다.Wikipedia 링크에서 일반적인 알고리즘 정보를 찾을 수 있습니다.

ANTLR은 매우 훌륭한 LL(*) 파서 생성기입니다.나는 그것을 적극 추천합니다.

개발자는 항상 깔끔한 접근 방식을 원하며 처음부터 구문 분석 논리를 구현하려고 노력합니다. Dijkstra Shunting-Yard 알고리즘.결과는 깔끔하게 보이는 코드이지만 버그가 많을 가능성이 있습니다.나는 그러한 API를 개발했습니다. JMEP, 그게 다인데 안정적인 코드를 갖추는 데 몇 년이 걸렸습니다.

모든 작업을 수행하더라도 해당 프로젝트 페이지에서 모든 작업이 이미 완료된 후에도 JavaCC 또는 ANTLR을 사용하도록 전환하는 것을 진지하게 고려하고 있음을 알 수 있습니다.

이 질문을 받은 시점으로부터 11년 후의 미래:바퀴를 다시 만들고 싶지 않다면 세상에는 이국적인 수학 파서가 많이 있습니다.

산술 연산, 방정식 풀이, 미분, 적분, 기본 통계, 함수/공식 정의, 그래프 작성 등을 지원하는 몇 년 전에 제가 쓴 글이 있습니다.

그것은 ~라고 불린다 파서NG 그리고 그것은 무료입니다.

표현식을 평가하는 방법은 다음과 같이 간단합니다.

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

또는 변수를 사용하고 간단한 표현식을 계산합니다.

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

또는 함수를 사용하여:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

또는 주어진 지점에서 도함수를 평가하려면(뒤에서 상징적 차별화(수치 아님)를 수행하므로 정확도는 수치 근사 오류로 인해 제한되지 않습니다):

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

차별화되는 점 x^3 * ln(x) x=3에 한 번.현재 미분할 수 있는 횟수는 1입니다.

또는 수치 적분의 경우:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

이 파서는 상당히 빠르며 다른 기능도 많이 있습니다.

Objective C에 대한 바인딩을 통해 Swift로 포팅하는 작업이 완료되었으며 다른 반복 사용 사례 중에서 그래프 애플리케이션에 사용했습니다.

부인 성명:ParserNG는 제가 작성했습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top