美文网首页
iOS分数四则运算

iOS分数四则运算

作者: 我是C | 来源:发表于2018-05-03 17:01 被阅读57次

    核心：中缀表达式->后缀表达式
    适用范围：任意精度计算
    基础数据类型：NSDecimalNumber
    项目地址：GLArithmetic

    pod 'GLArithmetic'

    1.中缀表达式处理

    #import <Foundation/Foundation.h>

/*字符串包含*/
#if __IPHONE_OS_VERSION_MIN_REQUIRED >= 80000
#define kContainsString(source,string) ([source containsString:string])
#else
#define kContainsString(source,string) ([source rangeOfString:string].location != NSNotFound)
#endif

typedef NS_ENUM(NSUInteger, OperatorPriority) {
    OperatorPriorityHigher,
    OperatorPriorityLower,
    OperatorPriorityEqual,
    OperatorPriorityError
};
@interface OperatorExpressionHandle : NSObject
+ (NSArray*)postfixExpWithInfixExp:(NSString*)infixExp;
//判断是否是操作符
+ (BOOL)isOperator:(char)anOperator;
//判断是否是运算符
+ (BOOL)isCaculaOperator:(NSString*)operatorStr;
//判断是否是数字
+ (BOOL)isNumber:(NSString*)numberStr;
//比较操作符优先级
+ (OperatorPriority)compareOperator1:(NSString*)operator1 Operator2:(NSString*)operator2;
@end

    #import "OperatorExpressionHandle.h"

@implementation OperatorExpressionHandle

+ (NSArray*)postfixExpWithInfixExp:(NSString*)infixExp{
    if (!infixExp.length) {
        return @[];
    }
    return (NSArray*)[OperatorExpressionHandle getPostfixExpFromInfixExpTo:infixExp];
}

//通过中缀表达式获得后缀表达式
+ (NSMutableArray *)getPostfixExpFromInfixExpTo:(NSString*)infixExp
{
    //中缀表达式转数组
    BOOL preIsNumber = NO;
    char currentChar = ' ';
    NSString *currentStr = @"";
    
    NSMutableArray *infixExpArray = [NSMutableArray array];
    for(NSInteger i = 0; i < infixExp.length; i++) {
        currentChar = [infixExp characterAtIndex:i];
        if(('-'==currentChar && !preIsNumber) || ![self isOperator:currentChar]){
            //当前字符是数字字符（当前字符是负号，前一个字符不是数字，或者不是操作符）
            currentStr = [currentStr stringByAppendingFormat:@"%c", currentChar];
            preIsNumber = YES;
        }else {
            //当前字符是操作符
            //入栈之前的字符串
            if(![currentStr isEqualToString:@""]) {
                [infixExpArray addObject:currentStr];
            }
            //入栈操作符
            [infixExpArray addObject:[NSString stringWithFormat:@"%c", currentChar]];
            //清空
            currentStr = @"";
            if (')' ==currentChar) {
                preIsNumber = YES;
            }else {
                preIsNumber = NO;
            }
        }
    }
    
    if(currentStr.length != 0){
        //最后一个数字串入栈
        [infixExpArray addObject:currentStr];
    }
    
    //中缀表达式数组倒序
    infixExpArray = [NSMutableArray arrayWithArray:[[infixExpArray reverseObjectEnumerator] allObjects]];
    
    NSMutableArray *dealStack = [NSMutableArray array];
    NSMutableArray *posfixExp = [NSMutableArray array];
    while(infixExpArray.count != 0){
        currentStr = infixExpArray.lastObject;
        if([self isNumber:currentStr]) {
            //数字直接加入
            [posfixExp addObject:currentStr];
        }else if([currentStr isEqualToString:@"("]) {
            //左括号入栈
            [dealStack addObject:currentStr];
        }else if([currentStr isEqualToString:@")"]) {
            //右括号，不断弹出操作栈顶，并加入，直到出现（，最后删除（
            if(dealStack.count == 0){
                NSLog(@"%@", @"Expression is wrong...");
                return nil;
            }else{
                while(![dealStack.lastObject isEqualToString:@"("]){
                    [posfixExp addObject:dealStack.lastObject];
                    [dealStack removeLastObject];
                    if(dealStack.count == 0){
                        NSLog(@"%@", @"Expression is wrong...");
                        return nil;
                    }
                }
                if([dealStack.lastObject isEqualToString:@"("]){
                    [dealStack removeLastObject];
                }
            }
        }else if ( [self isCaculaOperator:currentStr] ){
            //是操作符，栈顶操作符不是（且优先级高于或等于当前，则不断弹出
            while (dealStack.lastObject != nil && ![dealStack.lastObject isEqualToString:@"("] &&
                   [self compareOperator1:dealStack.lastObject Operator2:currentStr] != OperatorPriorityLower) {
                [posfixExp addObject:dealStack.lastObject];
                [dealStack removeLastObject];
            }
            [dealStack addObject:currentStr];
        }
        [infixExpArray removeLastObject];
    }
    while(dealStack.count != 0){
        if([dealStack.lastObject isEqualToString:@"(" ]){
            NSLog(@"%@", @"Expression is wrong...");
            return nil;
        }
        [posfixExp addObject:dealStack.lastObject];
        [dealStack removeLastObject];
    }
    
    return posfixExp;
}

