Code for Minimal Parentheses

CalculatorBrain.h

//
//  CalculatorBrain.h
//  Calculator
//
//  Created by Peter Polash on 7/2/12.
//  Copyright (c) 2012 Share. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface CalculatorBrain : NSObject

- (void) pushOperand:(double)operand;
- (double) performOperation: (NSString *)operation;
- (void) clearStack;
- (void) pushVariable: (NSString *)varName;
- (void) pop1ElementOffStack;

@property (readonly) id program;

+ (NSSet *) variablesUsedInProgram: (id) program;
+ (double) runProgram:(id) program;
+ (double) runProgram:(id)program
  usingVariableValues:(NSDictionary*) variableValues;
            
+ (NSString *) descriptionOfProgram:(id)program;

@end

CalculatorBrain.m

//
//  CalculatorBrain.m
//  Calculator
//
//  Created by Peter Polash on 7/2/12.
//  Copyright (c) 2012 Share. All rights reserved.
//

#import "CalculatorBrain.h"
#import "CalculatorOperand.h"

@interface CalculatorBrain()

@property (nonatomic, strong) NSMutableArray *programStack ;
@end

@implementation CalculatorBrain

@synthesize programStack = _programStack;

- (NSMutableArray *)programStack 
{
    if (! _programStack ) {
        _programStack = [ [NSMutableArray alloc] init ];
    }
    return _programStack;
}

-(void) pushOperand:(double)operand 
{
    NSNumber * operandObject = [ NSNumber numberWithDouble:operand ];
    [self.programStack addObject:operandObject ];

}

-(void) pop1ElementOffStack
{
    if ( (self.programStack) && ( [self.programStack count] > 0 ) ) {
        [self.programStack removeLastObject] ;
    }
}

-(void) pushVariable:(NSString *)varName
{
    [self.programStack addObject:varName ];
   
}

- (double) performOperation:(NSString *)operation
{
    [self.programStack addObject:operation];
    return [CalculatorBrain runProgram:self.program];
}

+ (double) runProgram:(id)program
{
    NSMutableArray *stack ;
    if ([program isKindOfClass:[NSArray class]]) {
        stack = [ program mutableCopy ];
    }
    return [self popOperandOffStack:stack];
}

+ (double) runProgram:(id)program usingVariableValues:(NSDictionary *) dicVarVals
{
    NSMutableArray *stack = NULL ;
    NSString *strVarName, *strVarValue ;
    id  idObj ;
    int i ;
    
    if ([program isKindOfClass:[NSArray class]]) 
    {
        
        // enumerate thru elements replacing variables with their current values
        stack = [ program mutableCopy ];
        
        if ( dicVarVals ) 
        {
            
            for ( i = 0 ; i < [stack count] ; ++i )
            {
                idObj = [stack objectAtIndex: i ] ;
                
                if ( [idObj isKindOfClass: [NSString class]] ){
                    strVarName = idObj ;
                    if ( [CalculatorBrain isStringAVariable : strVarName ] )
                    {
                        strVarValue = [dicVarVals valueForKey : strVarName] ;
                        if ( strVarValue ) 
                        {
                            double      dubVal = [ strVarValue doubleValue ] ;
                            NSNumber *  idNum = [ NSNumber numberWithDouble : dubVal ];
                            
                            [stack replaceObjectAtIndex:i withObject:idNum ];
                        }
                    }
                    
                }
            }
        }
    }
    return [self popOperandOffStack:stack];
}


- (id)program
{
    return [ self.programStack copy ];
}

                    

