有趣的算法(五) ——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 条评论
登录 后参与评论

相关文章

来自专栏Java3y

Java实现单向链表

一、前言 最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~ 本...

3888
来自专栏desperate633

详解排序算法--插入排序和冒泡排序插入排序和冒泡排序分析

冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把...

741
来自专栏Kevin-ZhangCG

[ Java学习基础 ] Java的继承与多态

2286
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day6 Java字符串

  字符串,是我们最常用的类型,每个用双引号来表示的串都是一个字符串。Java中的字符串是一个预定义的类,跟C++ 一样叫String,而不是Char数组。至于...

1868
来自专栏北京马哥教育

Python语言中list及tuple的使用示例

Python语言中的list Python有一种内置数据类型被称为列表:list。 1.list基本定义 list是一种有序的集合,可以随时添加和删除其中的元...

3117
来自专栏云霄雨霁

子字符串查找----Boyer-Moore算法(从右向左匹配)

1080
来自专栏老九学堂

【必读】C语言基础知识大全

C语言程序的结构认识 用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,使小伙伴对c语言有个初步认识。 例1:计算两个整数之和的c程...

4188
来自专栏PPV课数据科学社区

走近 Python (类比 JS)

Python 是一门运用很广泛的语言,自动化脚本、爬虫,甚至在深度学习领域也都有 Python 的身影。作为一名前端开发者,也了解 ES6 中的很多特性借鉴自 ...

39710
来自专栏轮子工厂

6. 简单又复杂的“运算符”,建议你看一哈

昨天的《5. 很“迷”的字符与字符串》初稿本来很短的,但是我觉得内容太少了,就加了一些,结果好像就变得特别多〒▽〒。

643
来自专栏老九学堂

【必读】超全的C语言基础知识大全

我们用一个简单的c程序例子,介绍c语言的基本构成、格式、以及良好的书写风格,加深小伙伴们对C语言的认识。

1672

扫码关注云+社区