老谭笔记

Objective-C实现的简单逻辑表达式解析

因为项目中会用到远程配置,配置内容会进行很多条件判定,为了让配置更灵活,所以希望最终能将条件满足情况直接进行逻辑表达式运算.
所以就涉及到表达式的解析,开源的表达式解析的库倒不是少,但考虑仅是逻辑表达式的处理,便不想引入庞大的外部库,于是就决定自己来造这个轮子.
简单分析,其实需要处理的表达式一共就包含这7种符号:&&,||,!,(,),YES,NO,并且相互之间的优先级也非常简单.

将解析的过程分解为如下几个步骤:
1.从表达式中按顺序读取并匹配符号;
2.当匹配到的是(,&&,||,!都直接放于栈中,继续步骤1;
3.当匹配到的是YES或NO,就依次从栈中取出前面的符号,如果是!取反后放入栈继续此步骤,如果是&&或||就再取前一个操作数作逻辑运算,并继续重复此步骤,直到栈内没有内容或遇上(便将当前操作结果的数放入栈继续步骤1;
4.当遇上)则取出栈顶的YES或NO,并将前一个(取出扔掉,然后继续执行步骤3.
5.当表达式解析到末尾,栈内便只有栈顶的这个结果.

最终代码实现,这可能不是最优的方案,代码也不是很简洁,但问题算是解决了:

typedef enum
{
    SymbolNULL = 0,
    LogicAnd = 1,
    LogicOR = 2,
    LogicNOT = 3,
    LeftParenthesis = 4,
    RightParenthesis = 5,
    SymbolYES = 6,
    SymbolNO = 7,
} SymbolType;

BOOL LogicOperation(NSString *expression,NSError **error)
{
    NSDictionary *symbolMap = @{@"&&":@(LogicAnd),@"||":@(LogicOR),@"!":@(LogicNOT),
                                @"(":@(LeftParenthesis),@")":@(RightParenthesis),
                                @"YES":@(SymbolYES),@"NO":@(SymbolNO)};

    //用作栈
    NSMutableArray *stackArr = [NSMutableArray array];

    NSInteger idx = 0;
    while (idx < expression.length)
    {
        //空格
        if ([expression characterAtIndex:idx] == ' ')
        {
            idx++;
            continue;
        }

        //读取当前的符号
        SymbolType curSymbol = SymbolNULL;
        for (NSString *symbolStr in symbolMap)
        {
            NSRange range = NSMakeRange(idx, symbolStr.length);

            if (NSMaxRange(range) > expression.length)
                continue;

            NSString *subStr = [expression substringWithRange:range];
            if ([symbolStr isEqualToString:subStr])
            {
                curSymbol = [symbolMap[symbolStr] integerValue];
                idx = NSMaxRange(range);
                break;
            }
        }

        //异常处理(不能识别当前符号)
        if (curSymbol == SymbolNULL)
        {
            if (error) *error = [NSError errorWithDomain:@"com.tencent" code:101 userInfo:@{NSLocalizedDescriptionKey:@"Invalid Symbol!"}];
            return NO;
        }

        //遇上&&,||,!,(都先放栈内,暂时不处理
        if (curSymbol == LogicAnd ||
            curSymbol == LogicOR ||
            curSymbol == LogicNOT ||
            curSymbol == LeftParenthesis)
        {
            [stackArr addObject:@(curSymbol)];
            continue;
        }

        //遇上右括号,取出括号内的值作为当前值(因为一旦遇上运算我们会优先运算结果,所以右括号前会是一个YES或NO,再前面会是一个左括号)
        if (curSymbol == RightParenthesis)
        {
            if (stackArr.count < 2)
            {
                if (error) *error = [NSError errorWithDomain:@"com.tencent" code:102 userInfo:@{NSLocalizedDescriptionKey:@"Missing Parenthesis!"}];
                return NO;
            }

            SymbolType resultSymbol = [[stackArr lastObject] integerValue];
            [stackArr removeLastObject];
            SymbolType otherSymbol = [[stackArr lastObject] integerValue];
            [stackArr removeLastObject];
            if ((resultSymbol!=SymbolYES && resultSymbol!=SymbolNO) ||
                otherSymbol != LeftParenthesis)
            {
                if (error) *error = [NSError errorWithDomain:@"com.tencent" code:103 userInfo:@{NSLocalizedDescriptionKey:@"Missing Parenthesis!"}];
                return NO;
            }
            curSymbol = resultSymbol;
        }

        //遇上YES和NO时尝试与前面的元素结合(此处循环与前面的结合运算)
        while (curSymbol == SymbolYES || curSymbol == SymbolNO)
        {
            SymbolType firstSymbol = SymbolNULL;
            if (stackArr.count > 0)
                firstSymbol = [[stackArr lastObject] integerValue];

            //完成取反运算
            if (firstSymbol == LogicNOT)
            {
                [stackArr removeLastObject];
                curSymbol = (curSymbol==SymbolYES) ? SymbolNO : SymbolYES;
            }

            //完成&&和||运算
            else if (firstSymbol == LogicAnd ||
                firstSymbol == LogicOR)
            {
                [stackArr removeLastObject];
                if (stackArr.count == 0)
                {
                    if (error) *error = [NSError errorWithDomain:@"com.tencent" code:104 userInfo:@{NSLocalizedDescriptionKey:@"Missing Value!"}];
                    return NO;
                }

                SymbolType otherSymbol = [[stackArr lastObject] integerValue];
                [stackArr removeLastObject];
                if (otherSymbol!=SymbolYES && otherSymbol!=SymbolNO)
                {
                    if (error) *error = [NSError errorWithDomain:@"com.tencent" code:105 userInfo:@{NSLocalizedDescriptionKey:@"Missing Value!"}];
                    return NO;
                }

                SymbolType result = SymbolNO;
                if (firstSymbol == LogicAnd)
                {
                    if (curSymbol==SymbolYES && otherSymbol==SymbolYES)
                        result = SymbolYES;
                }
                else
                {
                    if (curSymbol==SymbolYES || otherSymbol==SymbolYES)
                        result = SymbolYES;
                }
                curSymbol = result;
            }

            //其它情况直接压栈
            else
            {
                [stackArr addObject:@(curSymbol)];
                break;
            }
        }
    }

    SymbolType resultSymbol = [[stackArr lastObject] integerValue];
    return (resultSymbol==SymbolYES) ? YES : NO;
}