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

相关文章

来自专栏云霄雨霁

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

860
来自专栏生信小驿站

python-运算符与表达式

你所编写的大多数语句(逻辑行)都包含了表达式(Expressions)。一个表达式的简单例子便是 2+3。表达式可以拆分成运算符(Operators)与操作数(...

582
来自专栏柠檬先生

Sass 基础(六)

join() 函数    join()函数是将两个列表连接合并成一个列表。    >>join(10px 20px, 30px 40px)       (...

19010
来自专栏LIN_ZONE

css 使元素居中

<div style="text-align:center;">居中显示</div>

574
来自专栏架构说

c 语言基础知识之一

Q1 : 今天看redis代码 普通的函数都添加static 修改 static int aeApiCreate(aeEventLoop *eventLoop...

26111
来自专栏玄魂工作室

如何学python 第八课 流程控制-For,While,循环语句,函数

循环语句 也许你会问,什么是‘循环’?在脚本程序里,循环就是‘在一定情况下一次又一次的执行某些代码’。举个例子来说,假设你很饿,桌上有好多好多个馒头,当你依旧饿...

3349
来自专栏蓝天

c99 增加的restrict关键字

c99中新增加了一个类型定义,就是restrict。 restrict的定义是It can be applied only to pointers, and i...

532
来自专栏用户2442861的专栏

深入 char * ,char ** ,char a[ ] ,char *a[] 内核

http://blog.csdn.net/daiyutage/article/details/8604720

192
来自专栏前端架构与工程

【译】《Understanding ECMAScript6》- 第一章-基础知识(二)

块绑定 JavaScript中使用var进行变量声明的机制非常怪异。在大多数C系列的编程语言中,变量的创建是在被声明的时刻同时进行的。但是JavaScript并...

2465
来自专栏Android机动车

转向Kotlin——泛型

无论是Java还是Kotlin,泛型都是一个非常重要的概念,简单的泛型应用很容易理解,不过也有理解起来麻烦的时候。一起来认识一下。

722

扫描关注云+社区