有趣的算法(五)——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