双栈算数表达式求值算法

拼搏现实的明天。 2022-06-06 10:47 178阅读 0赞

/** * 双栈算数表达式求值算法 * 思路: * 1.将操作数压入操作数栈； * 2.将运算符压入运算符栈； * 3.忽略左括号； * 4.在遇到右括号时，弹出一个运算符， * 弹出所需要的操作数， * 并将运算符和操作数的运算结果压入操作数栈。 */
    public class Evaluate { 
        public static void main(String[] args) {
            String expression = "(1+((2+3)*(4*5)))";
            Evaluate e = new Evaluate();
            double cal = e.cal(expression);
            System.out.println(cal);
        }
        public double cal(String expression) {
            char[] charArray = expression.toCharArray();
            Stack<String> ops = new Stack<String>();//运算符栈
            Stack<Double> vals = new Stack<Double>();//操作数栈
            int length = charArray.length;
            for(int i = 0; i < length;i++) {
                String s = String.valueOf(charArray[i]);
                if(s.equals("(")) {
                    //忽略
                }else if(s.equals("+")) {
                    ops.push(s);//将运算符压入运算符栈
                }else if(s.equals("-")) {
                    ops.push(s);//将运算符压入运算符栈
                }else if(s.equals("*")) {
                    ops.push(s);//将运算符压入运算符栈
                }else if(s.equals("/")) {
                    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;
                    }
                    vals.push(v);//把计算的结果压入操作数栈
                }else {
                    //将操作数压入操作数栈
                    vals.push(Double.parseDouble(s));
                }
            }
            return vals.pop();
        }
    }

![这里写图片描述][SouthEast]

[SouthEast]: /images/20220606/63c19ee1dd4141448af85f1c344592a6.png