Java计算器-调车场

我正在努力实现 Dijkstra's algorithm Shunting-yard 用简单的动作(+-/*)阅读数学方程式。它基本上得到一个“中缀”字符串并将其转换为“后缀”字符串。

例如:输入-> "(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;

}