我正在用C语言创建一个程序,该程序通过堆栈实现使用反向抛光算法将infix形式的表达式转换为后缀形式。但是,在如何放置与堆栈最顶层元素具有相同优先级的传入令牌时,我遇到了问题。例如,给定infix表单:(a+be/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);顺便说一下,这个部分只对操作符标记('+‘、'-’、'‘、'/’、'^)和开括号执行。优先级函数为开括号返回0,'+‘和'-’返回1,'‘和'/’返回2,'^‘返回3。
我在想我应该在我的节目里做些什么。不过,对于其他输入,它执行得很好。
发布于 2015-06-29 15:30:56
您有一个关联性问题:虽然(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);发布于 2015-06-29 20:36:24
最简单的解决方案是给所有运算符两个优先值:左优先和右优先。您总是将堆栈上符号的左优先级与输入符号的右优先级进行比较。
分配值的一种方法是使所有左先例都是偶数,而所有右先例都是奇数。根据运算符的相联性,右优先级将比左优先级多一次或少一次。
https://stackoverflow.com/questions/31119525
复制相似问题