基于后序表达式的 iOS 条件表达式求值引擎设计与实现

一、项目背景与问题定义

1.1 业务场景

在移动应用开发中,我们经常面临这样的需求:需要根据用户属性、上下文环境等多个条件动态决定业务逻辑。典型场景包括:

A/B 测试与特性开关: 根据用户 ID、VIP 等级、地域等条件决定是否开启某功能
动态 UI 渲染: 服务端下发配置,客户端根据条件判断显示哪些 UI 元素
权限系统: 复杂的多条件权限判断
智能推荐: 基于用户画像和行为数据的精准投放

1.2 传统方案的局限性

硬编码方式:

if (user.age > 18 && user.vipLevel >= 2 && [user.city isEqualToString:@"Beijing"]) {
    // 业务逻辑
}

问题: 每次调整条件都需要发版,无法动态配置。

NSPredicate 方案:

NSPredicate *predicate = [NSPredicate predicateWithFormat:@"age > 18 AND vipLevel >= 2"];
BOOL result = [predicate evaluateWithObject:user];

问题: 语法固定,难以扩展自定义运算符,且主要面向数据筛选而非条件判断。

1.3 解决方案

开发一个轻量级、可扩展的表达式求值引擎,支持:

服务端下发表达式字符串,客户端动态解析执行
灵活的变量绑定机制(支持 KeyPath、上下文注入)
可自由扩展的运算符系统
高性能的求值算法

二、核心技术选型

2.1 算法基础:后序表达式(逆波兰表示法)

中缀表达式 vs 后序表达式:

表达式类型	示例	特点
中缀表达式	`a + b * c`	人类习惯,但计算需要考虑优先级和括号
后序表达式	`a b c * +`	无需括号,按顺序入栈计算即可

为什么选择后序表达式?

无需考虑优先级: 后序表达式已按计算顺序排列
计算效率高: 使用栈结构单次遍历即可完成
易于构建表达式树: 后序表达式天然适合构建二叉树

2.2 数据结构:二叉表达式树

对于表达式 (a && b) || c,构建的二叉树为:

       ||
      /  \
    &&    c
   /  \
  a    b

优势:

树形结构直观表达运算优先级
支持递归求值
便于实现短路求值优化

2.3 转换算法:调度场算法(Shunting Yard Algorithm)

由 Edsger Dijkstra 发明,用于将中缀表达式转换为后序表达式。

算法核心思想:

使用两个数据结构:输出队列、运算符栈
遍历中缀表达式的每个 token:
- 操作数直接进入输出队列
- 左括号压入栈
- 右括号则弹出栈顶元素到输出队列,直到遇到左括号
- 运算符则根据优先级决定是否先弹栈

时间复杂度: O(n),空间复杂度 O(n)

三、架构设计

3.1 整体架构

┌─────────────────────────────────────────┐
│         LSYConditionAdjudicator         │  (外观类)
│                                         │
│  + calculateWithExpressionString:...    │
└─────────────┬───────────────────────────┘
              │
              ├──> [1] Infix to Postfix (调度场算法)
              │
              ├──> [2] Build Expression Tree (构建二叉树)
              │
              └──> [3] Recursive Evaluation (递归求值)
                         │
                         └──> LSYConditionOperator Protocol
                                   │
                     ┌─────────────┼──────────────┐
                     │             │              │
              NumberComparison  StringOps   LogicalOps
                (>, <, >=, <=)  (startWith) (&&, ||)

3.2 核心类职责划分

类名	职责	设计原则
`LSYConditionAdjudicator`	统一入口,协调整个求值流程	外观模式 + 单一职责
`LSYConditionOperator`	运算符协议,定义运算符行为	接口隔离原则
`LSYOperateNode`	二叉树节点,存储运算符和子树	数据结构封装
`LSYConditionOperatorXXX`	具体运算符实现类	策略模式 + 开放封闭原则

3.3 设计模式应用

3.3.1 策略模式(Strategy Pattern)

每个运算符是一个独立的策略类,实现 LSYConditionOperator 协议:

@protocol LSYConditionOperator <NSObject>
- (NSString *)operatorString;  // 运算符符号
- (int)priority;               // 优先级
- (BOOL)calculateWithLeftOperand:(id)left rightOperand:(id)right error:(NSError **)error;
@optional
- (LSYConditionOperandType)leftOperandType;   // 左运算数类型约束
- (LSYConditionOperandType)rightOperandType;  // 右运算数类型约束
@end

