算法-表达式求值

今天在网上看到Dijkstra的双栈算术表达式求值算法,以前很早的时候知道通过算术栈和数值栈搞定的,这次用OC通过数组实现了预期的效果.

(原理参考网上,原作者不详)

编程语言系统一般都内置了对算术表达式的处理,我们可以简易的模仿一下算术表达式处理机制,思想不变,主要是实现方式略有不同。算术表达式可能是一个数、或者是由一个左括号、一个算术表达式、一个运算符、另一个算术表达式和一个右括号组成的表达式。为了简化问题,这里定义的是未省略括号的算术表达式,它明确地说明了所有运算符的操作数,形式如下:(1+((2+3)*(4*5)))

思路:

     表达式由括号、运算符和操作数构成,我们根据以下4中情况从左至右逐个将这些实体送入栈处理:

     1.将操作数压入操作数栈;

     2.将运算符压入运算符栈;

     3.忽略左括号;

     4.在遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算后的结果压入操作数栈;

    在处理完最后一个右括号时,操作数栈上只会剩下一个值,它就是表达式的计算结果。这种方法咋一看难理解,但要证明它能计算得到正确的值很简单:

    每当算法遇到一个括号包围,并由一个运算符和两个操作数组成的子式时,他都将运算符和操作数运算结果压入操作数栈。这样的结果就像是在输入中用这个值代替了该子表达式,因此用这个值代替子表达式得到的结果和原表达式相同。我们可以反复应用这个规律并得到一个最终值。

例如:

(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];
}


上一篇:VS2017调试时提示“运行时无法计算表达式的值”


下一篇:1,由于代码已经过优化或者本机框架位于调用堆栈之上,无法计算表达式的值。