我已经开发了一种使用简单堆栈算法的方程式解析器，该算法将处理二进制（+，-，|，＆，*，/等）运算符，一元（！）运算符和括号。
但是，使用此方法会使我拥有所有具有相同优先级的内容-尽管可以使用括号强制执行优先级，但不管运算符如何，它都是从左到右进行求值的。
因此，现在“ 1 + 11 * 5”返回60，而不是人们期望的56。
虽然这适合当前项目，但我希望有一个通用例程，可以用于以后的项目。
为清楚起见进行了编辑：
解析具有优先级的方程的最佳算法是什么？
我对一些易于实现的东西感兴趣，并且了解我可以自己编写代码，以避免可用代码出现许可问题。
语法：
我不懂语法问题-我是用手写的。很简单，我认为不需要YACC或Bison。我只需要使用诸如“ 2 + 3 *（42/13）”之类的方程式来计算字符串。
语言：
我正在用C进行此操作，但是我对算法感兴趣，而不对特定于语言的解决方案感兴趣。C足够低，可以根据需要轻松转换为另一种语言。
代码示例
我在上面发布了简单表达式解析器的测试代码。项目需求发生了变化，因此由于性能或空间没有合并到项目中，因此我不需要优化代码。它采用原始的冗长形式，应该易于理解。如果我根据运算符优先级对其做任何进一步的处理，我可能会选择宏技巧，因为它可以简单地与程序的其余部分匹配。但是，如果我在真实的项目中使用过它，我将寻求一个更紧凑/更快速的解析器。
您需要递归下降解析器。
要获得优先权，您需要进行递归思考，例如，使用示例字符串，
1+11*5
要手动执行此操作，您必须先阅读1，然后查看加号并从…开始以全新的方式进行递归解析“会话”，11并确保将解析11 * 5为自己的因子，并生成带有的解析树1 + (11 * 5)。
1
11
11 * 5
1 + (11 * 5)
即使尝试解释，这一切都让人感到非常痛苦，尤其是在C变得更加无能为力的情况下。请参见，在解析11之后，如果*实际上是+，则必须放弃尝试创建术语并改为解析C的尝试。11本身就是一个因素。我的头已经爆炸了。递归的体面策略是可能的，但是有更好的方法…
如果您使用像Bison这样的GPL工具，那么您可能不必担心许可问题，因为bison生成的C代码未包含在GPL中（IANAL，但我敢肯定，GPL工具不会强制GPL在生成的代码/二进制文件；例如，Apple用GCC编译了诸如Aperture之类的代码，他们无需GPL所说的代码就可以出售它）。
下载Bison（或等效的工具，ANTLR等）。
通常有一些示例代码，您可以在其上运行bison并获得所需的C代码，以演示这四个功能的计算器：
http://www.gnu.org/software/bison/manual/html_node/Infix- Calc.html
查看生成的代码，发现这并不像听起来那样简单。同样，使用像Bison这样的工具的优点是：1）学到一些东西（特别是如果您阅读了Dragon书籍并学习了语法），2）避免了NIH尝试重新发明轮子。使用真正的解析器生成器工具，您实际上希望以后可以扩展，向其他人展示解析器是解析工具的领域。
更新：
这里的人们提供了很多合理的建议。我唯一不跳过解析工具或仅使用Shunting Yard算法或手推递归递归解析器的警告是，玩具语言1可能有一天会变成具有功能（正弦，余弦，对数）以及变量，条件和条件的大型实际语言。循环。
对于小型，简单的解释器而言，Flex / Bison可能会显得过大，但是当需要进行更改或添加功能时，脱离分析器+评估器可能会带来麻烦。您的情况会有所不同，您将需要运用自己的判断力；只是不要为自己的罪行惩罚别人 [2]并建立一个不够充分的工具。
我最喜欢的解析工具
世界上最好的工具是Parsec库（用于递归的体面解析器），该库随附了编程语言Haskell。它看起来很像BNF，或者像某种专用工具或领域特定的语言进行解析（示例代码[3]），但实际上它只是Haskell中的一个常规库，这意味着它与其余的编译步骤相同，您可以编写任意的Haskell代码并在解析器中调用它，也可以 在同一代码中 混合和匹配其他 所有 库。（顺便说一下，将这样的解析语言嵌入Haskell之外的语言中会导致大量的语法混乱。我在C＃中做到了这一点，并且效果很好，但不是那么简洁。）
笔记：
1 Richard Stallman在“ 为什么不应该使用Tcl”中说
Emacs的主要教训是扩展语言不应该仅仅是“扩展语言”。它应该是一种真正的编程语言，旨在编写和维护大量程序。因为人们会想要这样做！
[2]是的，使用该“语言”让我永远感到害怕。
还要注意，当我提交此条目时，预览是正确的，但是 SO不足以解析我在第一段中的紧密锚标签 ，证明解析器不是一件容易的事，因为如果您使用正则表达式和一些hacks， 那么您可能会出现一些细微的错误 。
[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