//判断是否是操作符
+ (BOOL)isOperator:(char)anOperator
{
    return ('+' == anOperator
            ||  '-' == anOperator
            ||  '*' == anOperator
            ||  '/' == anOperator
            ||  '^' == anOperator
            ||  '(' == anOperator
            ||  ')' == anOperator);
}

//判断是否是数字
+ (BOOL)isNumber:(NSString*)numberStr;
{
    return !([numberStr isEqualToString:@"+"]
             || [numberStr isEqualToString:@"^"]
             || [numberStr isEqualToString:@"-"]
             || [numberStr isEqualToString:@"*"]
             || [numberStr isEqualToString:@"/"]
             || [numberStr isEqualToString:@")"]
             || [numberStr isEqualToString:@"("]
             || [numberStr isEqualToString:@"="]);
}
//判断是否是运算符
+ (BOOL)isCaculaOperator:(NSString*)operatorStr
{
    return ([operatorStr isEqualToString:@"+"]
            ||  [operatorStr isEqualToString:@"^"]
            ||  [operatorStr isEqualToString:@"-"]
            ||  [operatorStr isEqualToString:@"*"]
            ||  [operatorStr isEqualToString:@"/"]);
}

//比较操作符优先级
+ (OperatorPriority)compareOperator1:(NSString*)operator1 Operator2:(NSString*)operator2
{
    if([operator1 isEqualToString:@"^"]){
        if( [operator2 isEqualToString:@"^" ]){
            return OperatorPriorityEqual;
        }else if([operator2 isEqualToString:@"*"]
                 || [operator2 isEqualToString:@"/"]
                 || [operator2 isEqualToString:@"+"]
                 || [operator2 isEqualToString:@"-"]){
            return OperatorPriorityHigher;
        }else{
            return OperatorPriorityError;
        }
    }else if([operator1 isEqualToString:@"*"]
             || [operator1 isEqualToString:@"/"]){
        if([operator2 isEqualToString:@"^"]){
            return OperatorPriorityLower;
        }else if([operator2 isEqualToString:@"*"]
                 || [operator2 isEqualToString:@"/" ]){
            return OperatorPriorityEqual;
        }else if([operator2 isEqualToString:@"+"]
                 || [operator2 isEqualToString:@"-" ]){
            return OperatorPriorityHigher;
        }else{
            return OperatorPriorityError;
        }
    }else if([operator1 isEqualToString:@"+" ]
             || [operator1 isEqualToString:@"-" ]) {
        if([operator2 isEqualToString:@"^" ]
           || [operator2 isEqualToString:@"*"]
           || [operator2 isEqualToString:@"/" ]) {
            return OperatorPriorityLower;
        } else if([operator2 isEqualToString:@"+"]
                  || [operator2 isEqualToString:@"-" ]) {
            return OperatorPriorityEqual;
        } else {
            return OperatorPriorityError;
        }
    }else{
        return OperatorPriorityError;
    }
}

@end

    2.核心处理逻辑

    #import <Foundation/Foundation.h>

@interface OperatorCaculateFraction : NSObject
//计算分数表达式
+ (NSString*)calculateFraction:(NSString *)infixexp errorString:(NSString **)errorString;
//分数转小数
+ (NSString*)fractionTranslatePoint:(NSString *)fraction;
@end

    #import "OperatorCaculateFraction.h"
#import "OperatorExpressionHandle.h"

#define kDecimalNumberWithString(v) [NSDecimalNumber decimalNumberWithString:v]
#define kDecimalNumberPowerOf10(v,power) [v decimalNumberByMultiplyingByPowerOf10:power]
#define kDecimalNumberAdd(v1,v2) [v1 decimalNumberByAdding:v2]
#define kDecimalNumberSub(v1,v2) [v1 decimalNumberBySubtracting:v2]
#define kDecimalNumberMul(v1,v2) [v1 decimalNumberByMultiplyingBy:v2]
#define kDecimalNumberDiv(v1,v2) [v1 decimalNumberByDividingBy:v2]

