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

Associativity rule in Infix to Postfix expression

我的 infixpostfix 算法使用 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 并移动到表达式中的下一个字符。关于上述规则,应该发生以下情况:

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

这是一个简单的修复。您需要从以下位置更新 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,您应该更新您的代码。

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

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