首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >优先方程(表达式)解析器?

问优先方程(表达式)解析器?
EN

Stack Overflow用户
提问于 2008-08-26 14:52:05
回答 22查看 98.2K关注 0票数 116

我开发了一个方程解析器,它使用一个简单的堆栈算法,它将处理二进制(+,-,binary,&,*,/等)操作符,一元(!)运算符和括号。

然而,使用此方法,所有具有相同优先级的事物都将保留下来--它是从左到右计算的,而不管是哪个操作符,尽管可以使用括号强制执行优先级。

因此,现在"1+11*5“返回60,而不是人们可能预期的56。

虽然这是适合当前项目,我想有一个通用的例程,我可以使用在以后的项目。

编辑的清晰度:

什么是优先分析方程的好算法?

我对一些简单的实现感兴趣,并理解我可以为自己编写代码以避免使用可用代码的许可问题。

语法:

我不懂语法问题--这是我亲手写的。这很简单,我不认为需要YACC或Bison。我只需要用"2+3 * (42/13)“这样的方程计算字符串。

语言:

我用C语言做这件事,但我对算法感兴趣,而不是语言特定的解决方案。C级别很低,如果需要的话,很容易转换成另一种语言。

代码示例

我在上面发布了我所说的简单表达式解析器的测试代码。项目需求发生了变化,因此我从来不需要为性能或空间优化代码,因为它没有被合并到项目中。它是原始的详细形式,应该是容易理解的。如果我在运算符优先级方面做进一步的工作,我可能会选择宏黑客,因为它简单地与程序的其余部分相匹配。不过,如果我曾经在实际项目中使用过它,我将使用一个更紧凑/更快速的解析器。

相关问题

数学解析器的智能设计?

-Adam

EN

回答 22

Stack Overflow用户

发布于 2008-09-06 18:38:43

调车码算法是正确的工具。维基百科对此非常困惑,但基本上这种算法的工作原理如下:

比如说,你想要评估1+2*3+ 4。直觉地说,你“知道”你必须先做2*3,但是你怎么得到这个结果呢?关键是要认识到,当您从左到右扫描字符串时,当跟随的操作符具有较低(或等于)优先级时,您将计算一个操作符。在示例的上下文中,下面是您想要做的事情:

  1. 看:1+ 2,什么都别做。
  2. 现在看1+2* 3,仍然什么也不做。
  3. 现在看看1+2*3+ 4,现在您知道了,由于下一个操作符的优先级较低,所以必须对2*3进行计算。

你是如何实现这一点的?

您希望有两个堆栈,一个用于数字,另一个用于运算符。你总是把数字推到堆栈上。将每个新运算符与堆栈顶部的运算符进行比较,如果堆栈顶部的运算符具有更高的优先级,则将其从运算符堆栈中弹出,从数字堆栈中弹出操作数,应用运算符并将结果推到数字堆栈上。现在,您可以使用堆栈操作符的顶部重复比较。

回到这个例子,它的工作方式如下:

N=操作

  • 读1. n= 1,操作=
  • 读+。N= 1,操作=+
  • 读2. n=12,操作=+
  • 读*。N=12,操作=+*
  • 读3. n=12. 3,操作=+*
  • 读+。N=12 3,Ops =+*
    • Pop 3,2并执行2*3,并将结果推到N. N=1 6,Ops =+
    • +是左关联的,所以您希望弹出1,6关闭并执行+。N= 7,操作= []。
    • 最后,将+推到运算符堆栈上。N= 7,操作= +。

​

  • 读4.n=7.4.OPS= +。
  • 输入不足,所以现在要清空堆栈。这样你就能得到结果。

那里,这并不难,是吗?它不调用任何语法或解析器生成器。

票数 175
EN

Stack Overflow用户

发布于 2010-03-25 16:27:22

parsing.htm

很好地解释了不同的方法:

  • 递归下降识别
  • 调车码算法
  • 经典解
  • 优先爬升

用简单的语言和伪代码写的。

我喜欢“优先攀登”。

票数 27
EN

Stack Overflow用户

发布于 2008-10-09 06:06:34

有一篇很好的文章这里关于将简单的递归下降解析器与操作符优先解析结合起来。如果您最近一直在编写解析器,那么阅读应该是非常有趣和有教育意义的。

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

https://stackoverflow.com/questions/28256

复制
相关文章

相似问题

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