我如何将 NSString 方程解析为树？ Objective-C

Question

我正在尝试解析当前 NSString 形式的布尔方程。

我想将它解析成一棵树，以便我可以操纵表达式并将其简化为最简单的形式。

就像 Wolfram Alpha 能够做到的那样。

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))

to

Not(a) or B

我的问题是将方程解析为树对象，其中每个树节点有3个属性：

1.TreeNode *parent

2.NSMutableArray *children

3.NSString *data

谢谢

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 存储库上的此 wiki 页面中进行了解释。我不确定逻辑表达式是否有任何重写规则（应用德摩根定律等），但添加这些并不难。

关于您的要求：

1. 每个 DDExpression 节点都有一个 parentExpression 只读属性
2. 您可以通过 arguments 访问 DDExpression 节点的子表达式 属性
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;

方法按照名称所暗示的方式执行操作。
希望这可以帮助其他人将来寻找专门用于布尔代数的解析器或作为不同解析器的基础。