`resol_dtor() ` Алгоритм скобок

Я сталкиваюсь с неприятной проблемой с алгоритмом завершения скобок. Используемая мной математическая библиотека DDMathParser обрабатывает только тригонометрические функции в радианах. Если кто-то хочет использовать степени, они должны позвонить dtor(deg_value), Проблема в том, что это добавляет дополнительные скобки, которые должны быть учтены в конце.

Например, математическое выражение sin(cos(sin(x))) будет переводить на sin(dtor(cos(dtor(sin(dtor(x))) в моем коде. Тем не менее, обратите внимание, что мне нужно две дополнительные скобки, чтобы это было полное математическое выражение. Следовательно, создание resolve_dtor(),

Вот моя попытка решения, идея состояла в том, чтобы 0 означать левую, 1 означать левую пареню с dtor(, а также 2 означать правый, таким образом завершая либо 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_hacker, который он предоставил:

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

Оно работает! Дайте мне знать, если есть какие-то незначительные исправления, которые было бы полезно добавить, или если есть более эффективный подход.

Источник

2 ответа

Решение

Я не пробовал читать ваш код, но я бы использовал простой подход, при котором мы сканируем вперед через строку ввода, записывая вторую строку, пока мы поддерживаем переменную с именем depth который записывает текущий уровень вложенности скобок, а также стек, который запоминает уровни вложенности, которые нуждаются в дополнительном ) потому что мы добавили dtor( когда мы вошли в них:

  • Задавать depth до 0.
  • Для каждого персонажа c во входной строке:
    • Запишите это в выходной.
    • Является c (? Если так:
      • Был ли предыдущий токен sin, cos так далее.? Если это так, нажмите текущее значение depth в стеке, и выписать dtor(,
      • инкремент depth,
    • Является c )? Если так:
      • декремент depth,
      • Вершина стека равна depth? Если так, выскакивают это и выписывают ),
Источник

DDMathParser изначально поддерживает использование градусов для тригонометрических функций и вставит соответствующие dtor функции для вас. Он даже автоматически вставит его, выполнив:

@"sin(42°)"

Вы можете сделать это, установив angleMeasurementMode на соответствующем DDMathEvaluator объект.

Источник
Другие вопросы по тегам