I have a program that I want to be able to take an expression like "4+56^4" and convert it into a number. I have a RPN system almost working (Reverse Polish Notation, the same that HP uses) , but I wondered if there was an easier way. If not, I can do it by myself, but if there is, it would be a lot easier.
Got a tip for us?
Let us know
Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
macOS How to convert an expression into a number
- Thread starter Duke Leto
- Start date
- Sort by reaction score
Eh? I don't understand the question. You want to convert it into it's constituant parts or what? Or do you just want the answer and the only way you can get the expression into the program is as a string which you want to convert into useable numbers?
Not sure what language you're using, but if you accept in RPN it shouldn't be too hard. Essentially you will have a "perform operation" function that accepts two numbers (in the easiest case both are integers) and a single operator. I would personally define a number of things in a c-style language to use as operators, such as:
#define OP_PLUS 1
#define OP_MINUS 2
etc.
When you are reading the input, you can do something like:
Code:
if(strncmp(op_buf,"+") == 0) {
op=OP_PLUS;
}Then you can pass op into your function, and use switch to determine what operation to perform on the two numbers. Something like:
Code:
switch(op) {
case OP_PLUS:
return operatorA + operatorB;
break;
case OP_MINUS:
return operatorA - operatorB;
break;
}If the language you're using allows for a switch-like syntax on character strings, you don't have to deal with this intermediate step.
The main part of the program will need to manage parsing the expression and keeping stacks or using recursive evaluation. This page provides a lot of information on implementing this:
http://www.math.bas.bg/~bantchev/place/rpn/rpn.hows.html
-Lee
Your input will likely be NSStrings instead of char *, then. The logic is pretty much the same, though.
Code:
NSMutableArray *inputTokens = nil;
inputTokens = [inputBuffer componentsSeparatedByCharactersInSet:[NSCharacterSet whitespaceCharacterSet]];
while([inputTokens count] > 1) { When we are down to one item it should be our result
if([myRPNClass isNumeric:[inputTokens lastObject]]){ //isNumeric would have to be defined to take an NSString * and return true/false
NSLog(@"Error. Invalid RPN equation entered.");
//exit, return, whatever
} else {
[MyRPNClass performSingleOperation:inputTokens]; //This method does the real work
}
}
if([myRPNClass isNumeric:[inputTokens lastObject]]) {
NSLog(@"The result is: %d",[[inputTokens lastObject] intValue]);
} else {
NSLog(@"Parse error.");
}
...
+ (void) performSingleOperation:(NSArray *)inputTokens {
NSString *operator = [inputTokens lastObject];
[inputTokens removeLastObject]; //pop
int op;
if([operator isEqualToString:@"+"]) {
op=OP_PLUS;
} elseif { //Fill in all other operator cases
...
}
if(![myRPNClass isNumeric:[inputTokens lastObject]) { //non-numeric
[myRPNClass performSingleOperation:inputTokens];
}
int operandA = [[inputTokens lastObject] intValue];
[inputTokens removeLastObject]; //pop
if(![myRPNClass isNumeric:[inputTokens lastObject]) { //non-numeric
[myRPNClass performSingleOperation:inputTokens];
}
int operandB = [[inputTokens lastObject] intValue];
[inputTokens removeLastObject]; //pop
switch(op) {
case OP_PLUS:
[inputTokens addObject:[NSString initWithFormat:@"%d",operandA + operandB]];
break;
... //One case for each operator
}
return;
}
+ (BOOL) isNumeric:(NSString *)toCheck { //There may be a better way to do this, but it was the best i could come up with
if([toCheck intValue] != 0) {
return true;
} else if([toCheck isEqualToString:@"0"]) {
return true;
} else {
return false;
}
}I didn't compile this, but I'm pretty confident in the various NSString and NSMutableArray methods used. Since I didn't try it myself, the logic may be a bit off. This essentially uses an NSMutableArray as a stack. It keeps all of the operators and operands on the same stack. I didn't use any NSNumber *s as intermediate storage for actual integer values. It seemed just as well to keep them in strings. The "main" routine doesn't do much, performSingleOperation does the work, calling itself recursively if needed. When the while() loop in the main function completes the single member on the stack should be the result. You can use intValue to get the actual int.
This also assumes only binary operations. Something like taking the negative of a number, or the square root, would need to be written as x -1 * and x .5 ^ instead of the implicit use normally seen with these operations. I guess this is always the case in RPN, but I can't say that I am intimately familiar with it.
-Lee
Edit: I just realized that in the "main" method you should only make a call to performSingleOperation once, if the RPN is formatted properly. The while should really just be collapsed to an if(count > 1), and inside that an if(isNumeric). I don't feel like changing it, but that just occurred to me.
THis is so much more beautiful in python 
:
:
Code:
def is_number(token):
try:
float(token)
except Exception, e:
return False
return True
def result_from_rpn_expression(rpn_expression):
tokens = rpn_expression.split(" ")
def plus(a, b):
return a + b
def minus(a, b):
return a - b
def mult(a, b):
return a * b
def div(a, b):
return a / b
operations = {
"+" : plus,
"-" : minus,
"*" : mult,
"/" : div
}
token_stack = []
for token in tokens:
if is_number(token) :
token_stack.append(token)
else :
token_stack.append(operations[token](float(token_stack.pop()), float(token_stack.pop())))
return token_stack[0]THis is so much more beautiful in python
Code:
token_stack.append(operations[token](float(token_stack.pop()), float(token_stack.pop())))Overall that was certainly more elegant, but that line would make some perl devs blush. =)
-Lee
Making a more functional calculator for your math classes than what the iPhone has? I think a killer app for the iPhone might be some sort of graphing calculator, or perhaps derivative/integral solvers a la TI-89. Yes, RPN is probably the way to go - it's implementation (stacks, input processing, etc) is advanced enough to not be a cakewalk but easy enough for people to wrap their heads around that it is a textbook (pardon the pun) coding exercise in CS courses. If you really wanted to go all out, you could use lex and yacc to implement your own parser so it can accept more "natural" inputs. Chances are this problem has been solved 100 times over and can probably just get someone's implementation. I'm glad I was exposed to lex and yacc in school as they have very limited domain scope but man are they powerful.
lex/flex and yacc/bison are great tools, but may be slightly overkill for this problem. The grammar for this type of expression is not too complex. If you use infix it gets a bit worse in terms of parenthetical expressions and dealing with order of operations, but with RPN it's pretty simple.
I might save lex/flex and yacc/bison for a slightly more complex task (for the graphing calculator, especially if it were multivariate, it would be a bit more suitable).
-Lee
I might save lex/flex and yacc/bison for a slightly more complex task (for the graphing calculator, especially if it were multivariate, it would be a bit more suitable).
-Lee