我在使用括号完成算法时遇到了一个令人沮丧的问题。我正在使用的数学库 DDMathParser 仅以弧度处理三角函数。如果希望使用度数,则必须调用 dtor(deg_value)
。问题是这会添加一个必须在末尾说明的额外括号。
例如,数学表达式 sin(cos(sin(x)))
将转换为 sin(dtor(cos(dtor(sin(dtor(x))))
在我的代码中。但是,请注意,我需要两个额外的括号才能使其成为完整的数学表达式。因此,创建了 resolve_dtor()
。
这是我尝试的解决方案,想法是让 0
表示左括号,1
表示左括号 with 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;
}
有效!让我知道是否有任何可以添加的小修正,或者是否有更有效的方法。
最佳答案
没有尝试阅读您的代码,但我会使用一种简单的方法,我们向前扫描输入字符串,在我们进行时写出第二个字符串,同时维护一个名为 depth
的变量来记录括号的当前嵌套级别,以及记住需要额外 )
的嵌套级别的堆栈,因为我们在输入它们时添加了 dtor(
:
- 将
depth
设置为 0。 - 对于输入字符串中的每个字符
c
:- 将其写入输出。
c
是(
吗?如果是:- 前面的标记是
sin
、cos
等吗?如果是,则将depth
的当前值压入堆栈,并写出dtor(
. - 增加
深度
。
- 前面的标记是
c
是)
吗?如果是这样:- 减少
深度
。 - 栈顶是否等于
深度
?如果是,弹出它并写出)
。
- 减少
关于objective-c - `resolve_dtor() ` 括号算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24028784/