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

一 代码

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

三 求值轨迹

四 代码参考

https://gitee.com/cakin24/Algorithm