好处:

新增运算符无需修改核心代码
每个运算符独立测试、维护

3.3.2 工厂模式(Factory Pattern)

通过 OperatorMap.plist 配置文件映射运算符字符串到具体类:

<key>&&</key>
<string>LSYConditionOperatorAnd</string>
<key>startWith</key>
<string>LSYConditionOperatorStartWith</string>

运行时动态创建运算符实例:

+ (NSDictionary<NSString *,id<LSYConditionOperator>> *)operatorMap {
    static NSDictionary *operatorMap = nil;
    if (!operatorMap) {
        NSDictionary *originMap = [NSDictionary dictionaryWithContentsOfFile:path];
        NSMutableDictionary *dic = [NSMutableDictionary new];
        for (NSString *operatorStr in originMap.allKeys) {
            id<LSYConditionOperator> operator = [NSClassFromString(originMap[operatorStr]) new];
            [dic setObject:operator forKey:operatorStr];
        }
        operatorMap = dic.copy;
    }
    return operatorMap;
}

优势:

配置驱动,易于管理
延迟加载,按需创建

3.3.3 外观模式(Facade Pattern)

LSYConditionAdjudicator 对外提供简单统一的接口,隐藏内部复杂逻辑:

+ (BOOL)calculateWithExpressionString:(NSString *)expressionString
                               target:(id)target
                              context:(NSDictionary *)context
                                error:(NSError **)error;

用户无需关心内部的"中缀转后序"、"构建树"、"递归求值"等细节。

四、核心实现详解

4.1 中缀表达式转后序表达式

输入: ( a && b ) || c
输出: a b && c ||

实现代码核心逻辑 (简化版):

+ (NSArray *)postfixExpressionArrayWithString:(NSString *)expressionString error:(NSError **)error {
    NSArray *tokens = [expressionString componentsSeparatedByString:@" "];
    NSMutableArray *output = [NSMutableArray new];  // 输出队列
    NSMutableArray *stack = [NSMutableArray new];   // 运算符栈
    
    for (NSString *token in tokens) {
        if ([token isEqualToString:@"("]) {
            [stack addObject:token];  // 左括号入栈
        }
        else if ([token isEqualToString:@")"]) {
            // 右括号:弹栈直到遇到左括号
            while (![stack.lastObject isEqualToString:@"("]) {
                [output addObject:stack.lastObject];
                [stack removeLastObject];
            }
            [stack removeLastObject];  // 弹出左括号
        }
        else if ([self isOperator:token]) {
            // 运算符:根据优先级判断是否弹栈
            while (stack.count > 0 && 
                   [self priorityOf:stack.lastObject] >= [self priorityOf:token]) {
                [output addObject:stack.lastObject];
                [stack removeLastObject];
            }
            [stack addObject:token];
        }
        else {
            [output addObject:token];  // 操作数直接输出
        }
    }
    
    // 将栈中剩余运算符全部输出
    while (stack.count > 0) {
        [output addObject:stack.lastObject];
        [stack removeLastObject];
    }
    
    return output;
}

关键点:

使用栈处理运算符优先级
括号通过栈的入栈/出栈机制消除
最终输出即为后序表达式

4.2 构建二叉表达式树

输入: 后序表达式 a b && c ||
输出: 二叉树

算法思路:

遍历后序表达式
遇到操作数则入栈
遇到运算符则弹出两个栈顶元素作为左右子树,构建新节点后入栈

实现代码:

+ (LSYOperateNode *)operateTreeWithPostfixExpressionArray:(NSArray *)array error:(NSError **)error {
    NSMutableArray *stack = [NSMutableArray new];
    
    for (NSString *token in array) {
        if ([self isOperator:token]) {
            // 遇到运算符:弹出两个元素构建树节点
            LSYOperateNode *node = [LSYOperateNode new];
            node.value = token;
            node.right = stack.lastObject;  // 先弹出的是右子树
            [stack removeLastObject];
            node.left = stack.lastObject;   // 后弹出的是左子树
            [stack removeLastObject];
            [stack addObject:node];
        } else {
            // 遇到操作数:直接入栈
            [stack addObject:token];
        }
    }
    
    return stack.lastObject;  // 栈顶即为树根
}

树节点定义:

@interface LSYOperateNode : NSObject
@property (strong, nonatomic) id value;   // 运算符字符串
@property (strong, nonatomic) id left;    // 左子树(可能是 LSYOperateNode 或操作数字符串)
@property (strong, nonatomic) id right;   // 右子树
@end

4.3 递归求值与短路优化

核心思路:

后序遍历表达式树
叶子节点:解析变量或常量
非叶子节点:调用运算符的 calculate 方法

关键优化:短路求值

对于逻辑运算符 && 和 ||,实现短路求值:

+ (BOOL)calculateNode:(LSYOperateNode *)node 
           withTarget:(id)target 
              context:(NSDictionary *)context 
                error:(NSError **)error {
    
    id<LSYConditionOperator> operator = [self operatorForString:node.value];
    
    // 1. 计算左子树
    id leftOperand = [self evaluateSubtree:node.left target:target context:context error:error];
    
    // 2. 短路求值优化
    if ([node.value isEqualToString:@"&&"]) {
        if (![leftOperand boolValue]) {
            return NO;  // 左侧为假,无需计算右侧
        }
    } else if ([node.value isEqualToString:@"||"]) {
        if ([leftOperand boolValue]) {
            return YES;  // 左侧为真,无需计算右侧
        }
    }
    
    // 3. 计算右子树
    id rightOperand = [self evaluateSubtree:node.right target:target context:context error:error];
    
    // 4. 调用运算符执行计算
    return [operator calculateWithLeftOperand:leftOperand 
                                rightOperand:rightOperand 
                                       error:error];
}

性能收益:

对于表达式 falseCondition && expensiveOperation(),右侧不会执行
在复杂条件链中能显著减少计算量

4.4 变量解析与类型转换

支持三种变量类型:

对象属性: $var{userInfo.userId} → 使用 KVC 解析
上下文参数: $context{source} → 从 context 字典取值
常量: 18、Tom、${null}

解析实现:

+ (id)parseOperand:(id)operand withTarget:(id)target context:(NSDictionary *)context {
    if ([operand isKindOfClass:[NSString class]]) {
        if ([operand isEqualToString:@"${null}"]) {
            return nil;
        }
        else if ([operand hasPrefix:@"$var{"]) {
            // 提取 KeyPath
            NSString *keyPath = [operand substringWithRange:NSMakeRange(5, operand.length - 6)];
            return [target valueForKeyPath:keyPath];  // KVC 取值
        }
        else if ([operand hasPrefix:@"$context{"]) {
            // 提取 key
            NSString *key = [operand substringWithRange:NSMakeRange(9, operand.length - 10)];
            return [context objectForKey:key];
        }
        // 处理空格转义
        operand = [operand stringByReplacingOccurrencesOfString:@"$space{}" withString:@" "];
        // 处理字符串转义
        if ([operand hasPrefix:@"$s{"]) {
            operand = [operand substringWithRange:NSMakeRange(3, operand.length - 4)];
        }
    }
    return operand;
}

类型转换:

运算符可指定运算数类型,引擎会自动转换:

+ (id)transformOperand:(id)operand 
              withType:(LSYConditionOperandType)type 
           operatorStr:(NSString *)operatorStr 
         isLeftOperand:(BOOL)isLeft 
                 error:(NSError **)error {
    switch (type) {
        case LSYConditionOperandTypeNumber:
            if ([operand isKindOfClass:[NSString class]]) {
                NSNumberFormatter *formatter = [NSNumberFormatter new];
                NSNumber *result = [formatter numberFromString:operand];
                if (result) return result;
            }
            // 转换失败,报错
            *error = [NSError errorWithDomain:@"com.lsy.PostfixExpression" code:-1 
                     userInfo:@{NSLocalizedDescriptionKey: 
                                [NSString stringWithFormat:@"%@运算%@参数必须是数字",
                                 operatorStr, isLeft?@"左":@"右"]}];
            return nil;
            
        case LSYConditionOperandTypeString:
            if (![operand isKindOfClass:[NSString class]]) {
                *error = [NSError errorWithDomain:@"com.lsy.PostfixExpression" code:-1 
                         userInfo:@{NSLocalizedDescriptionKey: 
                                    [NSString stringWithFormat:@"%@运算%@参数必须是字符串",
                                     operatorStr, isLeft?@"左":@"右"]}];
            }
            return operand;
            
        default:
            return operand;
    }
}

五、运算符扩展实战

5.1 现有运算符实现示例

数值比较运算符:

@implementation LSYConditionOperatorGreaterThan

