# RPN-Stack-Based Recursive Calculator Needs Tuneup

This function takes an array of strings and numbers and recursively processes it as a kind of "calculating program". The structure is based on Reverse Polish Notation, so the top object in the stack (last in the array) determines what to do with the next one (or two) items in the program. For example, if the array was [1, 2, "+"], the solution would be 3.

• In the case of errors, it should return an NSString describing the error that happened.

• If more than one error occurs in processing, it is not clear which error should receive priority, so I've chosen to prioritize the first error found and ignore any further errors.

I think that this code could be made much more simple, but I'm not sure how best to do that in Objective C. What suggestions do you have to improve this code?

 + (id)popOperandOffProgramStack:(NSMutableArray *)stack
{
id result;
double dResult;

id topOfStack = [stack lastObject];
if (topOfStack) [stack removeLastObject];

if ([topOfStack isKindOfClass:[NSNumber class]])
{
result = topOfStack;
}
else if ([topOfStack isKindOfClass:[NSString class]])
{
id rightSide = [self popOperandOffProgramStack:stack];
if (![rightSide isKindOfClass:[NSNumber class]]) {
return rightSide;
}
double r = [(NSNumber *)rightSide doubleValue];

NSString *operation = topOfStack;
if ([[self class] isBinaryOperation:operation]) {
id leftSide = [self popOperandOffProgramStack:stack];
if (![leftSide isKindOfClass:[NSNumber class]]) {
return leftSide;
}
double l = [(NSNumber *)leftSide doubleValue];
if([operation isEqualToString:@"+"]) {
dResult =  l + r;
} else if([operation isEqualToString:@"-"]) {
dResult = l - r;
} else if([operation isEqualToString:@"*"]) {
dResult = l * r;
} else if([operation isEqualToString:@"/"]) {
if(r == 0.0) {
return @"Error: Tried to divide by zero";
} else {
dResult = l / r;
}
}
} else if ([operation isEqualToString:@"+/-"]) {
dResult = -r;
} else if([operation isEqualToString:@"sin"]) {
dResult = sin(r);
} else if([operation isEqualToString:@"cos"]) {
dResult = cos(r);
} else if([operation isEqualToString:@"sqrt"]) {
if(r < 0) {
return @"Error: tried to sqrt a negative number";
}
dResult = sqrt(r);
} else if([operation isEqualToString:@"π"]) {
dResult = 3.141592654;
} else {
/* unknown operations and unset variables will return 0 */
dResult = 0.0;
}
result = [NSNumber numberWithDouble:dResult];
}
return result;
}


Instead of returning an error-String, I would pass in a nil'ed-NSError object by reference, and write an error to it, in case it occurred. the returned object would be nil

+ (NSNumber *)popOperandOffProgramStack:(NSMutableArray *)stack error:(NSError **)error
{
//…
error = [[NSError alloc] int…] ;
}


Usage:

NSError *error = nil;
if ([Calculator popOperandOffProgramStack:parameters error:&error])
{
//returned object not nil -> success
} else {
//nil-object -> let's check the error
}


this avoids type checking.

• There are two minor problems in the first method: First you need to assign to *error not error (remember you passed a pointer to an error ref), second, you should wrap the assignment in if (error != nil) { ... } so that people who are not interested in the error text can pass nil in. – JeremyP Apr 17 '12 at 9:28

At the risk of exposing my C++ (lots of little objects) roots...

I think this code shows signs of having complexity cornered into it for the sake of simplicity in the code that feeds it. In particular, there was likely some kind of parser that tokenized the input into the stack of NSNumber or NSString. Producing a stack and two operand types puts this code a couple steps up from a purely stringly typed interface. But it could go further. Each element of the stack could have been created as an instance of an Operand base class, or actually an Operand sub-class like NumberOperand, SumOperand, ProductOperand, SinOperand, etc. where each class specializes a simple popResult method that gets called by popOperandOffProgramStack to deal with popping its operand(s if any), checking its error cases, and calculating its result. It's probably not that much extra work for the parser, assuming that each operand had to be validated against all the possible forms, anyway. You'd just have to use what you discovered during the successful validation to construct an operand of the right type -- or, for each function operand, possibly just reference a singleton object -- they're stateless, so different instances aren't very useful. With Operand objects, you don't lose the details, so popOperandOffProgramStack doesn't have to reconstruct them with all this matching.

You are confusing the RPN expression (the stream of numbers and commands) with the stack that the RPN calculator operates on.

