현재 NSString 형식의 부울 수식을 구문 분석하려고합니다.NSString 방정식을 트리로 구문 분석하려면 어떻게해야합니까? Objective-C
표현식을 가장 단순한 형식으로 조작하고 단순화 할 수 있도록이를 트리로 구문 분석하고 싶습니다.
Wolfram Alpha처럼 할 수 있습니다.
단순화 입력 :
:
(A and (A or B) or (B and A) or not(A)) and (B or not (A))
트리의 각 노드는 3 개 속성을 갖는 경우 내 문제 트리 객체에 식을 파싱
Not(a) or B
2.NSMutableArray * 어린이
3.NSString * 데이터
감사
이 난 나무에 부울 식을 구문 분석 쓴 마지막 Objective- C 코드 도움을 주셔서 감사합니다 그래서 :
가가의
A AND B OR C AND NOT(B)
과 같은 식을 필요가 형태 :
:A.B + C./b
이 우선 순위가 구문 분석 괄호와 함께 작동 이 이름으로 묵시적으로 방법이 할
@interface TreeNode : NSObject{
NSMutableArray *children;
TreeNode *parent;
NSString *value;
}
+(TreeNode *)newTreeNodeWithValue:(NSString *)Value;
-(void)addChild:(TreeNode *)child;
다음의 TreeNode 개체 속성과 메소드를 가지고
-(TreeNode *)ParseStringIntoTree:(NSString *)InputString{ //input string to parse
//returns root-node of tree
TreeNode *first=[[TreeNode alloc] init];
TreeNode *current=first;
NSString *workingString = [NSString stringWithString:InputString];
if (([workingString characterAtIndex:0]=='(') && ([workingString characterAtIndex:workingString.length-1]==')')) {
NSRange boop={1,workingString.length-2};
workingString=[workingString substringWithRange:boop];
}
int brackCount=0;
bool plussesLeft=FALSE;
for (int pos=0; pos<workingString.length; pos++) {
char currentC=[workingString characterAtIndex:pos];
//1
if (currentC=='(') {
brackCount++;
}
//2
if (currentC==')') {
brackCount--;
}
if (currentC=='+' && brackCount==0){
plussesLeft=TRUE;
}
}
//############ PARSE plus signs with BRACKETS
brackCount=0;
int prevPlusPos=-1;
if (plussesLeft) {
for (int pos=0; pos<workingString.length; pos++) {
char currentC=[workingString characterAtIndex:pos];
//1
if (currentC=='(') {
brackCount++;
}
//2
if (currentC==')') {
brackCount--;
}
//3
if (currentC=='+'&&brackCount==0) {
NSRange boop={prevPlusPos+1, pos-prevPlusPos-1};
NSString *toParse=[workingString substringWithRange:boop];
TreeNode *child;
if(toParse.length>1){child=[self ParseStringIntoTree:toParse];}
else{child=[TreeNode newTreeNodeWithValue:toParse];}
[current addChild:child];
[current setValue:@"+"];
prevPlusPos=pos;
}
//4
if (pos==workingString.length-1 &&brackCount==0 && prevPlusPos!=-1) {
NSRange boop={prevPlusPos+1, pos-prevPlusPos};
NSString *toParse=[workingString substringWithRange:boop];
TreeNode *child;
if(toParse.length>1){child=[self ParseStringIntoTree:toParse];}
else{child=[TreeNode newTreeNodeWithValue:toParse];};
[current addChild:child];
[current setValue:@"+"];
}
}
}
//############ finish PARSE plus signs with BRACKETS
BOOL dotsLeft=FALSE;
for (int pos=0; pos<workingString.length; pos++) {
char currentC=[workingString characterAtIndex:pos];
//1
if (currentC=='(') {
brackCount++;
}
//2
if (currentC==')') {
brackCount--;
}
if (currentC=='.' && brackCount==0){
dotsLeft=TRUE;
}
}
int prevDotPos=-1;
if (!plussesLeft && dotsLeft) {
for (int pos=0; pos<workingString.length; pos++) {
char currentC=[workingString characterAtIndex:pos];
//1
if (currentC=='(') {
brackCount++;
}
//2
if (currentC==')') {
brackCount--;
}
//3
if (currentC=='.' && brackCount==0 && prevPlusPos==-1) {
NSRange boop={prevDotPos+1, pos-prevDotPos-1};
NSString *toParse=[workingString substringWithRange:boop];
TreeNode *child;
if(toParse.length>1){child=[self ParseStringIntoTree:toParse];}
else{child=[TreeNode newTreeNodeWithValue:toParse];}
[current addChild:child];
[current setValue:@"."];
prevDotPos=pos;
}
//4
if (pos==workingString.length-1 &&brackCount==0 && prevDotPos!=-1) {
NSRange boop={prevDotPos+1, pos-prevDotPos};
NSString *toParse=[workingString substringWithRange:boop];
TreeNode *child;
if(toParse.length>1){child=[self ParseStringIntoTree:toParse];}
else{child=[TreeNode newTreeNodeWithValue:toParse];};
[current addChild:child];
[current setValue:@"."];
}
}
//left with current being the
}
if (!plussesLeft && !dotsLeft) {
if ([workingString characterAtIndex:0]=='/') {
TreeNode *child=[self ParseStringIntoTree:[workingString substringFromIndex:1]];
[current addChild:child];
[current setValue:@"/"];
}
if (workingString.length==1) {
[current setValue:workingString];
}
}
return first;
}
. 이것은 나중에 다른 사람을 도울 수 있습니다. 파서를 부울 대수 또는 특히 다른 파서의 기초로 사용하는 것이 좋습니다.
트리 (AST)로 문자열을 구문 분석하려면, 당신은 두 가지 구성 요소를 필요로 문자열을 분할하는 렉서를, 개별 "토큰"- 중괄호, 연산자, 케이스의 식별자 및 구문 분석기 (parser) - 렉서에서 하나씩 토큰을 소비하고 트리를 작성합니다. 렉서에 대해서는 NSScanner를 사용할 것입니다. 문법 파서는 손으로 직접 작성하거나 (예 : http://en.wikipedia.org/wiki/Recursive_descent_parser 참조) yacc 또는 Lemon과 같은 도구를 사용할 수 있습니다.
My math parser (DDMathParser)는 약간의 수정으로이 문제를 처리 할 수 있어야합니다 : 완전히 this wiki page on the DDMathParser repository에 설명되어 표현 ... DDMathParser does rudimentary expression rewriting을 단순화로
#import "DDMathParser.h"
NSString *source = @"(A and (A or B) or (B and A) or not(A)) and (B or not (A))";
source = [source stringByReplacingOccurrencesOfString:@" and " withString:@" && "];
source = [source stringByReplacingOccurrencesOfString:@" or " withString:@" || "];
NSError *error = nil;
DDExpression *e = [DDExpression expressionFromString:source error:&error];
if (e) {
// it successfully parsed
}
. 논리적 표현식 (DeMorgan의 법칙 적용 등)에 대한 재 작성 규칙이 있는지 확실하지 않지만 추가하기가 어렵지 않습니다.
DDExpression 노드 당신은 때문에 DDMathParser의 방법 결정에 arguments 재산DDExpression 노드의 하위 표현식을 액세스 할 수있는 parentExpression 읽기 전용 특성및 B은 실제로 A() 및 B() (즉, 매개 변수를 사용하지 않는 함수)으로 구문 분석됩니다. 변수를 "변수"식으로 구문 분석하려면 앞에 $A 등 $이 필요합니다. 이는 variable 속성과는 반대로 function 속성을 사용하여 해당 이름에 액세스 할 수 있음을 의미합니다. .좋아
+1 문자열이 올바른 형식이라는 것을 보증 할 수 있다면 RD 파서를 작성하는 것이 대부분 사소할 수 있습니다. –
그 덕분에, 위키 피 디아 항목을 살펴 봤지만 파서를 더 정확하게 작성하는 방법, 팁에 대해 여전히 헷갈 렸습니다. – Tawfiqh
@Tawfiqh : 파서를 생성하는 파서 생성기를 사용하십시오. 나는 단순하기 때문에 [레몬] (http://www.hwaci.com/sw/lemon/lemon.html)을 제안 할 것이다. – georg