Infix to Postfix 表达式中的结合性规则

Question

我的 infix 到 postfix 算法使用 stack:

static int Prec(char ch) {
    switch (ch) {
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '^':
        return 3;
    }
    return -1;
}

static String infixToPostfix(String exp) {
    String result = new String("");
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < exp.length(); ++i) {
        char c = exp.charAt(i);
        if (Character.isLetterOrDigit(c))
            result += c;
        else if (c == '(')
            stack.push(c);
        else if (c == ')') {
            while (!stack.isEmpty() && stack.peek() != '(')
                result += stack.pop();
            stack.pop();
        } else {
            while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek())) {
                result += stack.pop();
            }
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) {
        if (stack.peek() == '(')
            return "Invalid Expression";
        result += stack.pop();
    }
    return result;
}

输入： K+L-M*N+(O^P)*W/U/V*T+Q^J^A

预期输出： KL+MN*-OP^W*U/V/T*+QJA^^+

实际输出： KL+MN*-OP^W*U/V/T*+QJ^A^+

If current operator and operator at top of stack have same precedence then check their associativity,

If associativity of operators is Right to Left, then simply push operator onto the stack.

If associativity of operators is Left to Right, then pop operator from stack and check for associativity again for current operator and operator at top of stack.

预期输出和实际输出的不同之处在于计算子表达式 ^J^A 时。当到达字符 Q 时，堆栈包含 ['+']。我输出操作数 Q 并移动到表达式中的下一个字符。关于上述规则，应该发生以下情况：

^ 是 Q 之后的下一个字符。由于 ^ 的优先级高于 +，我将其压入堆栈，['+','^'] 并将指针移动到 J.
输出J作为操作数并移动指针。
指针现在位于 ^。由于栈顶还包含一个^，它们具有相同的优先级，所以我们需要检查从右到左的关联规则。因此，我们将 ^ 压入堆栈。所以堆栈看起来像 ['+','^','^'].
指针现在是最后一个字符 A 所以直接输出它。
因为我们已经到达表达式的末尾，我们可以开始从堆栈中弹出运算符，这样子表达式的后缀形式将类似于 QJA^^+.

但是，我的代码不适用于关联性。有人可以解释一下在上述实现中如何处理关联性吗？

Answer 1

这是一个简单的修复。您需要从以下位置更新 while 循环条件：

while (!stack.isEmpty() && Prec(c) <= Prec(stack.peek()))

收件人：

while (!stack.isEmpty() && (prec(c) < prec(stack.peek()) || (prec(c) == prec(stack.peek()) && isLeftToRightAssociative(stack.peek()))))

方法如下isLeftToRightAssociative():

public static boolean isLeftToRightAssociative(Character operator)
{
    //You can also use return operator != '^' as an alternative to the if-else given below
    if (operator == '^') return false;
    else return true;      
}

我应该补充一点，如果用户输入包含 unary operators 的表达式，您的代码将不会产生正确的输出。如果您将使用 unary operators，您应该更新您的代码。

Answer 2

轻松修复 - 在 else 语句之前添加另一个 else if

else if (c==stack.peek() and c=='^')
{ stack.push(c); }

Infix to Postfix 表达式中的结合性规则

Associativity rule in Infix to Postfix expression

java

algorithm

stack

postfix-notation

infix-notation