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

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

顺便说一句，这部分只针对运算符标记（'+'、'-'、''、'/'、'^）和左括号执行。优先级函数returns 0为左括号，1为'+'和'-'，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

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

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

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

Precedence of operators in infix to postfix conversion

c

stack

operator-precedence