首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >infix到后缀转换中操作符的优先级

问infix到后缀转换中操作符的优先级
EN

Stack Overflow用户
提问于 2015-06-29 15:22:55
回答 2查看 3.9K关注 0票数 1

我正在用C语言创建一个程序,该程序通过堆栈实现使用反向抛光算法将infix形式的表达式转换为后缀形式。但是,在如何放置与堆栈最顶层元素具有相同优先级的传入令牌时,我遇到了问题。例如,给定infix表单:(a+be/d+e^f^2),后缀形式应该是:ab+cd/-EF2^+。但是,我的程序输出: ab+cd/-ef^2^+。我认为问题在于我的代码的这一部分:

代码语言:javascript
复制
while(priority(token) <= priority(top_elem(&S)) && !isStackEmpty(&S)){
    x = POP(&S);
    printf("%c", x);
}
PUSH(&S, token);

顺便说一下,这个部分只对操作符标记('+‘、'-’、'‘、'/’、'^)和开括号执行。优先级函数为开括号返回0,'+‘和'-’返回1,'‘和'/’返回2,'^‘返回3。

我在想我应该在我的节目里做些什么。不过,对于其他输入,它执行得很好。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2015-06-29 15:30:56

您有一个关联性问题:虽然(a * b) * c == a * (b * c)为真,但对于powerTo (或^):(a ^ b) ^ c != a ^ (b ^ c)则不成立。

当每个操作数的优先级匹配时,您需要解决这个问题:

代码语言:javascript
复制
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);
票数 2
EN

Stack Overflow用户

发布于 2015-06-29 20:36:24

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

分配值的一种方法是使所有左先例都是偶数,而所有右先例都是奇数。根据运算符的相联性,右优先级将比左优先级多一次或少一次。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/31119525

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档