中缀后缀表达式中的关联规则

Question

使用堆栈的中缀到后缀算法：

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^+

如果当前运算符和堆栈顶部的运算符具有相同的优先级，则检查它们的相关性，

null

null

然而，我的代码不适合于关联。有人能解释一下在上面的实现中如何处理关联性吗？

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

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