The way an RPN calculator normally works is, it starts with an empty stack. When it encounters a number, it pushes it onto the stack. When it encounters an operation, the operation pops the necessary number of operands from the stack and pushes the result onto the stack. The stack only contains numbers — never operators.

Therefore, your RPN calculator should either create a stack, or take an (empty) stack as a parameter. I've chosen the latter option for greater flexibility.

There are some other improvements you could make. One is to write all of the operators as blocks in a dictionary, and do dynamic dispatching by looking up the operator by name. That is more elegant than a long chain of else-ifs.

Also, contrary to common belief, division by zero is not an error in IEEE 754 — it results in infinity (or negative infinity, if dividing by negative zero). Therefore, you would get better functionality by removing the check for division by zero.

Finally, creating a result of 0.0 when faced with invalid input is reckless. The user will see a seemingly successful computation that is not what was intended. When encountering invalid input, the function must indicate an error. A good way to do that is to throw an exception.

### Suggested implementation

RPNCalc.h

#import <Foundation/Foundation.h>

@interface RPNCalc : NSObject
+ (void) rpnCalc:(NSArray *)program stack:(NSMutableArray *)stack;
@end


RPNCalc.m

#import "RPNCalc.h"

#include <math.h>

static NSDictionary *constants;
static NSDictionary *unaryOperations;
static NSDictionary *binaryOperations;
static Boolean initialized = FALSE;

@implementation RPNCalc
+ (void) initialize
{
constants = [NSDictionary dictionaryWithObjectsAndKeys:
[NSNumber numberWithDouble:acos(-1)], @"π",
//[NSNumber numberWithDouble:exp(1)],   @"e",
nil
];
unaryOperations = [NSDictionary dictionaryWithObjectsAndKeys:
^double (double a) { return -a; },      @"+/-",
^double (double a) { return sin(a); },  @"sin",
^double (double a) { return cos(a); },  @"cos",
^double (double a) { return sqrt(a); }, @"sqrt",
nil
];
binaryOperations = [NSDictionary dictionaryWithObjectsAndKeys:
^double (double a, double b) { return a + b; }, @"+",
^double (double a, double b) { return a - b; }, @"-",
^double (double a, double b) { return a * b; }, @"*",
^double (double a, double b) { return a / b; }, @"/",
nil
];
initialized = TRUE;
}

+ (void) rpnCalc:(NSArray *)program stack:(NSMutableArray *)stack
{
if (!initialized) {
[RPNCalc initialize];
}

NSEnumerator *prog = [program objectEnumerator];
id op;
while (op = [prog nextObject]) {
if ([op isKindOfClass:[NSNumber class]]) {
} else if ([op isKindOfClass:[NSString class]]) {
id expr;
if ((expr = [constants objectForKey:op])) {

} else if ((expr = [unaryOperations objectForKey:op])) {
double (^unaryOperation)(double) = expr;
double top1 = [[stack lastObject] doubleValue];
[stack removeLastObject];
double result = unaryOperation(top1);

} else if ((expr = [binaryOperations objectForKey:op])) {
double (^binaryOperation)(double, double) = expr;
double top1 = [[stack lastObject] doubleValue];
[stack removeLastObject];
double top2 = [[stack lastObject] doubleValue];
[stack removeLastObject];
double result = binaryOperation(top2, top1);

} else {
NSException *e = [NSException exceptionWithName:@"RPNException"
reason:@"Unrecognized string"
userInfo:nil];
@throw e;
}
} else {
NSException *e = [NSException exceptionWithName:@"RPNException"
reason:@"Encountered a value that is neither a number nor a string"
userInfo:nil];
@throw e;
}
}
}
@end


main.m

int main(int argc, const char * argv[])
{

@autoreleasepool {
@try {
NSMutableArray *prog = [NSMutableArray arrayWithCapacity:(argc - 1)];
for (int i = 1; i < argc; i++) {
char *end;
double d = strtod(argv[i], &end);
if (*end == '\0') {
} else {
}

}
NSMutableArray *stack = [[NSMutableArray alloc] init];
[RPNCalc rpnCalc:prog stack:stack];

NSNumber *result;
NSEnumerator *results = [stack reverseObjectEnumerator];
while ((result = (NSNumber *)[results nextObject])) {
printf("%f\n", [result doubleValue]);
}
} @catch (NSException *e) {
NSLog(@"%@\n", e);
}
}
return 0;
}


### Example usage

$./cr8693 π 2 / sin 1 2 / + 1.500000$ ./cr8693 1 -0 /
-inf