使用双栈解析小数负数算术表达式的一些想法

最近因为一些原因，我需要写一个简易的计算器，需要支持加减乘除,小数和负数运算。其实思路很简单，无非就是使用双栈解析一串算术表达式的文本。《算法》一书中也有一个简单的demo。但如何快速高效的解析，便成了一个问题。

百度了一圈，发现很多文章要先把表达式转成后缀表达式，再实现求值。例如java实现算术表达式求值，但这么做真的有必要吗？只是解析加减乘除需要这么多代码吗？我对此抱有疑问。

我的疑问在于，转成后缀表达式无非就是对数字和操作符进行入栈和出栈的操作，但这个操作不转成后缀表达式也是可以的。下面是我的代码。

public static BigDecimal calculate(char[] array)  {
        Stack<String> opsStack = new Stack<>();//操作符栈
        Stack<BigDecimal> valuesStack = new Stack<>();//值栈
        String valueString = "";
        int count=0;
        //遍历的时候进行区分
        for (char a : array) {
            if (a == '-'&&count==0) {//为了能支持第一个数是负数进行判断
                valueString+="-";
            } else if (a == '+' || a == '*' || a == '/'||a=='-') {
                opsStack.push(String.valueOf(a));
                valuesStack.push(new BigDecimal(valueString));
                valueString = "";
            } else {
                valueString += String.valueOf(a);
            }
            count++;
        }
        if (!valueString.equals("")) {
            valuesStack.push(new BigDecimal(valueString));
        }
        int size = opsStack.size();
        BigDecimal value = new BigDecimal(0);
        String ops1 = "";
        for (int i = 0; i < size; i++) {
            BigDecimal tmp1 = valuesStack.pop();
            BigDecimal tmp2 = valuesStack.pop();
            String opsLast = opsStack.pop();//栈顶的操作符
            String afterLast = opsStack.isEmpty() ? "" : opsStack.peek();//倒数第二个操作符
            /*
             * 下面两行代码进行优先级判断，因为目前没有括号，所以只用判断最后一个和倒数第二个操作符的优先级
             */
            boolean isLastLow = opsLast.equals("+") || opsLast.equals("-");
            boolean isAfterHighter = afterLast.equals("*") || afterLast.equals("/");
            if (isLastLow && isAfterHighter) {
                value = tmp1;
                ops1 = opsLast;
                valuesStack.push(tmp2);
            } else {
                BigDecimal tmpValue = new BigDecimal(0);
                if (afterLast.equals("-")) {
                    tmp2 = new BigDecimal(-1).multiply(tmp2);
                }
                switch (opsLast) {
                case "+":
                    tmpValue = tmp2.add(tmp1);
                    break;
                case "-":
                    tmpValue = tmp2.subtract(tmp1);
                    break;
                case "*":
                    tmpValue = tmp2.multiply(tmp1);
                    break;
                case "/":
                    tmpValue = tmp2.divide(tmp1, 10, BigDecimal.ROUND_DOWN);
                    break;
                }
                if (!ops1.equals("")) {
                    switch (ops1) {
                    case "+":
                    case "-":
                        valuesStack.push(tmpValue.add(value));
                        break;
                    case "*":
                        valuesStack.push(tmpValue.multiply(value));
                        break;
                    case "/":
                        valuesStack.push(tmpValue.divide(value, 10, BigDecimal.ROUND_DOWN));
                        break;
                    }
                    ops1 = "";
                } else {
                    valuesStack.push(tmpValue);
                }
            }
        }

        return valuesStack.pop();
    }

下面是测试用例

小数负数测试.png

因为比较懒，所以没有进行四舍五入之类的操作了。以后要支持其他运算符例如log的话，只需要在优先级那里加以判断就行了。而加入需要支持括号的话，则就会变的很复杂了。《算法》一书中的Dijkstra的双栈算法很优雅，但局限性很大，有几个操作符就需要几个括号。但我大概想了一下，括号会存在嵌套的情况，需要由内到外进行操作，或许把最外层括号内的包括括号存入操作符栈，之后当遍历操作符栈遇到括号时候，再把这个括号内的数进行之前的解析，而内层括号里的数字和括号存入另一个操作符栈，类似递归。但这个写起来太费时间就不写了。

欢迎大家对我的文章提出意见和建议