f********x
发帖数: 2086 | 1 比如
String str = "1 + 2 * 3 /4"
输出2.5
我的思路是
两个队列
一个存数字
一个存运算符号
遍历放入队列，如果有* /，则计算完了* / 结果再放入队列
然后通过两个队列计算
但是如果有括号就不知道怎么搞了 |
f**********3
发帖数: 295 | 2 典型的parse，要建Abstract syntac tree （AST）， 树结构，然后每个节点evaluate
左边，eveluate右边，最后apply operator
这个例子的AST：
+
/\
1 /
/\
* 4
/\
2 3
【在 f********x 的大作中提到】
: 比如
: String str = "1 + 2 * 3 /4"
: 输出2.5
: 我的思路是
: 两个队列
: 一个存数字
: 一个存运算符号
: 遍历放入队列，如果有* /，则计算完了* / 结果再放入队列
: 然后通过两个队列计算
: 但是如果有括号就不知道怎么搞了
|
v**********m
发帖数: 5516 | 3 import javax.script.ScriptEngineManager;
import javax.script.ScriptEngine;
public class TestOfStringToMath {
public static void main(String[] args) throws Exception{
ScriptEngineManager mgr = new ScriptEngineManager();
ScriptEngine engine = mgr.getEngineByName("JavaScript");
String foo = "1 + 2 * 3 /4";
System.out.println(engine.eval(foo));
}
}
google到的，编译通过。
With JDK1.6, you can use the built-in Javascript engine.
http://stackoverflow.com/questions/3422673/evaluating-a-math-ex
【在 f********x 的大作中提到】
: 比如
: String str = "1 + 2 * 3 /4"
: 输出2.5
: 我的思路是
: 两个队列
: 一个存数字
: 一个存运算符号
: 遍历放入队列，如果有* /，则计算完了* / 结果再放入队列
: 然后通过两个队列计算
: 但是如果有括号就不知道怎么搞了
|
s***e
发帖数: 403 | 4 可以参考任何一本数据结构书。
表达式求值的常用方法是用堆栈解决。一个operand栈一个operator栈。 |
f**********3
发帖数: 295 | 5 这个像是cheating，不过要看出题人要求了
【在 v**********m 的大作中提到】
: import javax.script.ScriptEngineManager;
: import javax.script.ScriptEngine;
: public class TestOfStringToMath {
: public static void main(String[] args) throws Exception{
: ScriptEngineManager mgr = new ScriptEngineManager();
: ScriptEngine engine = mgr.getEngineByName("JavaScript");
: String foo = "1 + 2 * 3 /4";
: System.out.println(engine.eval(foo));
: }
: }
|
v**********m
发帖数: 5516 | 6 那只能用你二楼的那个思路了。
【在 f**********3 的大作中提到】
: 这个像是cheating，不过要看出题人要求了
|
f********x
发帖数: 2086 | 7
evaluate
Thanks!
那括号的话就是括号内的生成树就行了
【在 f**********3 的大作中提到】
: 典型的parse，要建Abstract syntac tree （AST）， 树结构，然后每个节点evaluate
: 左边，eveluate右边，最后apply operator
: 这个例子的AST：
: +
: /\
: 1 /
: /\
: * 4
: /\
: 2 3
|
s********u
发帖数: 1109 | 8 没有括号的话，用longway大神发过的方法。有括号的话，可以先转换成后缀。 |
n****e
发帖数: 678 | 9 能贴下“longway大神发过的方法”吗？ 多谢！
【在 s********u 的大作中提到】
: 没有括号的话，用longway大神发过的方法。有括号的话，可以先转换成后缀。
|
o*********r
发帖数: 203 | 10 You need to:
1) convert it into post-fix expression by using stack, which will eliminate
any brackets ( ).
2) compute result using stack.
There are many resources available online about 'Infix to postfix expression
' algorithm.
|
f********x
发帖数: 2086 | 11
eliminate
expression
Thanks!
【在 o*********r 的大作中提到】
: You need to:
: 1) convert it into post-fix expression by using stack, which will eliminate
: any brackets ( ).
: 2) compute result using stack.
: There are many resources available online about 'Infix to postfix expression
: ' algorithm.
:
|
l*n
发帖数: 529 | 12 可以用recursion，找到第一个乘法，用计算结果替代原算式，如此继续。
有括号的话，可以先找最右边的左括号，并用计算结果替代原算式。
当然，这种解法是比较naive的，真的应用实现还得上逆波兰式。
【在 f********x 的大作中提到】
: 比如
: String str = "1 + 2 * 3 /4"
: 输出2.5
: 我的思路是
: 两个队列
: 一个存数字
: 一个存运算符号
: 遍历放入队列，如果有* /，则计算完了* / 结果再放入队列
: 然后通过两个队列计算
: 但是如果有括号就不知道怎么搞了
|
