アルゴリズム-式評価

今日、Dijkstraのダブルスタック算術式の評価アルゴリズムをネット上で見ました.以前は算術スタックと数値スタックでできたことを知っていましたが、今回はOCで配列を通じて予想された効果を実現しました.
(原理参考ネット上、原作者不詳)
プログラミング言語システムは一般的に算術式の処理を内蔵しており、算術式の処理メカニズムを簡単に模倣することができ、思想は変わらず、主に実現方式が少し異なる.算術式は、1つの数、または1つの左かっこ、1つの算術式、1つの演算子、別の算術式、および1つの右かっこからなる式です.問題を簡略化するために、ここではカッコを省略しない算術式を定義し、すべての演算子のオペランドを明確に説明します.形式は以下の通りです:(1+((2+3)*(4*5))
考え方:
式は括弧、演算子、オペランドで構成されています.これらのエンティティは、次の4つの状況に応じて左から右にスタックに送られます.
     1.操作数を操作数スタックに圧入する.
     2.演算子を演算子スタックに押し込む.
     3.左かっこを無視
     4.右かっこに遭遇した場合、演算子をポップアップし、必要な数の操作数をポップアップし、演算後の結果を操作数スタックに押し込む.
最後の右かっこを処理すると、オペランドスタックには1つの値しか残っていません.これが式の計算結果です.この方法は一見理解しにくいが、正確な値を計算できることを証明するのは簡単だ.
アルゴリズムがカッコで囲まれ、1つの演算子と2つのオペランドからなるサブ式に遭遇するたびに、演算子とオペランドの演算結果をオペランドスタックに押し込みます.このような結果は,入力でこの値をサブ式に置き換えたようなものであり,サブ式の代わりにこの値を用いた結果は元の式と同じである.この法則を繰り返し適用し,最終値を得ることができる.
例:
(1+((2+3)*(4*5)))
(1+(5*(4*5)))
(1+(5*20))
(1+100)
  101
OCコードは以下のように実装される.

-(NSInteger)operationExpression:(NSString *)expression{

    NSMutableArray  *operationArr=[[NSMutableArray alloc]initWithCapacity:1];
    NSMutableArray  *valArr=[[NSMutableArray alloc]initWithCapacity:1];
    for (NSInteger i=0; i<expression.length; i++) {
        NSString  *currentStr=[NSString stringWithFormat:@"%c",[expression characterAtIndex:i]];
        if([currentStr isEqualToString:@"("]);
        else if([currentStr isEqualToString:@"+"]){
            [operationArr addObject:currentStr];
        }else if([currentStr isEqualToString:@"-"]){
            [operationArr addObject:currentStr];
        }else if([currentStr isEqualToString:@"*"]){
            [operationArr addObject:currentStr];
        }else if([currentStr isEqualToString:@")"]){
            
            NSInteger  lastValue=[[valArr objectAtIndex:valArr.count-1] integerValue];
            NSInteger  secondValue=[[valArr objectAtIndex:valArr.count-2] integerValue];
            
            [valArr removeObjectAtIndex:valArr.count-1];
            [valArr removeObjectAtIndex:valArr.count-1];
            NSString   *lastOperation=[operationArr objectAtIndex:operationArr.count-1];
            [operationArr removeObjectAtIndex:operationArr.count-1];
            
            
            
            NSInteger newValue=0;
            if([lastOperation isEqualToString:@"+"]) newValue=secondValue+lastValue;
            else if([lastOperation isEqualToString:@"-"]) newValue=secondValue-lastValue;
            else if([lastOperation isEqualToString:@"*"]) newValue=secondValue*lastValue;
            else if([lastOperation isEqualToString:@"/"]) newValue=secondValue/lastValue;
            
            [valArr addObject:[NSNumber numberWithLong:newValue]];
            
        }else{
            [valArr addObject:currentStr];
        }
    }
    return [[valArr objectAtIndex:0] integerValue];
}

浮動小数点数を処理できない、処理できない、2桁を超える整数を処理できないなど、多くの欠点がありますが、考えがあれば最適化を続けてみてください.