括弧補完アルゴリズムでイライラする問題に直面しています。私が使用している数学ライブラリ DDMathParser は、ラジアン単位の三角関数のみを処理します。学位を使用したい場合は、 に電話する必要がありますdtor(deg_value)。問題は、これにより、最後に説明する必要がある追加の括弧が追加されることです。
たとえば、数式は私のコードでsin(cos(sin(x)))は に変換さsin(dtor(cos(dtor(sin(dtor(x)))れます。ただし、完全な数式にするためには、2 つの追加の括弧が必要であることに注意してください。したがって、の作成resolve_dtor()。
これが私の試みた解決策です。アイデアは0、左括弧を1意味し、左括弧を dtor(で意味し、右括弧を意味して、またはのいずれか2を完成させることでした。01
- (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))です。
結論
この半解決策はおそらく過度に複雑です (私の一般的な問題の 1 つと思われます)。
解決
彼が提供した@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;
}
できます！追加したほうがよい小さな修正があるか、またはより効率的なアプローチがあるかどうかをお知らせください。