Java计算器-调车场

Question

我试图实现迪克斯特拉算法 Shunting-yard来读取一个简单操作的数学方程(+-/*)。它基本上得到一个"infix“字符串，并将其转换为”后缀“字符串。

例如:输入-> "(3+5)*4-12"。输出：Queue[3,5,+,4, *,12,-]

当你从右到左阅读时，你会发现你需要从乘法4中减去12，再加上3和5。

我做得很对。我认为将队列解释为计算的最简单方法是使用递归，因此我提出了以下代码：

public static Expression newCalc(ArrayDeque<String> q)//q is the output of Shunting yard algo
{
    String tmp =q.pollLast();
    if(tmp.equals("*") || tmp.equals("/") || tmp.equals("+") || tmp.equals("-")) {
        Expression rightOperation = newCalc(q);
        Expression leftOperation = newCalc(q);
        if(tmp.equals("+")) 
            return new Plus(leftOperation,rightOperation);
        else if(tmp.equals("-"))
            return new Minus(leftOperation,rightOperation);
        else if(tmp.equals("*"))
            return new Mul(leftOperation,rightOperation);
        else if(tmp.equals("/"))
            return new Div(leftOperation,rightOperation);
        else
            return new Number(0);
    }
    else 
        return new Number(Double.parseDouble(tmp));

}

它适用于几乎任何字符串，但如下所示的字符串除外：

"(3+5)*4-12+1"

在调车场之后，队列输出为：[3,5,+,4, *,12,1,+,-]

问题在于，递归返回(3+5)*4 -(12+1)，这是错误的，我无法解决这个问题(我知道我可以使用迭代解决方案，但我想了解如何使这个问题工作)。

谢谢。

编辑：

我的调车场

public static double calc(String expression){

    Stack<String> s = new Stack<String>();  
    ArrayDeque<String> q = new ArrayDeque<String>();
    StringBuilder sb = new StringBuilder(expression);
    String token = new String();

    while((token = atoi(sb)) != null) {
    //atoi is a method that extract the correct next token ,cut it it from the string and return it.
        if(token.equals("/")|| token.equals("-")|| token.equals("+")|| token.equals("*")) {
            while ((token.equals("-")||token.equals("+"))&&
                    !s.isEmpty()&&
                    ((s.peek().equals("*")||s.peek().equals("/"))))
                q.add(s.pop());
            s.push(token);
        }
        else if(token.equals("("))
            s.push(token);
        else if(token.equals(")"))
        {
            while(!s.peek().equals("("))
                q.add(s.pop());
            s.pop();    
        }       
        else 
        {
            q.add(token);
        }
    }
    while(!s.isEmpty()&&(s.peek().equals("/")||s.peek().equals("*")||s.peek().equals("+")||s.peek().equals("-")))
        q.add(s.pop());
    return Math.floor(newCalc(q).calculate()*1000)/1000;

}

Answer 1

正如@BillThe蜥蜴在这个问题的评论中所暗示的那样，递归是好的，问题在于我的分流场算法。代码的UML说，只有在一个操作符优先于另一个操作符的情况下，才会替换两个操作符，但是他们忘了提到，当两个操作符之间没有优先级时，我也需要保留操作符的原始顺序(特别是+和-，这在不同的执行顺序上有差异)。这就解决了问题：

while ((token.equals("-")||token.equals("+"))&& 
        !s.isEmpty()&&
        ((!s.peek().equals("(")&&!s.peek().equals(")")))) // I've changed this line
    q.add(s.pop());
s.push(token);

谢谢你的帮助。