算法第四版 P80 Dijkstra的双栈算术表达式求值算法

逃离我推掉我的手 2022-03-19 09:22 150阅读 0赞

# 目的 #

根据书的算法,自己理解以后自己**默写**出算法

# java代码 #

package book1_3;
    
    import edu.princeton.cs.algs4.Stack;
    
    /**
     * @description: $Dijkstra的双栈算术表达式求值算法
     * 双栈就是数字栈和操作符号栈
     * @create: 2019-02-16
     **/
    public class Evaluate {
        /*expression表达式的规则是:
        1.每个计算都有双括号
        2.数字和加减乘除以及括号之间存在空格
        * */
        public static double cal(String expression){
            String[] stringArray = expression.split(" ");
            Stack<String> fuhao=new Stack<String>();//1操作符号栈
            Stack<Double> number=new Stack<Double>();//2数字栈
            for (String s:stringArray) {
                //表达式从左往右.逐个读取
                //第一种情况,遇到左括号,则什么都不做
                if(s.equals("(")){
    
                }else if (s.equals("+")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                fuhao.push("+");
                }else if (s.equals("-")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("-");
                }else if (s.equals("*")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("*");
                }else if (s.equals("/")){//第二种情况,遇到加减乘除,则放到1操作符号栈里面
                    fuhao.push("/");
                }else if(s.equals(")")){//第三种情况,遇到右括号.则从操作符号栈中取出1个操作符号,从数字栈中取出2个数字
                    double pop1 = number.pop();
                    double pop2 = number.pop();
                    String jisuanfu = fuhao.pop();
                    double result=0.0;
                    //根据操作符号来计算这两个数字
                    //注意:栈是后进先出的,因此先取的pop1要放到pop2的后面
                    /*举例:12/4
                    * 数字栈放进去后是:
                    * 4
                    * 12
                    * 数字栈取出来后是:
                    * pop1=4    pop2=12
                    * 所以是pop2/pop1 而不是pop1/pop2
                    * */
                    if(jisuanfu.equals("+")){
                        result=pop2+pop1;
                    }else if(jisuanfu.equals("-")){
                        result=pop2-pop1;
                    }else if(jisuanfu.equals("*")){
                        result=pop2*pop1;
                    }else if(jisuanfu.equals("/")){
                        result=pop2/pop1;
                    }
                    number.push(result);
                }else {//第四种情况,排除了左右括号和操作符号以外.只剩下一种情况,数字,数字无脑放到数字栈
                    number.push(Double.valueOf(s));
                }
            }
            /*
            * 全部计算完毕后,数字栈只剩下一个数字了,就是计算的结果.取出来返回即可
            * */
            return number.pop();
        }
    
        public static void main(String[] args) {
            String expression1="( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )";
            double cal1 = cal(expression1);
            System.out.println(cal1);
            System.out.println("-------");
            String expression2="( 12 + ( ( 8 / 4 ) * ( 9 - 5 ) ) )";
            double cal2 = cal(expression2);
            System.out.println(cal2);
        }
    }

# 结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 心得 #

1.利用两个栈来分别存不同的数据:一个存放数字,另一个存放操作符号  
2.栈后进先出,就说明取出来是最新的,右括号左边最近的两个数字就是最新的  
3.泛型可以让栈变得比较专业.放数字就放数字,放字符串String就放String  
4.利用Double.parseDouble(String s),String转为Double  
5.也可以利用Double.valueOf(String s),String转为Double  
6.取出来的来个数字pop1和pop2的顺序要颠倒下.因为原始表达式的数字顺序放到栈里面,然后再取出来,顺序就变颠倒了  
7.大量的if elseif else可以转换成switch语法

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220319/934026f7c38846309eebd9c7b043c92b.png