Java Calculator - Shunting yard

Question

I'm trying to implement Dijkstra's algorithm Shunting-yard to read a mathmathical equation with simple actions (+-/*). It basically gets an "infix" string and turns it into a "postfix" string.

E.G. : Input -> "(3+5)*4-12" . Output: Queue[3,5,+,4, *,12,-]

While reading from right to left, you see you need to subtract 12 from a multiplication of 4 by an addition of 3 and 5.

I've done this correctly. I thought the easiest way to interpret the queue into a calculation would be with recursion, so I've came up with the following code:

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));

}

It works for almost any string, except strings like the following:

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

After Shunting yard , the Queue output is : [3,5,+,4, *,12,1,+,-]

The problem with this, is that the recursion is returning (3+5)*4 -(12+1) which is wrong, and I can't figure out how to fix this (I know I can use an iterative solution, but I want to understand how I can make this work).

Thanks.

EDIT:

My Shunting yard algo:

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

As @BillTheLizard suggested in the comments of this question, the recursion was fine, the problem was with my Shunting yard algorithem. The UML of the code said to replace two operators only if one has precedence over the other, but they forgot to mention that I also need to keep the original order of the operators when no precedence between the two operators (specifically with + and - that has differences in different execution orders). This fixed the issue:

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);

Thanks for the help.