c-运算符在中缀到后缀转换中的优先级

Question

我正在用C语言创建一个程序，该程序通过堆栈实现使用反向抛光算法将中缀形式的表达式转换为后缀形式。然而，我遇到了一个问题，即如何放置一个优先级与堆栈最顶层元素相同的传入令牌。例如，给定中缀形式：（a+b-c/d+e^f^2），后缀形式应该是：ab+cd/-ef2^^+。然而，我的程序输出：ab+cd/-ef^2 ^+。我认为问题出在我的代码的这一部分：

while(priority(token) <= priority(top_elem(&S)) && !isStackEmpty(&S)){
    x = POP(&S);
    printf("%c", x);
}
PUSH(&S, token);

顺便说一句，此部分仅对运算符标记（"+"、"-"、""、"/"、"^"）和左括号执行。priority函数为左括号返回0，为"+"one_answers"-"返回1，为""one_answers"/"返回2，为"^"返回3。

我在想我的课程应该改什么。不过，它对其他输入执行良好。

Answer 1

您有一个关联性问题：虽然(a * b) * c == a * (b * c)成立，但powerTo（或^）不成立：(a ^ b) ^ c != a ^ (b ^ c)。

当优先级匹配时，您需要为每个操作数解决此问题：

while(!isStackEmpty(&S) &&
      (priority(token) < priority(top_elem(&S)) ||
       priority(token) == priority(top_elem(&S)) && !isRightAsoc(token)))
{
    x = POP(&S);
    printf("%c", x);
}
PUSH(&S, token);

Answer 2

最简单的解决方案是给所有运算符两个优先级值：左优先级和右优先级。您总是将堆栈上符号的左优先级与输入符号的右优先级进行比较。

赋值的一种方法是使所有左先验为偶数，使所有右先验为奇数。右侧优先级将比左侧优先级多一个或少一个，具体取决于运算符的关联性。