具有优先级的等式（表达式）解析器？
我开发了一个使用简单堆栈算法的公式解析器，该算法将处理二元（+， - ，|，＆，*，/等）运算符，一元（！）运算符和括号。
然而，使用这种方法会让我看到所有具有相同优先级的东西 - 无论运算符如何，都会从左向右进行评估，但优先级可以使用括号强制执行。
所以现在“1 + 11 * 5”返回60，而不是人们所期望的那样。
虽然这适用于当前的项目，但我希望有一个通用的例程供我以后的项目使用。
为清晰起见编辑：
解析具有优先级的方程式的好算法是什么？
我对一些简单的实现感兴趣，并且明白我可以编写自己的代码来避免使用可用代码的许可问题。
语法：
我不明白这个语法问题 - 我手写的。 很简单，我没有看到YACC或Bison的需要。 我只需要用等式如“2 + 3 *（42/13）”来计算字符串。
语言：
我在C中这样做，但我对算法感兴趣，而不是语言特定的解决方案。 C的级别足够低，以便在需要时很容易转换为另一种语言。
代码示例
我发布了上面讨论的简单表达式解析器的测试代码。 项目需求发生了变化，因此我从不需要优化性能或空间的代码，因为它并未纳入项目中。 它采用了最初的详细形式，应该容易理解。 如果我在运算符优先级方面做了进一步处理，我可能会选择宏hack，因为它与简单程序的其余部分相匹配。 如果我曾经在一个真实的项目中使用过这个，我将会选择一个更加紧凑/快速的解析器。
相关问题
数学解析器的智能设计？
-亚当
困难的方式
你想要一个递归下降解析器。
要获得优先权，您需要递归思考，例如，使用您的示例字符串，
1+11*5
要做到这一点手动，你必须阅读1 ，然后看到加号，并开始一个全新的递归解析“会话”从11开始......并确保将11 * 5解析为它自己的因素，产生一个解析树1 + (11 * 5) 。
这一切都感到非常痛苦，甚至试图解释，尤其是在C的增加无能为力的情况下。请参见解析11之后，如果*实际上是a +，那么您将不得不放弃尝试制定术语，而是解析11本身就是一个因素。 我的头已经爆炸了。 递归体面战略是可能的，但有一个更好的方法...
简单（正确）的方法
如果您使用像Bison这样的GPL工具，您可能不需要担心授权问题，因为由bison生成的C代码不在GPL范围内（IANAL，但我确信GPL工具不会强制GPL开启生成的代码/二进制文件;例如Apple编译代码，比如说，Aperture with GCC，并且它们在不需要GPL代码的情况下销售它）。
下载野牛（或其他相当的东西，ANTLR等）。
通常有一些示例代码可以运行野牛，并获得您所需的C代码来演示这四个函数计算器：
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
看看生成的代码，看看这不像听起来那么容易。 另外，使用像Bison这样的工具的好处是：1）你学到了一些东西（特别是如果你阅读龙书并学习语法），2）避免NIH试图重新发明轮子。 使用真正的解析器生成器工具，您实际上有望在稍后扩展，向其他人展示解析器是解析工具的领域。
更新：
这里的人提供了很多合理的建议。 我唯一的反对跳过解析工具或仅使用Shunting Yard算法或手卷递归体解析器的警告是，有一点玩具语言1可能有一天变成具有函数（sin，cos，log）和变量，条件和for循环的大型实际语言。
Flex / Bison对于一个小而简单的解释器来说可能是过分的矫枉过正，但当需要进行更改或需要添加功能时，一个解析器+评估器可能会导致故障。 你的情况会有所不同，你需要使用你的判断; 只是不要因为你的罪而惩罚别人[2]，并且建立一个不够充分的工具。
我最喜欢的解析工具
世界上最好的工具是用于编程语言Haskell的Parsec库（用于递归体裁解析器）。 它看起来很像BNF，或者像一些专门用于解析的工具或领域专用语言（示例代码[3]），但它实际上只是Haskell中的一个常规库，意味着它在与其余部分相同的构建步骤中编译的Haskell代码，并且您可以编写任意Haskell代码并在您的解析器中调用该代码，并且可以在同一代码中混合并匹配其他库。 （顺便说一下，在Haskell之外的语言中嵌入这样的解析语言会导致大量的语法错误，我在C＃中做了这样的工作，它运行得非常好，但它并不那么漂亮和简洁。）
笔记：
1 Richard Stallman说，为什么你不应该使用Tcl
Emacs的主要教训是扩展语言不应该仅仅是一种“扩展语言”。 它应该是一种真正的编程语言，专为编写和维护大量程序而设计。 因为人们会想要这样做！
[2]是的，我永远因使用这种“语言”而伤痕累累。
另外请注意，当我提交这个条目时，预览是正确的，但是SO不足以解析我的第一段的关闭锚标签 ，证明解析器不会被忽略，因为如果你使用正则表达式和一个关闭你可能会得到一些微妙的错误 。
[3]使用Parsec的Haskell解析器的代码片段：一个四元函数计算器，扩展了指数，圆括号，乘法空白和常量（如pi和e）。
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
分流码算法是这个的正确工具。 维基百科对此很困惑，但基本上这种算法是这样工作的：
说，你想评估1 + 2 * 3 + 4.直觉上，你“知道”你必须先做2 * 3，但你如何得到这个结果？ 关键是要认识到，由左到右，当你扫描的字符串，你将评估操作时遵循它具有较低（或等于）优先级的运营商。 在这个例子的背景下，这就是你想要做的事情：
你如何实现这个？
你希望有两个堆栈，一个用于数字，另一个用于操作员。 您一直将数字推入堆栈。 您将每个新操作符与堆栈顶部的操作符进行比较，如果堆栈顶部的操作符具有更高优先级，则将其从操作堆栈弹出，将操作数从数字堆栈中弹出，应用操作员并推送结果到数字堆栈上。 现在您重复与堆栈运算符顶部的比较。
回到这个例子，它的工作原理是这样的：
N = [] Ops = []
* 。 N = [1 2]，Ops = [+ *] * 3，并将结果推送到N. N = [1 6]，Ops = [+] +是左结合的，所以你也想弹出1,6，并执行+。 N = [7]，Ops = []。 在那里，这并不困难，是吗？ 它不会调用任何语法或解析器生成器。
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
很好的解释不同的方法：
用简单的语言和伪代码编写。
我喜欢'优先攀登'之一。
链接地址: http://www.djcxy.com/p/66543.html