- (NSString *)operatorString { return @">"; }
- (int)priority { return 3; }

- (LSYConditionOperandType)leftOperandType {
    return LSYConditionOperandTypeNumber;
}

- (LSYConditionOperandType)rightOperandType {
    return LSYConditionOperandTypeNumber;
}

- (BOOL)calculateWithLeftOperand:(id)leftOperand 
                   rightOperand:(id)rightOperand 
                          error:(NSError **)error {
    return [leftOperand compare:rightOperand] == NSOrderedDescending;
}

@end

字符串运算符:

@implementation LSYConditionOperatorStartWith

- (NSString *)operatorString { return @"startWith"; }
- (int)priority { return 3; }

- (LSYConditionOperandType)leftOperandType {
    return LSYConditionOperandTypeString;
}

- (LSYConditionOperandType)rightOperandType {
    return LSYConditionOperandTypeString;
}

- (BOOL)calculateWithLeftOperand:(id)leftOperand 
                   rightOperand:(id)rightOperand 
                          error:(NSError **)error {
    return [leftOperand hasPrefix:rightOperand];
}

@end

5.2 自定义运算符示例

需求: 添加正则匹配运算符 matches

步骤1: 创建运算符类

// LSYConditionOperatorRegex.h
@interface LSYConditionOperatorMatches : NSObject <LSYConditionOperator>
@end

// LSYConditionOperatorRegex.m
@implementation LSYConditionOperatorMatches

- (NSString *)operatorString {
    return @"matches";
}

- (int)priority {
    return 3;
}

- (LSYConditionOperandType)leftOperandType {
    return LSYConditionOperandTypeString;
}

- (LSYConditionOperandType)rightOperandType {
    return LSYConditionOperandTypeString;
}

- (BOOL)calculateWithLeftOperand:(id)leftOperand 
                   rightOperand:(id)rightOperand 
                          error:(NSError **)error {
    NSError *regexError = nil;
    NSRegularExpression *regex = [NSRegularExpression 
        regularExpressionWithPattern:rightOperand 
                             options:0 
                               error:&regexError];
    
    if (regexError) {
        *error = [NSError errorWithDomain:@"com.lsy.RegexOperator" 
                                     code:-1 
                                 userInfo:@{NSLocalizedDescriptionKey: @"正则表达式格式错误"}];
        return NO;
    }
    
    NSRange range = [regex rangeOfFirstMatchInString:leftOperand 
                                             options:0 
                                               range:NSMakeRange(0, leftOperand.length)];
    return range.location != NSNotFound;
}

@end

步骤2: 在 OperatorMap.plist 中注册

<key>matches</key>
<string>LSYConditionOperatorMatches</string>

步骤3: 使用

NSString *expression = @"$var{email} matches ^[a-zA-Z0-9]+@[a-zA-Z0-9]+\\.[a-zA-Z]{2,}$";
BOOL result = [LSYConditionAdjudicator calculateWithExpressionString:expression 
                                                             target:user 
                                                            context:nil 
                                                              error:nil];

六、架构设计原则分析

6.1 SOLID 原则应用

6.1.1 单一职责原则(Single Responsibility Principle)

实践:

LSYConditionAdjudicator: 仅负责协调整体流程
LSYConditionOperatorAnd: 仅负责逻辑与运算
LSYOperateNode: 仅负责存储树节点数据

好处: 每个类职责清晰,易于维护和测试

6.1.2 开放封闭原则(Open/Closed Principle)

实践:

核心引擎对修改封闭:新增运算符无需改动 LSYConditionAdjudicator
对扩展开放:通过实现 LSYConditionOperator 协议即可扩展

示例: 上述添加正则运算符,零修改核心代码

6.1.3 里氏替换原则(Liskov Substitution Principle)

实践:
所有运算符实现类都可替换为 id<LSYConditionOperator> 类型使用:

id<LSYConditionOperator> operator = [[self operatorMap] objectForKey:operatorStr];
BOOL result = [operator calculateWithLeftOperand:left rightOperand:right error:error];

无论具体是哪个运算符类,调用方式一致。

6.1.4 接口隔离原则(Interface Segregation Principle)

实践:
协议中使用 @optional 标记可选方法:

@protocol LSYConditionOperator <NSObject>
@required
- (NSString *)operatorString;
- (int)priority;
- (BOOL)calculateWithLeftOperand:(id)left rightOperand:(id)right error:(NSError **)error;