+ (double) popOperandOffStack: (NSMutableArray *) stack
{
    double result = 0 ;
    
    id topOfStack = [ stack lastObject ];
    if ( topOfStack ) [stack removeLastObject ];
    if ( [ topOfStack isKindOfClass:[NSNumber class]]) 
    {
        result = [ topOfStack   doubleValue ] ;
    } 
    else if ( [ topOfStack isKindOfClass:[NSString class]] )
    {
        NSString * operation = topOfStack ;
        
        if ( [self isStringAVariable:operation ] ) {
            result = 0 ;
        }else if ( [ operation isEqualToString:@"+"]){
            result = [ self popOperandOffStack:stack] + [self popOperandOffStack:stack ];
            
        } else if ([ operation isEqualToString:@"*"]) { 

            result = [ self popOperandOffStack:stack] * [ self popOperandOffStack:stack] ;
            
        } else if ([ operation isEqualToString:@"-"]) {
            double subtrahend = [ self popOperandOffStack:stack] ;
            result = [ self popOperandOffStack:stack] - subtrahend ;
            
        } else if ([ operation isEqualToString:@"/"]) {
            double divisor = [ self popOperandOffStack:stack] ;
            if (divisor) result = [ self popOperandOffStack:stack] / divisor ;
            
        } else if ([ operation isEqualToString:@"sin"]) {
            result = sin( [ self popOperandOffStack:stack] ) ;
            
        } else if ([ operation isEqualToString:@"cos"]) {
            result = cos( [ self popOperandOffStack:stack] ) ;
            
        } else if ([ operation isEqualToString:@"sqrt"]) {
            double argument = [ self popOperandOffStack:stack] ;
            if (argument >= 0 ) result = sqrt( argument ) ;
            
        } else if ([ operation isEqualToString:@"log"]) {
            double argument = [ self popOperandOffStack:stack] ;
            if (argument >= 0 ) result = log10 ( argument ) ;
            
        } else if ([ operation isEqualToString:@"e"]) {
            result = (double) M_E ;
            
        } else if ([ operation isEqualToString:@"∏"]) {
            result = (double) M_PI ;
            
        } else if ([ operation isEqualToString:@"+/-"] ) {
            result = - ( [ self popOperandOffStack:stack] ) ;
            
        } else if ( [ operation isEqualToString:@"Ent" ] ) {
            // the  "enter" operator gets a full operand, recursively, but using a stack copy so nothing is pulled of the actual stack. thus the full recursive result of operand is in result and is also available in the original stack
            
            NSMutableArray * stack2 = [ stack mutableCopy ]; 
            result = [ self popOperandOffStack:stack2] ;              
        }
    }
    return (result) ;
}



+ (NSString *) descriptionOfProgram: (id) program
{
    CalculatorOperand * opDesc ;
    NSMutableArray *stack ;
    NSString * description = @"";
    
    int     iCount = 0 ;
    
    if ([program isKindOfClass:[NSArray class]]) {
        stack = [ program mutableCopy ];
    }
    
    do {
        
        opDesc = [self descriptionOfTopOfStack:stack] ;
        description = [description  stringByAppendingString : opDesc.description];

        if  ((iCount = [stack count]))
        {
           description = [ description stringByAppendingString:@", "];
            
        }
    } while ( iCount ) ;
    return ( description );
}

