我使用简单的堆栈算法开发了一个方程解析器,它将处理二进制(+, - ,|,&,*,/等)运算符,一元(!)运算符和括号.
但是,使用这种方法会让我拥有相同优先级的所有内容 - 无论操作符如何,都会从左到右进行评估,尽管可以使用括号强制执行优先级.
所以现在"1 + 11*5"会返回60,而不是人们所期望的56.
虽然这适用于当前项目,但我希望有一个通用例程,我可以用于以后的项目.
编辑清晰:
解析具有优先级的方程的好算法是什么？
我对一些简单的实现感兴趣,并且理解我可以自己编写代码来避免使用可用代码的许可问题.
语法:
我不明白语法问题 - 我是手写的.这很简单,我认为不需要YACC或Bison.我只需要用诸如"2 + 3*(42/13)"之类的方程计算字符串.
语言:
我在C中这样做,但我对算法感兴趣,而不是语言特定的解决方案.C足够低,如果需要,很容易转换成另一种语言.
代码示例
我发布了上面讨论的简单表达式解析器的测试代码.项目要求发生了变化,因此我从不需要优化性能或空间代码,因为它没有包含在项目中.它是原始的详细形式,应该易于理解.如果我在运算符优先级方面做了更多的事情,我可能会选择宏hack,因为它简单地匹配程序的其余部分.但是,如果我在一个真实的项目中使用它,我将寻求一个更紧凑/更快速的解析器.
相关问题
-亚当
如果我有一个数学方程式的字符串,我想拆分然后计算它.我知道我可以使用eval()函数来做到这一点,但我很感兴趣,如果有另一种方法可以做到这一点 - 特别是首先拆分字符串.所以我有类似的东西
var myString = "225 + 15 - 10"
var newString = myString.split(" ");
这会将myString变成一个数组:["225","+","15"," - ","10"];
我的下一个任务是将所有奇数编号的字符串转换为整数,我认为我可以使用parseInt(); 对于.我的问题是,如何将"+"和" - "转换为实际的算术运算符？所以最后我留下了一个我可以计算的数学表达式？
这可能吗？
让我们说我有一个方法声明这样:
public double Calc(String expression) {
// Code
}
我想采用像String这样的String表达式
"2 + 4 - (3 * 4)"
然后将其提供给它Calc(),它应该返回它获得的值.
你能从字符串中解析数学表达式,以便它成为Java可以理解的表达式吗？因为通常你可以写
return 2 + 4 - (3 * 4);
但这只适用于那个单一的表达.
受最近TED演讲的启发,我想写一小段教育软件.研究人员制作了一些名为" Siftables "的小型微型计算机.
替代文字http://images.ted.com/images/ted/tedindex/embed-posters/DavidMerrill-2009.embed_thumbnail.jpg
[David Merril, inventor - with Siftables in the background.]
他使用了很多块应用程序,但我最喜欢的是每个块都是数字或基本操作符号.然后,您可以在一行中重新排列数字块或操作符号,它将在另一个可筛选块上显示答案.
alt text http://i44.tinypic.com/m7us6g.png
所以,我已经决定要在有限的范围内实施一个软件版本的"数学Siftables"作为我正在参加的CS课程的最终项目.
解析和解释一串数学表达式的普遍接受的方法是什么,如果它们有效,执行操作？
这是我应该实现完整解析器/词法分析器的情况吗？我认为解释基本的数学表达式将是计算机科学中的一个半常见问题,所以我正在寻找正确的方法来解决这个问题.
例如,如果我的Math Siftable块在哪里排列如下:
[1][+][2]
这将是一个有效的序列,我将执行必要的操作以达到"3".
但是,如果孩子要将几个操作块拖到一起,例如:
[2][\][\][5]
这显然是无效的.
最终,我希望能够使用用户可以拖动的块来解析和解释任意数量的操作链.任何人都可以向我解释或指向我解析基本数学表达式的资源吗？
我更喜欢尽可能多的语言不可知的答案.