@implementation OperatorCaculateFraction
+ (NSString*)calculateFraction:(NSString *)infixexp errorString:(NSString **)errorString{
    if (!infixexp.length) {
        *errorString = @"字符串为空";
        return nil;
    }
    NSString *infixexp1 = [infixexp stringByReplacingOccurrencesOfString:@" " withString:@""];
    NSString *infixexp2 = [infixexp1 stringByReplacingOccurrencesOfString:@"×" withString:@"*"];
    NSString *infixexp3 = [infixexp2 stringByReplacingOccurrencesOfString:@"÷" withString:@"/"];
    
    NSMutableArray *postfixExp = (NSMutableArray *)[OperatorExpressionHandle postfixExpWithInfixExp:infixexp3];
    
    NSString *result = [self calculateWithPosfixExpF:postfixExp errorString:errorString];
    result = [self ireducibleFraction:result];
    
    return result;
}

//用后缀表达式计算结果 guolei
+ (NSString*)calculateWithPosfixExpF:(NSMutableArray *)posfixExp errorString:(NSString **)errorString
{
    if (errorString == NULL) {
        NSString __autoreleasing *err = nil;
        errorString = &err;
    }
    posfixExp = [NSMutableArray arrayWithArray:[[posfixExp reverseObjectEnumerator] allObjects]];
    NSMutableArray *dealStack = [NSMutableArray array];
    
    NSString *numberStr1 = @"";
    NSString *numberStr2 = @"";
    while(posfixExp.count != 0){
        NSString *currentStr = posfixExp.lastObject;
        if([OperatorExpressionHandle isNumber:currentStr]){
            //操作数入栈
            [dealStack addObject:currentStr];
        }else if ([OperatorExpressionHandle isCaculaOperator:currentStr]) {
            
            if ([currentStr isEqualToString:@"/"]) {
                
                numberStr1 = dealStack.lastObject;
                [dealStack removeLastObject];
                numberStr2 = dealStack.lastObject;
                [dealStack removeLastObject];
                
                if (kContainsString(numberStr1,currentStr) || kContainsString(numberStr2,currentStr)) {
                    NSString *result = [self caculteFraction:numberStr2 d2:numberStr1 operator:currentStr];
                    [dealStack addObject:result];
                    
                }else{
                    
                    NSMutableString *mutableString = [NSMutableString string];
                    [mutableString appendString:numberStr2];
                    [mutableString appendString:currentStr];
                    [mutableString appendString:numberStr1];
                    if ([numberStr1 isEqualToString:@"0"] || [numberStr1 isEqualToString:@"-0"]) {
                        *errorString = @"分母或除数不能为0";
                        return nil;
                    }
                    [dealStack addObject:mutableString];
                }
                
            }else{
                
                numberStr1 = dealStack.lastObject;
                [dealStack removeLastObject];
                numberStr2 = dealStack.lastObject;
                [dealStack removeLastObject];
                
                NSString *result = [self caculteFraction:numberStr2 d2:numberStr1 operator:currentStr];
                [dealStack addObject:result];
            }
        }
        [posfixExp removeLastObject];
    }
    
    if (dealStack.count ==1) {
        return [NSString stringWithFormat:@"%@",dealStack.lastObject];
    }else {
        return nil;
    }
}

