Dijkstra双栈算术表达式求值算法

痛定思痛。 2021-07-24 17:38 366阅读 0赞

**一 代码**

package MyEvaluate;
    
    import common.Stack;
    import common.StdIn;
    import common.StdOut;
    
    /**
    * Copyright (C), 2020-2020, XXX有限公司
    * FileName: Evaluate
    * Author:   cakin
    * Date:     2020/1/18
    * Description: Dijkstra算法的算术表达式求值
    */
    public class Evaluate {
        public static void main( String[] args ) {
            Stack<String> ops = new Stack<String>();
            Stack<Double> vals = new Stack<Double>();
            while(!StdIn.isEmpty()){
                String s = StdIn.readString();
                if(s.equals("(")){}
                else if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")||s.equals("sqrt")){
                    ops.push(s);
                }
                else if(s.equals(")")){
                    String op = ops.pop();
                    double v = vals.pop();
                    if(op.equals("+")){
                        v = vals.pop() + v;
                    }else if(op.equals("-")){
                        v = vals.pop() - v;
                    }else if(op.equals("*")){
                        v = vals.pop() * v;
                    }else if(op.equals("/")){
                        v = vals.pop() / v;
                    }else if(op.equals("sqrt")){
                        v = Math.sqrt(v);
                    }
                    vals.push(v);
                }
                else {
                    vals.push(Double.parseDouble(s));
                }
            }
            StdOut.println(vals.pop());
        }
    }

**二 测试**

( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )
    ^D
    101.0

**三 求值轨迹**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

**四 代码参考**

[https://gitee.com/cakin24/Algorithm][https_gitee.com_cakin24_Algorithm]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/1daab952bb0a4ec5a6e2408a33d661ac.png
[https_gitee.com_cakin24_Algorithm]: https://gitee.com/cakin24/Algorithm