Java计算器 - 调车场

Question

我正在尝试使用简单的动作(+ - /*)来实现Dijkstra算法 Shunting-yard来读取数学方程式.它基本上得到一个"中缀"字符串,并将其转换为"后缀"字符串.

EG:输入 - > "(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

正如@BillTheLizard 在这个问题的评论中所建议的，递归很好，问题出在我的调车场算法上。代码的 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);

谢谢您的帮助。