//未约分的分数
+ (NSString*)normalFraction:(NSString*)aFraction{
    if (!aFraction.length || [aFraction isKindOfClass:[NSNull class]]) {
        return @"非法";
    }
    
    NSArray<NSString*> *d1Arr = [self parseFraction:aFraction];
    NSString *f1 = d1Arr[0];
    NSString *f2 = d1Arr[1];
    
    if ([f2 isEqualToString:@"0"] || [f2 isEqualToString:@"-0"]) {
        return @"非法";
    }
    if ([f1 isEqualToString:@"0"] || [f1 isEqualToString:@"-0"]) {
        return @"0";
    }
    
    NSString *first = @"";
    
    NSInteger co = 0;
    if (kContainsString(f1, @"-")) {
        f1 = [f1 substringFromIndex:1];
        co++;
    }
    if (kContainsString(f2, @"-")) {
        f2 = [f2 substringFromIndex:1];
        co++;
    }
    if (co%2 != 0) {
        first = @"-";
    }
    
    NSInteger k = 0;
    NSInteger k1 = 0;
    
    
    if (kContainsString(f1, @".")) {
        NSRange range = [f1 rangeOfString:@"."];
        k = f1.length-range.location-1;
    }
    
    if (kContainsString(f2, @".")) {
        NSRange range = [f2 rangeOfString:@"."];
        k1 = f2.length-range.location-1;
    }
    
    short max = MAX(k, k1);
    
    NSDecimalNumber *f11;
    NSDecimalNumber *f22;
    
    if (max) {
        f11 = kDecimalNumberPowerOf10(kDecimalNumberWithString(f1),max);
        f22 = kDecimalNumberPowerOf10(kDecimalNumberWithString(f2),max);
    }else{
        f11 = kDecimalNumberWithString(f1);
        f22 = kDecimalNumberWithString(f2);
    }
    return [NSString stringWithFormat:@"%@%@/%@",first,f11,f22];
}
//ireducible
+ (NSString *)ireducibleFraction:(NSString*)aFraction{
    
    NSString *normalfraction = [self normalFraction:aFraction];
    
    if ([normalfraction isEqualToString:@"非法"]) {
        return @"非法";
    }
    
    NSString *first = @"";
    if (kContainsString(normalfraction, @"-")) {
        normalfraction = [normalfraction substringFromIndex:1];
        first = @"-";
    }
    
    NSArray<NSString*> *d1Arr = [self parseFraction:normalfraction];
    NSString *a = d1Arr[0];//分子
    NSString *b = d1Arr[1];//分母
    
    //最大公约数
    NSDecimalNumber *gcd = [self greatestCommonDivisorA:kDecimalNumberWithString(a) b:kDecimalNumberWithString(b)];
    
    NSDecimalNumber *son = kDecimalNumberDiv(kDecimalNumberWithString(a),gcd);
    NSDecimalNumber *mom = kDecimalNumberDiv(kDecimalNumberWithString(b),gcd);
    
    NSString *result;
    if ([mom isEqualToNumber:@(1)]) {
        result = [NSString stringWithFormat:@"%@%@",first,son];
    }else{
        result = [NSString stringWithFormat:@"%@%@/%@",first,son,mom];
    }
    
    return result;
}

+ (BOOL)isZeroWithSub:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    if ([kDecimalNumberSub(a, b) compare:kDecimalNumberWithString(@"0")] != NSOrderedSame) {
        return NO;
    }
    return YES;
}

+ (NSDecimalNumber *)maxA:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    if ([a compare:b] == NSOrderedDescending) { //a>b
        return a;
    }else{
        return b;
    }
}

+ (NSDecimalNumber *)minA:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    if ([a compare:b] == NSOrderedDescending) { //a>b
        return b;
    }else{
        return a;
    }
}

//是否能被整除
+ (BOOL)isDivisible:(NSDecimalNumber*)d1 byD2:(NSDecimalNumber*)d2{
    NSDecimalNumber *result = kDecimalNumberDiv(d1, d2);
    NSString *resultStr = [NSString stringWithFormat:@"%@",result];
    if (kContainsString(resultStr, @".")) {
        return NO;
    }
    return YES;
}

+ (NSString*)caculteFraction:(NSString*)d1 d2:(NSString*)d2 operator:(NSString*)operator{
    
    NSString *d11 = d1;
    NSString *d22 = d2;
    
    NSArray<NSString*> *d1Arr = [self parseFraction:d11];
    NSArray<NSString*> *d2Arr = [self parseFraction:d22];
    
    //分子
    NSDecimalNumber *numerator1 = kDecimalNumberWithString(d1Arr[0]);
    NSDecimalNumber *numerator2 = kDecimalNumberWithString(d2Arr[0]);
    
    //分母
    NSDecimalNumber *denominator1 = kDecimalNumberWithString(d1Arr[1]);
    NSDecimalNumber *denominator2 = kDecimalNumberWithString(d2Arr[1]);
    
    NSDecimalNumber *numerator3;
    NSDecimalNumber *denominator3;
    if([operator isEqualToString:@"+"]) {
        numerator3 = kDecimalNumberAdd(kDecimalNumberMul(numerator1, denominator2),kDecimalNumberMul(numerator2, denominator1));
        denominator3 = kDecimalNumberMul(denominator1, denominator2);
    }else if([operator isEqualToString:@"-"]) {
        numerator3 = kDecimalNumberSub(kDecimalNumberMul(numerator1, denominator2),kDecimalNumberMul(numerator2, denominator1));
        denominator3 = kDecimalNumberMul(denominator1, denominator2);
    }else if([operator isEqualToString:@"*"]) {
        numerator3 = kDecimalNumberMul(numerator1, numerator2);
        denominator3 = kDecimalNumberMul(denominator1, denominator2);
    }else if([operator isEqualToString:@"/"]) {
        numerator3 = kDecimalNumberMul(numerator1, denominator2);
        denominator3 = kDecimalNumberMul(denominator1, numerator2);
    }else{
        return nil;
    }
    NSString *retF = [NSString stringWithFormat:@"%@/%@",numerator3,denominator3];
    return retF;
}

