Как я могу разобрать уравнение NSString в дерево?Objective-C

Question

Я пытаюсь разобрать булево уравнение, которое в настоящее время имеет форму NSString.

Я хочу разобрать его в дерево, чтобы можно было манипулировать и упростить выражение в его простейшей форме.

Как может сделать Вольфрам Альфа.

http://www.wolframalpha.com/input/?i=%28A+and+%28A+or+B%29+or+%28B+and+A%29+or+not%28A%29%29+and+%28B+or+not+%28A%29%29

Упрощает ввод:

(A and (A or B) or (B and A) or not(A)) and (B or not (A))

до

Not(a) or B

Моя проблема заключается в разборе уравнения в объект дерева, где каждый узел дерева имеет 3 свойства:

1.TreeNode * parent

2.NSMutableArray * children

3.NSString* данные

спасибо

Answer 1

Чтобы разобрать строку в дерево (AST), вам нужны два компонента: лексер, который разбивает строку на отдельные «токены» - фигурные скобки, операторы, идентификаторы в вашем случае и парсер, который потребляет токены по одномуодин из лексеров и строит дерево.Для лексера, который вы, вероятно, собираетесь использовать NSScanner, парсер для вашей грамматики легко написать вручную (см., Например, http://en.wikipedia.org/wiki/Recursive_descent_parser), или вы можете использовать такой инструмент, как yacc или Lemon.

Answer 2

Мой математический парсер (DDMathParser) должен быть в состоянии справиться с этим с небольшой модификацией:

#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
}

Что касается упрощения выражения ... DDMathParser выполняет элементарную перезапись выражения , что полностью объяснено в этой вики-странице в хранилище DDMathParser . Я не уверен, есть ли какие-либо правила переписывания для логических выражений (применяя закон Деморгана и т. Д.), Но добавить их будет несложно.

Относительно ваших требований:

1. Каждый DDExpression узел имеет parentExpression свойство только для чтения
2. Вы можете получить доступ к подвыражениям узла DDExpression через свойство arguments
3. Из-за решения о том, как DDMathParser анализирует строки, A и B будут фактически проанализированы как A() и B() (то есть функции, которые не принимают параметров). Если вы хотите, чтобы они анализировались как «переменные» выражения, им потребуется $ впереди: $A и т. Д. Это просто означает, что вы можете получить доступ к названию вещи, используя свойство function, в отличие от свойства variable.

Answer 3

Хорошо, спасибо за помощь, это последний код Objective-C, который я написал для анализа логического выражения в дереве:

принимает выражение, такое как

A AND B OR C AND NOT(B)

в форме:

A.B + C./b

Работает с разбором скобок с приоритетом:

-(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;

}

Где объект treeNode имеет свойства и методы:

@interface TreeNode : NSObject{
    NSMutableArray *children;
    TreeNode *parent;
    NSString *value;
}

+(TreeNode *)newTreeNodeWithValue:(NSString *)Value;
-(void)addChild:(TreeNode *)child;

Методы делают то, что подразумевается там именами. Надеюсь, что в будущем это может помочь любому другому, ищущему парсер либо специально для булевой алгебры, либо, возможно, в качестве основы для другого парсера.