@optional
- (LSYConditionOperandType)leftOperandType;
- (LSYConditionOperandType)rightOperandType;
@end

不需要类型约束的运算符(如 ==)无需实现 leftOperandType 方法。

6.1.5 依赖倒置原则(Dependency Inversion Principle)

实践:
核心引擎依赖抽象协议,而非具体实现:

// 依赖抽象
id<LSYConditionOperator> operator = ...;
BOOL result = [operator calculateWithLeftOperand:...];

// 而非依赖具体类
LSYConditionOperatorAnd *andOperator = ...;

好处: 解耦,易于替换和测试(可注入 Mock 对象)

6.2 其他设计亮点

6.2.1 错误处理

使用 NSError ** 双指针传递错误信息:

NSError *error = nil;
BOOL result = [LSYConditionAdjudicator calculateWithExpressionString:expr 
                                                             target:target 
                                                            context:context 
                                                              error:&error];
if (error) {
    NSLog(@"错误: %@", error.localizedDescription);
}

优势:

符合 Objective-C 的错误处理惯例
可携带详细错误信息(domain、code、userInfo)
区分"计算结果为假"和"计算过程出错"

6.2.2 惰性解析

变量仅在求值时才通过 KVC 取值:

id result = [target valueForKeyPath:@"userInfo.userId"];

好处:

避免不必要的数据访问(短路求值时部分变量不会解析)
降低内存占用

七、性能优化与测试

7.1 性能优化手段

短路求值: 逻辑运算符提前退出
单例缓存: 运算符映射表复用
算法复杂度:
- 中缀转后序: O(n)
- 构建树: O(n)
- 递归求值: O(n)
- 总体: O(n),n 为表达式 token 数量

7.2 测试用例示例

// 测试短路求值
NSString *expr = @"$var{falseCondition} && $var{expensiveOperation}";
// expensiveOperation 不应被访问

// 测试括号优先级
NSString *expr = @"( $var{a} == 1 || $var{b} == 2 ) && $var{c} == 3";

// 测试类型转换
NSString *expr = @"$var{stringNumber} > 100";  // "200" 自动转为 200

// 测试错误处理
NSString *expr = @"$var{age} > notANumber";  // 应返回类型错误

// 测试嵌套对象
NSString *expr = @"$var{user.profile.settings.theme} == dark";

八、实际应用案例

8.1 A/B 测试系统

服务端配置:

{
  "experimentId": "newUI_2024",
  "targetRule": "$var{userId} in 1000,2000,3000 && $var{vipLevel} >= 2 && $context{platform} == iOS"
}

客户端判断:

NSDictionary *context = @{@"platform": @"iOS"};
BOOL shouldShowNewUI = [LSYConditionAdjudicator 
    calculateWithExpressionString:rule 
                           target:currentUser 
                          context:context 
                            error:nil];

8.2 动态权限控制

场景: 根据用户角色和资源属性决定访问权限

NSString *rule = @"( $var{role} == admin || $var{role} == moderator ) && $var{resource.isPublic} == 1";
BOOL canAccess = [LSYConditionAdjudicator calculateWithExpressionString:rule 
                                                               target:user 
                                                              context:@{...} 
                                                                error:nil];

8.3 智能推送

规则: VIP 用户且最近7天未登录且消息未读数>5

NSString *rule = @"$var{vipLevel} > 0 && $var{daysSinceLastLogin} > 7 && $var{unreadCount} > 5";

九、技术总结与展望

9.1 技术亮点

算法选择合理: 调度场算法 + 二叉树,经典且高效
架构设计优秀: 严格遵循 SOLID 原则,扩展性强
工程实践到位: 错误处理完善,性能优化充分
代码质量高: 职责清晰,易读易维护

9.2 可改进方向

节点增加权值：LSYOperateNode增加权值，表示子树层数，计算时根据左右节点权值决定计算顺序，可避免无效计算
增强类型系统: 当前类型检查较弱,可引入更严格的类型系统
表达式缓存: 对于频繁计算的相同表达式,可缓存后序表达式和表达式树
调试支持: 提供表达式执行日志,方便调试
更多运算符: 支持三元运算符、位运算等

9.3 适用场景

✅ 适合:

动态业务规则
服务端配置驱动
中小规模表达式(<100 tokens)

❌ 不适合:

高频实时计算(建议预编译)
复杂图灵完备脚本(建议使用 JavaScript Core)