java - Postfix 评估器未返回正确的结果

Question

这个问题已经有答案了:

Handling parenthesis while converting infix expressions to postfix expressions (2 个回答)

已关闭 6 年前。

我一直试图找出我的代码的错误，但没有成功。除了评估后缀表达式之外，我还应该为后缀翻译器编写一个中缀。我的代码运行了，但不幸的是它没有返回正确的值。

我有一个计算器 GUI，只要按下等号，它就会调用下面所示的代码。计算器将由空格分隔的字符串作为参数传递。然后，我在这个空格分隔的字符串上使用字符串分词器并从那里开始工作。如果有帮助的话，我可以提供计算器 GUI 的代码。

我的问题在于计算器提供的答案。例如，如果我输入(5+2)，计算器将返回 2 作为答案，如果我再次按等号，它将返回 5 作为答案。如果我输入 (5*2)+(3*9)，它会返回 9 作为答案，如果我再次按等号，它会返回 5 作为答案。我已多次尝试检查我的代码，但不幸的是我无法找到我的错误。任何帮助将不胜感激!

免责声明:我知道有关使用字符串分词器的旁注。我会使用其他东西，但这是要求之一。我还没有实现任何错误检查或优先级检查，因为我想确保它在假设输入正确并且首先不太复杂的情况下正常工作。另外，我知道我的代码无法正确处理像 (5+2)-1 这样的东西，因为 1 周围缺少括号。但是话又说回来，它无法处理比这更简单的东西。 .一旦我可以让它使用更简单的输入来工作，我就会担心这一点。最后，这确实是一项家庭作业，但请不要以为我希望这完全为我完成。如果您能提供一些建议，我们将不胜感激。

这是我的代码:

public class ExpressionEvaluator {

Stack<String> myStack = new Stack<>();
Queue<String> myQueue = new Queue<>();

String curToken; //Current token of my tokenized string.
double temp1;    //Place holder for first value of the calc section.
double temp2;    //Place holder for second value of the calc section.

public String processInput(String s) {

    StringTokenizer st = new StringTokenizer(s);

    while (st.hasMoreTokens()) {

        curToken = st.nextToken();

        if (openParenthesis(curToken)) {
            myStack.push(curToken);
        }

        if (closeParenthesis(curToken)) {
            do {
                myQueue.enqueue(myStack.pop());
            } while (!openParenthesis(myStack.peek()));
        }

        if (isOperator(curToken)) {
            while (!myStack.isEmpty() && !openParenthesis(myStack.peek())) {
                myQueue.enqueue(myStack.pop());
            }
            myStack.push(curToken);
        }
        if (isDouble(curToken)) {
            myQueue.enqueue(curToken);
        }
    }

    while (!myStack.isEmpty()) {
        myQueue.enqueue(myStack.pop());
    }

    while (!myQueue.isEmpty()) {
        if (isDouble(myQueue.peek())) {
            myStack.push(myQueue.dequeue());
        }

        else if (isOperator(myQueue.peek())) {
            temp1 = Double.parseDouble(myStack.pop());
            temp2 = Double.parseDouble(myStack.pop());
            myStack.push(Double.toString(calc(temp1, temp2)));
        }

        else {
            myQueue.dequeue();
        }
    }
    return myStack.pop();
}

 //Private methods used to simplify/clarify some things.


 //Checks if input is an operator, returns true if it is
private boolean isOperator(String str) {
    if (str == "+") {return true;}
    else if (str == "-") {return true;}
    else if (str == "*") {return true;}
    else if (str == "/") {return true;}
    else if (str == "^") {return true;}
    else {return false;}
}

 //Checks if input is an open parenthesis "(", returns true if it is

private boolean openParenthesis(String str) {
    if (str == "(") {return true;}
    else {return false;}
}

 //Checks if input is a close parenthesis ")", returns true if it is

private boolean closeParenthesis(String str) {
    if (str == ")") {return true;}
    else {return false;}
}

 //Checks if input is a double, returns true if it is
 //I actually got this method from Stack Overflow, so thanks!

private boolean isDouble(String str) {
    try {
        Double.parseDouble(str);
        return true;
    } catch (NumberFormatException e) {
        return false;
    }
}

 //Method used to actually do the calculations. I have
 //a feeling this is where my problem is, but I can't
 //think of a way to fix it.

private double calc(double a, double b) {
    String op = myQueue.dequeue();

    if (op == "+") {return a+b;}
    else if (op == "-") {return a-b;}
    else if (op == "*") {return a*b;}
    else if (op == "/") {return a/b;}
    else if (op == "^") {return Math.pow(a, b);}
    else {throw new UnknownElementException(null, "ERROR");}
}
 }

很抱歉出现奇怪的缩进。任何帮助将不胜感激!

Answer 1

有一个名为Shunting-yard的算法，它指定如何将中缀表示法转换为后缀表示法(也称为“逆波兰表示法”)。那么您就不必担心运算符优先级。

它使用队列和堆栈。基本上，当您遇到一个数字时，您会将其添加到队列中。当您遇到运算符时，您将它们插入堆栈。

您可以在这里找到详细的算法:Shunting-Yard Algorithm

一旦采用逆波兰表示法，您可以轻松地对其进行评估，如下所述: Postfix evaluation algorithm