I'm running into a frustrating problem with a parentheses completion algorithm. The math library I'm using, DDMathParser, only processes trigonometric functions in radians. If one wishes to use degrees, they must call dtor(deg_value). The problem is that this adds an additional parenthesis that must be accounted for at the end.
For example, the math expression sin(cos(sin(x))) would translate to sin(dtor(cos(dtor(sin(dtor(x))) in my code. However, notice that I need two additional parentheses in order for it to be a complete math expression. Hence, the creation of resolve_dtor().
Here is my attempted solution, the idea was to have 0 signify a left-paren, 1 signify a left-paren with dtor(, and 2 signify a right-paren thus completing either 0 or 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;
}
It seems the algorithm works for sin((3 + 3) + (6 - 3)) (translating to sin(dtor((3 + 3) x (6 - 3))) but not sin((3 + 3) + cos(3)) (translating to sin(dtor((3 + 3) + cos(dtor(3)).
Bottom Line
This semi-solution is most likely overcomplicated (one of my common problems, it seems), so I was wondering if there might be an easier way to do this?
Here is my solution to @j_random_hacker's pseudo code he provided:
- (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;
}
It works! Let me know if there are any minor corrections that would be good to add or if there is a more efficient approach.
Haven't tried reading your code, but I would use a simple approach in which we scan forward through the input string writing out a second string as we go while maintaining a variable called depth that records the current nesting level of parentheses, as well as a stack that remembers the nesting levels that need an extra ) because we added a dtor( when we entered them:
depth to 0.c in the input string:
c a (? If so:
sin, cos etc.? If so, push the current value of depth on a stack, and write out dtor(.depth.c a )? If so:
depth.depth? If so, pop it and write out ).