objective c - `resolve_dtor() `Parentheses Algorithm -

i'm running frustrating problem parentheses completion algorithm. math library i'm using, ddmathparser, processes trigonometric functions in radians. if 1 wishes use degrees, must call dtor(deg_value). problem adds additional parenthesis must accounted @ end.

for example, math expression sin(cos(sin(x))) translate sin(dtor(cos(dtor(sin(dtor(x))) in code. however, notice need 2 additional parentheses in order complete math expression. hence, creation of resolve_dtor().

here attempted solution, idea have 0 signify left-paren, 1 signify left-paren with dtor(, , 2 signify right-paren completing either 0 or 1.

- (nsmutablestring *)resolve_dtor:(nsmutablestring *)exp {     nsinteger mutable_length = [exp length];     nsmutablearray *paren_complete = [[nsmutablearray alloc] init];     // no/yes      (nsinteger index = 0; index < mutable_length; index++) {          if ([exp characteratindex:index] == '(') {              // check if "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 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 "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]) {             // know complete             [paren_complete removeallobjects];         }     }      return exp; }  - (bool)check_dtor:(nsmutablestring *)exp {     nsmutablearray *paren_complete = [[nsmutablearray alloc] init];     // no/yes      (nsinteger index = 0; index < [exp length]; index++) {          if ([exp characteratindex:index] == '(') {              // check if "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 incomplete parenthetical expression         }         else if ([exp characteratindex:index] == ')' && [paren_complete count] >= 1) {              // check if "dtor("             if (![self elem_is_zero:paren_complete]) {                 // indicate "dtor(" @ index 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]) {             // know complete             [paren_complete removeallobjects];         }     }      // step , see if "dtor(" expressions complete     (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 algorithm works sin((3 + 3) + (6 - 3)) (translating sin(dtor((3 + 3) x (6 - 3))) not sin((3 + 3) + cos(3)) (translating sin(dtor((3 + 3) + cos(dtor(3)).

bottom line

this semi-solution overcomplicated (one of common problems, seems), wondering if there might easier way this?

solution

here solution @j_random_hacker's pseudo code 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 regex checking asin, etc. (because of differing index size)     nsmutablestring *exp_copy = [nsmutablestring stringwithstring:exp];      (nsinteger = 0; < [exp_copy length]; i++) {         // check it!         if ([exp_copy characteratindex:i] == '(') {              if (i >= 4) {                 // check if - 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 - 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 minor corrections add or if there more efficient approach.

haven't tried reading code, use simple approach in scan forward through input string writing out second string go while maintaining variable called depth records current nesting level of parentheses, stack remembers nesting levels need ) because added dtor( when entered them:

• set depth 0.
• for each character c in input string:
  • write output.
  • is c (? if so:
    • was preceding token sin, cos etc.? if so, push current value of depth on stack, , write out dtor(.
    • increment depth.
  • is c )? if so:
    • decrement depth.
    • is top of stack equal depth? if so, pop , write out ).