`resolve_dtor()‘`Parentheses算法

Question

使用圆括号完成算法，我遇到了一个令人沮丧的问题。我使用的数学库，DDMathParser，只处理弧度的三角函数。如果一个人想使用学位，他们必须调用dtor(deg_value)。问题是，这增加了一个额外的括号，必须在末尾说明。

例如，数学表达式sin(cos(sin(x)))将在我的代码中转换为sin(dtor(cos(dtor(sin(dtor(x)))。但是，请注意，为了使它成为一个完整的数学表达式，我需要两个额外的括号。因此，创建了resolve_dtor()。

这是我尝试的解决方案，这个想法是让0表示左-p轮，1表示左-p轮与dtor(，2表示右-p轮，从而完成0或1。

- (NSMutableString *)resolve_dtor:(NSMutableString *)exp
{
    NSInteger mutable_length = [exp length];
    NSMutableArray *paren_complete = [[NSMutableArray alloc] init];     // NO/YES

    for (NSInteger index = 0; index < mutable_length; index++) {

        if ([exp characterAtIndex:index] == '(') {

            // Check if it is "dtor()"
            if (index > 5 && [[exp substringWithRange:NSMakeRange(index - 4, 4)] isEqual:@"dtor"]) {
                //dtor_array_index = [self find_incomplete_paren:paren_complete];
                [paren_complete addObject:@1];
            }
            else
                [paren_complete addObject:@0];      // 0 signifies an incomplete parenthetical expression
        }
        else if ([exp characterAtIndex:index] == ')' && [paren_complete count] >= 1) {

            // Check if "dtor("
            if (![self elem_is_zero:paren_complete]) {
                // Add right-paren for "dtor("
                [paren_complete replaceObjectAtIndex:[self find_incomplete_dtor:paren_complete] withObject:@2];
                [exp insertString:@")" atIndex:index + 1];
                mutable_length++;
                index++;
            }
            else
                [paren_complete replaceObjectAtIndex:[self find_incomplete_paren:paren_complete] withObject:@2];
        }
        else if ([paren_complete count] >= 1 && [[paren_complete objectAtIndex:0] isEqualToValue:@2]) {
            // We know that everything is complete
            [paren_complete removeAllObjects];
        }
    }

    return exp;
}

- (bool)check_dtor:(NSMutableString *)exp
{
    NSMutableArray *paren_complete = [[NSMutableArray alloc] init];     // NO/YES

    for (NSInteger index = 0; index < [exp length]; index++) {

        if ([exp characterAtIndex:index] == '(') {

            // Check if it is "dtor()"
            if (index > 5 && [[exp substringWithRange:NSMakeRange(index - 4, 4)] isEqual:@"dtor"]) {
                //dtor_array_index = [self find_incomplete_paren:paren_complete];
                [paren_complete addObject:@1];
            }
            else
                [paren_complete addObject:@0];      // 0 signifies an incomplete parenthetical expression
        }
        else if ([exp characterAtIndex:index] == ')' && [paren_complete count] >= 1) {

            // Check if "dtor("
            if (![self elem_is_zero:paren_complete]) {
                // Indicate "dtor(" at index is now complete
                [paren_complete replaceObjectAtIndex:[self find_incomplete_dtor:paren_complete] withObject:@2];
            }
            else
                [paren_complete replaceObjectAtIndex:[self find_incomplete_paren:paren_complete] withObject:@2];
        }
        else if ([paren_complete count] >= 1 && [[paren_complete objectAtIndex:0] isEqualToValue:@2]) {
            // We know that everything is complete
            [paren_complete removeAllObjects];
        }
    }

    // Now step back and see if all the "dtor(" expressions are complete
    for (NSInteger index = 0; index < [paren_complete count]; index++) {
        if ([[paren_complete objectAtIndex:index] isEqualToValue:@0] || [[paren_complete objectAtIndex:index] isEqualToValue:@1]) {
            return NO;
        }
    }

    return YES;
}

该算法似乎适用于sin((3 + 3) + (6 - 3)) (转换为sin(dtor((3 + 3) x (6 - 3)))，而不适用于sin((3 + 3) + cos(3)) (转换为sin(dtor((3 + 3) + cos(dtor(3)) )。

底线

这个半解决方案很可能过于复杂(似乎是我常见的问题之一)，所以我想知道是否有更简单的方法来做到这一点？

解决方案

以下是他提供的@j_random_ Here伪代码的解决方案：

- (NSMutableString *)resolve_dtor:(NSString *)exp
{
    uint depth = 0;
    NSMutableArray *stack = [[NSMutableArray alloc] init];
    NSRegularExpression *regex_trig = [NSRegularExpression regularExpressionWithPattern:@"(sin|cos|tan|csc|sec|cot)" options:0 error:0];
    NSRegularExpression *regex_trig2nd = [NSRegularExpression regularExpressionWithPattern:@"(asin|acos|atan|acsc|asec|acot)" options:0 error:0];
    // need another regex for checking asin, etc. (because of differing index size)
    NSMutableString *exp_copy = [NSMutableString stringWithString:exp];

    for (NSInteger i = 0; i < [exp_copy length]; i++) {
        // Check for it!
        if ([exp_copy characterAtIndex:i] == '(') {

            if (i >= 4) {
                // check if i - 4
                if ([regex_trig2nd numberOfMatchesInString:exp_copy options:0 range:NSMakeRange(i - 4, 4)] == 1) {
                    [stack addObject:@(depth)];
                    [exp_copy insertString:@"dtor(" atIndex:i + 1];
                    depth++;
                }
            }
            else if (i >= 3) {
                // check if i - 3
                if ([regex_trig numberOfMatchesInString:exp_copy options:0 range:NSMakeRange(i - 3, 3)] == 1) {
                    [stack addObject:@(depth)];
                    [exp_copy insertString:@"dtor(" atIndex:i + 1];
                    depth++;
                }
            }

        }
        else if ([exp_copy characterAtIndex:i] == ')') {
            depth--;
            if ([stack count] > 0 && [[stack objectAtIndex:[stack count] - 1]  isEqual: @(depth)]) {
                [stack removeObjectAtIndex:[stack count] - 1];
                [exp_copy insertString:@")" atIndex:i + 1];
            }
        }
    }

    return exp_copy;
}

它起作用了!请让我知道是否有任何小的更正将是好的补充，或如果有一个更有效的方法。

Answer 1

还没有尝试读取您的代码，但我会使用一种简单的方法，即在执行过程中向前扫描输入字符串，同时保留一个名为depth的变量，该变量记录当前的括号嵌套级别，以及一个堆栈，它记住需要额外)的嵌套级别，因为我们在输入它们时添加了一个dtor(：

• 将depth设置为0。
• 对于输入字符串中的每个字符c：
  • 把它写到输出中。
  • c是(吗？如果是：
    • 前面的令牌是sin、cos等吗？如果是这样的话，将depth的当前值推到堆栈上，并写出dtor(。
    • 增量depth

​

- Is `c` a `)`?  If so: 
    - Decrement `depth`.
    - Is the top of the stack equal to `depth`?  If so, pop it and write out `)`.

​

​

Answer 2

DDMathParser本机支持为三角函数使用学位，并将为您插入相关的dtor函数。它甚至会通过以下操作自动插入：

@"sin(42°)"

您可以通过在相关的angleMeasurementMode对象上设置DDMathEvaluator来做到这一点。