有趣的算法(五) ——Dijkstra双栈四则运算

有趣的算法(五)——Dijkstra双栈四则运算

(原创内容,转载请注明来源,谢谢)

一、概念

近期看到算法书上,提到dijkstra双栈的方法,实现输入一个四则运算的字符串,输出结果。

其实质上,就是利用两个栈,一个存储数字,一个存储运算符,再通过括号进行判定是否需要取出内容。

二、分析

为方便说明,现假设运算的字符串为(3*(8-2))。其中,为简化算法,假定每两个数的运算都要加上括号(对于不加括号的算法,后面会讨论到)。

运算的过程如下:

1)初始化两个栈,分别用于存放运算符和数字。接收这一整串的字符串,并从第一个字符开始,遍历字符串。

2)遇到左括号,忽略。

3)遇到数字,存入数字栈;遇到运算符,存入运算符栈。

4)遇到右括号,开始计算,取出数字栈最顶上两个元素,以及运算符栈最顶上一个元素,用数字栈倒数第二个元素通过运算符和第一个元素进行运算。

5)将计算的结果再压入数字栈。

6)重复2-5,直到遇到最后一个括号,则计算结束,返回最终数字栈中的唯一元素。

例如上图,一开始会将3、8、2压入数字栈,*、-压入运算符栈。当遇到第一个右括号,则将数字栈的8、2和运算符栈的-弹出,并按照8在前,2在后的顺序,运用运算符-,进行计算,得到结果6,再存入数字栈。

则此时,数字栈的顺序是3、6,运算符栈是*。再遇到一个右括号,则会计算3*6,将结果18压入数字栈。最终运算符栈没有内容,数字栈是唯一的数字。

三、编程

1、java实现

1)首先,利用hashset,可以区分数字set和运算符set,针对每一个字符,判断是否属于这两个set,或是否是有括号,并进行相应的操作,压入栈或者是取出并计算。

如下:

    private static finalHashSet<Character> numStringSet = new HashSet<Character>(){
        {add('0'); add('1'); add('2');add('3'); add('4'); add('5'); add('6'); add('7'); add('8'); add('9');}
    };
    private static finalHashSet<Character> operatorSet = new HashSet<Character>(){
        {add('+'); add('-'); add('*');add('/');}
    };

2)接着,利用两个stack泛型,一个是Double类型(主要是针对除法),一个是Character类型,用于保存计算期间的内容。

如下:

         private Stack<Double> doubleStack= new Stack<>();
private Stack<Character> charStack = new Stack<>();

3)接着,针对每个字符,进行判断,查看需要何种操作。

    private BooleanneedCalculate(Character ch){
        Boolean res = false;
       if(operatorSet.contains(ch)){
           this.pushChar(ch);//运算符
        }elseif(numStringSet.contains(ch)){
           this.pushDouble(Double.valueOf(String.valueOf(ch)));//数字
        }elseif(ch.equals(')')){
            res = true;//要计算的情况
        }
        return res;
    }

4)最后进行计算,并返回结果。

整体代码如下:

注:代码已传到github,https://github.com/linhxx/taskmanagement,就是之前的springboot项目,我计划将java相关的内容整合到里面,作为算法测试模块。

package com.lin.service.algorithm;
import java.util.HashSet;
import java.util.Stack;
public class CalculateService{
    privateStack<Double> doubleStack = new Stack<>();
    privateStack<Character> charStack = new Stack<>();
    private String strCalcu;
    private Integer strLength;
    private static finalHashSet<Character> numStringSet = new HashSet<Character>(){
        {add('0'); add('1');add('2'); add('3'); add('4'); add('5'); add('6'); add('7'); add('8');add('9');}
    };
    private static finalHashSet<Character> operatorSet = new HashSet<Character>(){
        {add('+'); add('-');add('*'); add('/');}
    };
    publicCalculateService(String strCalcu){
        this.strCalcu =strCalcu;
        this.strLength =strCalcu.length();
    }
    private voidpushDouble(Double num){
        doubleStack.push(num);
    }
    private voidpushChar(Character str){
        charStack.push(str);
    }
    private DoublepopDouble(){
        returndoubleStack.pop();
    }
    private CharacterpopChar(){
        returncharStack.pop();
    }
    private Boolean needCalculate(Characterch){
        Boolean res = false;
       if(operatorSet.contains(ch)){
           this.pushChar(ch);//运算符
        }elseif(numStringSet.contains(ch)){
           this.pushDouble(Double.valueOf(String.valueOf(ch)));//数字
        }else if(ch.equals(')')){
            res = true;//要计算的情况
        }
        return res;
    }
    private voidcalculateMiddle(){
        Double sum =this.popDouble();
        Character ch =this.popChar();
        Double num =this.popDouble();
        if(ch.equals('+')){
            sum += num;
        }elseif(ch.equals('-')){
            sum = num - sum;
        }elseif(ch.equals('*')){
            sum *= num;
        }elseif(ch.equals('/') && 0 == sum){
            sum = num / 1;
        }else{
            sum = num / sum;
        }
        this.pushDouble(sum);
    }
    public DoubledealCalculate(){
        for(int i=0;i<this.strLength; i++){
            Character ch =this.strCalcu.charAt(i);
           if(this.needCalculate(ch)){
                this.calculateMiddle();
            }
        }
        returndoubleStack.pop();
    }
}