+ (NSArray*)parseFraction:(NSString*)num{
    NSString *numerator1 = @"";//分子
    NSString *denominator1 = @"";//分母
    
    NSArray *arr1 = [num componentsSeparatedByString:@"/"];
    
    if (arr1.count == 2) {
        numerator1 = arr1[0];
        denominator1 = arr1[1];
    }else{
        numerator1 = arr1[0];
        denominator1 = @"1";
    }
    
    NSMutableArray *fractionArr = [NSMutableArray array];
    [fractionArr addObject:numerator1];
    [fractionArr addObject:denominator1];
    
    return (NSArray*)fractionArr;
}

+ (NSString*)fractionTranslatePoint:(NSString *)fraction{
    NSString *result;
    if (kContainsString(fraction, @"/")) {
        NSArray *ar = [fraction componentsSeparatedByString:@"/"];
        NSDecimalNumber *a = kDecimalNumberWithString(ar[0]);
        NSDecimalNumber *b = kDecimalNumberWithString(ar[1]);
        result = [self rounding:kDecimalNumberDiv(a, b) afterPoint:6];
    }else{
        result = fraction;
    }
    return result;
}

//保留几位小数
+ (NSString *)rounding:(NSDecimalNumber*)num afterPoint:(NSInteger)position{
    NSDecimalNumberHandler* roundingBehavior = [NSDecimalNumberHandler decimalNumberHandlerWithRoundingMode:NSRoundPlain scale:position raiseOnExactness:NO raiseOnOverflow:NO raiseOnUnderflow:NO raiseOnDivideByZero:NO];
    NSDecimalNumber *ouncesDecimal;
    NSDecimalNumber *roundedOunces;
    
    ouncesDecimal = num;
    roundedOunces = [ouncesDecimal decimalNumberByRoundingAccordingToBehavior:roundingBehavior];
    return [NSString stringWithFormat:@"%@",roundedOunces];
}

//最大公约数
+ (NSDecimalNumber*)greatestCommonDivisorA:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    NSDecimalNumber *t;
    while (![b isEqualToNumber:[NSDecimalNumber decimalNumberWithString:@"0"]]) {
        t = [self unsignedRemainderA:a b:b];
        a = b;
        b = t;
    }
    return a;
}

+ (NSDecimalNumber*)unsignedRemainderA:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    //商
    NSDecimalNumber *quotient = [self unsignedDivQuotient:a b:b];
    //余数
    NSDecimalNumber *remainder = [a decimalNumberBySubtracting:[b decimalNumberByMultiplyingBy:quotient]];
    return remainder;
}

//商
+ (NSDecimalNumber*)unsignedDivQuotient:(NSDecimalNumber*)a b:(NSDecimalNumber*)b{
    if (!a || !b) {
        return nil;
    }
    
    NSDecimalNumberHandler *roundUp = [NSDecimalNumberHandler
                                       
                                       decimalNumberHandlerWithRoundingMode:NSRoundDown
                                       
                                       scale:0
                                       
                                       raiseOnExactness:NO
                                       
                                       raiseOnOverflow:NO
                                       
                                       raiseOnUnderflow:NO
                                       
                                       raiseOnDivideByZero:YES];
    
    NSDecimalNumber *r = [a decimalNumberByDividingBy:b withBehavior:roundUp];
    
    return r;
}
@end

    表达式用例：

    "((-796487)/275501-(-145933)-378558)*(675142*95360+(-340735)*(-434962))/717924+(-319999)-(608588-164965)/877834/(-798337)*(-863880)-(-42189)",

    以上代码经过测试（python 验证结果），10万条上述随机表达式计算花费51秒，平均每条约0.00055秒

    相关文章

      网友评论

          本文标题：iOS分数四则运算

          本文链接：https://www.haomeiwen.com/subject/rhllrftx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|iOS分数四则运算|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！