+(CalculatorOperand *) descriptionOfTopOfStack: (NSMutableArray *) stack
{
    // For a full explanation of the logic in obtaining minimum parens and the use of the   
    // CalculatorOperand return object in these methods see the comments at the top the 
    // operandFr2ArgOperator() method, below.
    
    NSString * description = @"0" ;
    CalculatorOperand * opDesc ;
    
    opDesc = [CalculatorOperand newCalcOp:description multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
    
    id topOfStack = [ stack lastObject ];
    if ( topOfStack ) [stack removeLastObject ];
    if ( [ topOfStack isKindOfClass:[NSNumber class]] ) 
    {
        description = [ NSString stringWithFormat:@"%g", [ topOfStack   doubleValue ] ];
        opDesc = 
         [CalculatorOperand newCalcOp:description multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
    } 
    else if ([ topOfStack isKindOfClass:[NSString class]]) 
    {
        NSString * curString = topOfStack ;
        if ([CalculatorBrain isStringAVariable:curString ]) //a VARIABLE:  description= variable string, bools= FALSE, done
        {
            opDesc = [CalculatorOperand newCalcOp:curString multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
        }
        else                                    // Handle OPERATOR just pulled off stack
        {
            NSString *operator = curString ;      CalculatorOperand * arg1, *arg2;    NSMutableArray * stack2 ;
            
            switch ([ self numberOfArgsForOperator: operator]) {   // switch on the NUMBER OF ARGEUMENTS for operator
                case 0:    // an operator such as PI whose own string is returned as the description (booleans set to false)
                    opDesc = [CalculatorOperand newCalcOp:operator multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
                    break;
                case 1:           // a 1 argument operator
                    opDesc = [self operandFr1ArgOperator:operator argument:[self descriptionOfTopOfStack:stack]];
                    break;
                case 2:           // a 2 argument operator
                    arg2 = [self descriptionOfTopOfStack:stack];  arg1 = [self descriptionOfTopOfStack:stack];
                    opDesc = [self operandFr2ArgOperator:operator argument1:arg1 argument2:arg2];
                    break;
                case 3:          // special case: this is the Enter operator.   Here, we get a full operand recursively, using a COPY of the stack. Thus nothing (beyond the operator itself) is pulled off the actual stack. The full recursive result of operand goes to opDesc, and is still present in the original stack
                    stack2 = [ stack mutableCopy ] ;
                    opDesc = [ self descriptionOfTopOfStack: stack2] ; 
                    break ;
                default:
                    opDesc = 
                    [CalculatorOperand newCalcOp:@"operand error" multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
                    break;
            }
        }
        
    }
    return ( opDesc ) ;                   
    
} 

+ (int) numberOfArgsForOperator: (NSString *) operator
{
    static NSDictionary * dicNumberOfArgs = nil ;
    static NSNumber * n0, * n1, *n2, * n3 ;
    
    if ( ! dicNumberOfArgs )
    {
        n0 = [NSNumber numberWithInt:0];  n1 = [NSNumber numberWithInt:1] ;
        n2 = [NSNumber numberWithInt:2];  n3 = [NSNumber numberWithInt:3] ;
        
        dicNumberOfArgs = [NSDictionary dictionaryWithObjectsAndKeys:
                           n0, @"∏", n0, @"e",
                           n1, @"sqrt", n1, @"log", n1, @"sin", n1, @"cos", n1, @"+/-",
                           n2, @"+", n2, @"-", n2, @"/", n2, @"*",
                           n3, @"Ent",
                           nil] ;
    }
    
    int numArgs = 4 ;
    
    NSNumber * nsnNumArgs     = [ dicNumberOfArgs objectForKey: operator ] ;
    if ( nsnNumArgs ) numArgs = [ nsnNumArgs intValue ] ;

    return ( numArgs );
}


+ (CalculatorOperand *)   operandFr1ArgOperator: (NSString *)operator 
                                       argument: (CalculatorOperand *)argument
{
    CalculatorOperand * opDesc ;
    NSString * description ;
    
    if ( [operator isEqualToString:@"+/-"] ) { 
        //multiply by -1. Do so by calling operandFr2ArgOperator to build the operand, thus minimizing parens
        opDesc =  [self 
           operandFr2ArgOperator: @"*" 
                       argument1: [CalculatorOperand newCalcOp:@"(-1)" multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE]
                       argument2: argument ] ;
    } else {

        description = [NSString stringWithFormat: @"%@(%@)", operator, argument.description ];
    
        opDesc = [CalculatorOperand newCalcOp:description multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
    }
    return ( opDesc ) ;
}

+ (CalculatorOperand *)   operandFr2ArgOperator: (NSString *) operator 
                                      argument1: (CalculatorOperand *) arg1
                                      argument2: (CalculatorOperand *) arg2
{
// The recursive method, "descriptionOfTopOfStack", returns a CalculatorOperand object rather 
// than a string. This method does the same. 

// Notes on the RETURN OBJECT "CalculatorOperand": 
// Its properties are:    description, multiTerms, multifacter, hasDivisor.

// - description -  is the pointer to an NSString like "(a*b*PI+3+4a)/((a+b)+(c+d))", or "3", or "a"
//         The following booleans describe the operand in the object's description string. 
//         A property of an operand is set to FALSE if it exists only inside parentheses of the operand
// - muliTerms -    is TRUE for operands like "a+b", or for "a*b + c*d", but FALSE for "(a+b)*c"
// - multiFactors - is TRUE for operands like "a*b*c", or "a*b*c/d", but FALSE for "a*b + b*c" or "SQRT(a*b)"
// - hasDivisor -   is TRUE for operands like "a/b", or "a*3/(b*c*d)", but FALSE for "(a/b)*c" or "a/b + c/d"
          

/*
    // TIMING wise, the booleans and associated description string will be evaluated for a deepest 
level of recursion first (ie  for the simplest expressions first, such as a simple number or 
variable) and returned to its recursive caller BEFORE they're used by that recursive caller, 
(or to/by recursive callers earlier in the call chain). 

    // Each recursive caller uses ONLY the booleans it receives from a deeper call (along with its 
current operator) to determine the need for parens (which it adds to an operand's description 
string, if needed). It then sets up OUTPUT booleans (in the output operand object, opDesc) to be 
returned to (and similarly used by) ITS recursive caller. 
    
    // Output booleans are detemined only as a function of the current operator and the input booleans, 
already gotten for the current arguments. Thus we never need to search our description strings 
to determine the need for parens or for creating new booleans

    // The expression for a deep recursion gets more and more complex as it returns up the chain, 
always getting and using booleans (from the deeper call) to create the new description string and 
set the new booleans, which IT then returns.
    
    // Also note that this function is being called by descriptionOfTopOfStack. The arguments arg1 
and arg2 are CalculatorOperand objects that have their own booleans and desrcription string, all 
of which have already been returned by a deeper recursive call to descriptionOfTopOfStack, (made 
by our caller, descriptionOfTopOfStack, just before it called us) 
    
    // I've chosen to use parens where needed to make the description intuitively understandable, 
even if not required mathematically.  eg. I'm creating strings like "(a/d)*e" rather than "a/d*e", 
even though the latter is well defined, given that it's not always well understood. We could  
avoid such "mathematically unneccessary" parens, by eliminating the test of hasDivisor below. 
*/    
    NSString * description ;
    CalculatorOperand * opDesc ; // This is the return result
    
    // First init a new result-CalculatorOperand ( opDesc ), setting ALL BOOLEANS to a default value of FALSE
    // For the current operator, we'll apply parens to each input operand, if needed, and set the OUTPUT booleans    
    // Finally, at the bottom, get the output description string by sandwiching the 
    //  operator with the (potentially modified) input operand descriptions 
 
    opDesc = [CalculatorOperand newCalcOp:description multiTerms:FALSE multiFactors:FALSE hasDivisor:FALSE];
   
    if ([ operator isEqualToString:@"+" ])      // addition always combines operands with no additional parens needed
    {
        opDesc.multiTerms = TRUE ;    // this boolean is used for the return result. For "+", other bools get FALSE by default

    } else if ([ operator isEqualToString:@"-" ]) {  // subtraction only adds parens to right side, (if it has mutiple terms)

        if ( arg2.multiTerms )  [arg2 operandByAddingParens] ;// put parens on the outside of arg2 string, resets arg2 bools
        opDesc.multiTerms = TRUE ;                            // the output multiTerm boolean, other bools default to FALSE
    
    } else {   // for MILTIPLY AND DIVIDE. first for multiTerms in arg1, arg2 add parens, tests work for both mult or divide 
        
        if ( arg1.multiTerms ) [arg1 operandByAddingParens]; // put parens on the outside of arg1's string. resets arg1 bools
        if ( arg2.multiTerms ) [arg2 operandByAddingParens]; //   likewise
       
        if ([ operator isEqualToString:@"/" ])      // for DIVIDE ONLY
        {             
            if ( arg2.multiFactors ) {
                [arg2 operandByAddingParens];  //eg, output desc will get "a/(b*c)", not "a/b*c"
                if (arg1.multiFactors) [arg1 operandByAddingParens] ;// "(a*b)/(c*d)/(e*f)" not ""a*b/(c*d/(e*f))""
            }
            opDesc.multiFactors = arg1.multiFactors ;  opDesc.hasDivisor = TRUE; //if arg2 had factors, the line above hid it
            
            // If we'll be returning something like "a*b/c" (ie, a*b is in arg1) then the ouput multiFactors needs to be true, and we'll have gotten that status from our input arg1.multiFactors, in the line above. 
        }
        else                                        // for MULTIPLY only
        {
            if ( arg1.hasDivisor )  {
                [arg1 operandByAddingParens]; //eg, output will get "(a/b)*c" not "a/b*c", reset bools
                if (arg2.hasDivisor) [arg2 operandByAddingParens];//"(a/b)*(c/d)*(e/f)" not "((a/b)*c/d)*e/f" 
                   // *** Thanks to David Barton for suggesting the line above, it's a very sweet addition ***
            }
            opDesc.multiFactors = TRUE;  opDesc.hasDivisor = arg2.hasDivisor; //if arg1 had a divisor, the line above hid it
        }
        
    }

    // now create our resulting description string by sandwiching our operator with our newly modified arguments

    opDesc.description = [NSString stringWithFormat:@"%@%@%@", arg1.description, operator, arg2.description] ;

    return ( opDesc ) ;
}

+ (NSSet *)variablesUsedInProgram:(id)program
{
    NSArray * stack ;
    NSMutableSet * varSet = nil ;  // initialize the return value to NIL which will be RETAINED unless a true variable if found
    NSString * str;
    
    if ([program isKindOfClass:[NSArray class]]) {
        stack = program;
        
        NSEnumerator *enumerator = [stack objectEnumerator];
        id element;
        
        while (element = [enumerator nextObject]) 
        {
            /* code to act on each element as it is returned */
            
            if ( [ element isKindOfClass:[NSString class]] )
            {
                str = element ;
                if ( [self isStringAVariable : str ] ){
                    if ( ! varSet ) varSet = [NSMutableSet set] ;        //init to empty set now that we have a true var
                    [varSet addObject: str ] ;  
                }
            }
        }
        
    }
    
    return ( varSet ) ; 
}

+ (BOOL) isStringAVariable : (NSString*) string 
{
    return ( [string isEqualToString:@"a" ] || [string isEqualToString:@"b" ] || [string isEqualToString:@"X" ] ) ;
}


- (void) clearStack
{
    [ self.programStack removeAllObjects ];
}


@end

CalculatorOperand.h

//
//  CalculatorOperand.h
//  Calculator
//
//  Created by Peter Polash on 7/8/12.
//  Copyright (c) 2012 Share. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface CalculatorOperand : NSObject

// used to hold description and properties of operands as they are being combined during recursion

@property (nonatomic) NSString * description;// text descr of the operand thus (in recursion) far eg. "(a+b)"
@property BOOL multiTerms ; // does the operand have mutlitple terms, eg. "a+b" does, but "(a+b)*c" doesn't
@property BOOL multiFactors ; // does the operand have multiple factors. "a*b" does, but "(a+b)/c" doesn't
@property BOOL hasDivisor ;// does the operand have a divisor, "a/b" does. "a" doesn't and "(a/b)" doesn't


+ (CalculatorOperand*) newCalcOp: (NSString*) description
                      multiTerms: (BOOL) multiTerms
                    multiFactors: (BOOL) multiFactors
                      hasDivisor: (BOOL) hasDivisor;

- (void) operandByAddingParens ;


@end

CalculatorOperand.m

//
//  CalculatorOperand.m
//  Calculator
//
//  Created by Peter Polash on 7/8/12.
//  Copyright (c) 2012 Share. All rights reserved.
//

#import "CalculatorOperand.h"

@implementation CalculatorOperand

@synthesize description ;
@synthesize multiTerms ;
@synthesize multiFactors ;
@synthesize hasDivisor ;


+ (CalculatorOperand*) newCalcOp: (NSString*) description
                      multiTerms: (BOOL)      multiTerms
                    multiFactors: (BOOL)      multiFactors
                      hasDivisor: (BOOL)      hasDivisor
{
    CalculatorOperand *calcOperand ;
    
    calcOperand = [[CalculatorOperand alloc] init];
    
    calcOperand.description  = description ;
    calcOperand.multiTerms   = multiTerms;
    calcOperand.multiFactors = multiFactors ;
    calcOperand.hasDivisor   = hasDivisor;
    
    return (calcOperand);
}

- (void) operandByAddingParens
{   
    NSString * newDesc = [@"(" stringByAppendingString:self.description ];

    self.description  = [ newDesc stringByAppendingString:@")" ] ;
    self.multiTerms   = FALSE ;
    self.multiFactors = FALSE ;
    self.hasDivisor   = FALSE ;
               
    return ;
}


@end

James
Thanks for the very kind compliment.

I don't believe I've said what you quoted me as saying. Could leave me a message here including a full and exact quote of the part of my comments that you don't understand. Please copy and paste it in so that we're both sure you've got it verbatim. That way I could actually search for the text in the context of my code. Also if you want to email me your phone number (and a time range to call, including time zone or city) we could talk about it on the phone. my address is petegithubXXXpolash.net [ just replace the "XXX" with an "@", and no quotes ].

James

btw, What I did say is that, (for MY definition of of these flags), "a+b" will be considered to have multiple TERMS, but "(a+b)_c" will be considered to NOT have multiple TERMS. Generally speaking, in mathematics,, an expression like "a_b + c_d + e_f" is considered to have three TERMS (1= a_b, 2= c_d, and 3= e_f). while the expression a_b is considered to have two FACTORS (a and b), similarly c_d is considered to have two factors as is e_f.

Also in math, you could say that "a+a_b" would be considered to have two factors ("1+b" and "a"), but as explained in my comments (by MY working definition of these flags) I'm considering the expression "a+a_b", to have multiple terms but NOT multiple factors. To put it another way, I only consider an expression to have multiple factors if the expression is of a form that is already factored, so to speak, and only if the complete expression is not embedded in parentheses.

Let me know if I can be of any more help, (a phone conversation would be a lot easier).

James

Here's a link http://www.math-for-all-grades.com/AlgebraicExpressions.html