2、PHP实现

PHP实现上,相对于java,就比较简单粗暴了。因为php没有那么多的规定和数据类型,就是直接用array来存内容,所有的内容都是基于array,不过解答思想上,还是根据双栈的方式。

         <?php
class CalculateService{
         private$doubleStack = array();
   private $charStack = array();
   private $strCalcu;
   private $strLength;
   private static const $numStringSet = array('0', '1', '2', '3', '4', '5','6', '7', '8', '9');
   private static const $operatorSet = array('+', '-', '*', '/');
   public function __construct($strCalcu){
            $this->strCalcu =$strCalcu;
            $this->strLength =strlen($strCalcu);
   }
   private function push($type, $content){
            array_push($this->$type,$content);
   }
   private function pop($type){
            returnarray_pop($this->$type);
   }
   private function needCalculate($ch){
       $res = false;
       if(in_array($ch, self::$operatorSet)){
            $this->push('charStack', $ch);//运算符
       }else if(in_array($ch, self::$numStringSet)){
            $this->push('doubleStack',$ch);//数字
       }else if(')' == $ch){
            $res = true;//要计算的情况
       }
       return $res;
   }
   private function calculateMiddle(){
       $sum = $this->pop('doubleStack');
       $ch = $this->pop('charStack');
       $num = $this->pop('doubleStack');
       if('+' == $ch){
            $sum += $num;
       }else if('-' == $ch){
            $sum = $num - $sum;
       }else if('*' == $ch){
            $sum *= $num;
       }else if('/' == $ch && 0 == $sum){
            $sum = $num / 1;
       }else{
            $sum = (double)$num / $sum;
       }
       $this->push('doubleStack', $sum);
   }  
   public function dealCalculate(){
       for($i=0; $i<$this->strLength; $i++){
            $ch = $this->strCalcu[$i];
            if($this->needCalculate($ch)){
                $this->calculateMiddle();
            }
       }
       return $this->pop('doubleStack');
   }   
}

四、进阶

当前这个算法,是简化版的四则运算,有五个待解决的前提。

1、括号问题

由于目前采用判断有括号的方式,因此,即使1+1,也需要写成(1+1),否则会返回结果1。这显然不合理。而且任意两个数的运算,都需要加括号,无论其优先级。

要解决1+1必须写(1+1)的问题,这个较为简单,需要做两件事情:

1是在字符串都处理结束的时候,检查两个栈,是否数字栈只剩1个元素,运算符栈没有元素。如果不是,则按照倒序,逐个取出数字和运算符进行计算,将栈逐步清空。

2是需要在处理到左括号的时候,也将其存入运算符栈,则当处理到右括号的时候,可以一路追溯到左括号,将一系列的内容都取出进行计算。

2、取数问题

目前是逐个字符取数字,这就造成如果数字超过1位数,例如10,则会被当作1和0分别存入数字栈。

要解决这个问题,也较容易,即当遍历字符串,遍历到的元素是数字时,先暂存这个数字,再遍历下一个元素。如果下一个元素还是数字,则和该元素进行字符串拼接。直到下一个元素是运算符、括号或者没有下一个元素。将这一串拼接的数字,转成double存入数字栈中。

3、负数问题

和取数问题一样,负数例如-1,会被当作-和1分别存入两个栈中。

为了解决这个问题,需要在类中,加一个变量,来判断上一个元素是否是数字。如果上一个元素是数字,则-可以直接进入运算符栈;如果上一个元素不是数字,则需要将-和下一个元素进行计算,可以用0减去下一个数字,将得到的结果存入数字栈。

4、优先级问题

这个问题较为复杂,当没有对所有的运算进行括号限制的时候,就需要程序来判断优先级问题。

要解决这个问题,需要先建立一个优先级列表,可以是一个二维数组,数组按下标从0开始,每一个数组内的保存优先级一致的运算符,且0开始优先级逐渐减小。

这样,当取出运算符的时候,就需要在优先级列表里面进行判断,如果不是最高优先级,还需要再取一个元素,再进行判断。

5、拓展问题

除了四则运算,如果需要拓展到其他运算,如幂、开方、三角函数、对数等,以及特殊常量π、e等,则需要程序里面进行相应的定义。可以指定某些字母作为判断,例如2pow2,可以看作2的平方。

但是,由此,又引申出一个问题,错误处理。由于内容都是输入的,会出现诸多不符合情况的输入,例如连续两个运算符、除以0、括号数量不对等问题。因此,还需要加入错误处理机制,这个是最为复杂的部分。

——written by linhxx 2017.10.10

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2169
来自专栏WOLFRAM

向日葵中的数学之美

1823
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2621
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏marsggbo

Udacity并行计算课程 CS344 编程作业答案

832
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2478
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5866
来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9664

扫码关注云+社区