关于数学表达式解析和求值 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于数学表达式解析和求值

关于数学表达式解析和求值# JobHunting - 待字闺中

d*w2012-02-29 08:02

1 楼

这题都连续被apple,facebook问道了，想跟大家探讨一些解决方法。
题目如下，简单的就是四则运算
如：
(2+3)*10-1 =
复杂的是带变量的
r*r - 1/4*pi * r^2
可能的话化简，然后给出变量值
r = 2
pi = 3.14
求最后表达式的值
这里面分2步，一个是parse(String str); 一个是evaluate();
parse编译原理课上是讲过，定义一些term grammer
expression = sum
sum = sum +/- term
| term
term = term *// element
element = constant
| "(" expression ")"
但我发现写出来还是蛮麻烦的，有人说expression tree,如何构造这个tree也是个问题

H*e2012-02-29 08:02

2 楼

有系统的方法的。
先把in的转化为post,然后evaluate postfix
都是用stack实现的

【在 d********w 的大作中提到】

: 这题都连续被apple,facebook问道了，想跟大家探讨一些解决方法。
: 题目如下，简单的就是四则运算
: 如：
: (2+3)*10-1 =
: 复杂的是带变量的
: r*r - 1/4*pi * r^2
: 可能的话化简，然后给出变量值
: r = 2
: pi = 3.14
: 求最后表达式的值

d*w2012-02-29 08:02

3 楼

是有些印象，不过具体怎么做呢，给个link？

【在 H***e 的大作中提到】

: 有系统的方法的。
: 先把in的转化为post,然后evaluate postfix
: 都是用stack实现的

x*p2012-02-29 08:02

4 楼

A good way is to use recursive algorithm or Translate pattern.
First, remove () in pairs
Second, remove operators according to the order +, -, *, /
Finally, calculate the last expression, either in letters or converting to
numbers.

d*w2012-02-29 08:02

5 楼

找到一个把中序转前序的题
http://www.justin.tv/problems/prefixer
当时还写过python版的
def parse(s, reduce):
for operator in ["+-", "*/"]:
depth = 0
for p in xrange(len(s) - 1, -1, -1):
if s[p] == ')': depth += 1
if s[p] == '(': depth -= 1
if not depth and s[p] in operator:
left = parse(s[:p], reduce)
right = parse(s[p+1:], reduce)
if reduce and left.isdigit() and right.isdigit():
return str(eval(left + s[p] + right))
return '(' + ' '.join([s[p], left, right]) + ')'
s = s.strip()
if s[0] == '(':
return parse(s[1:-1], reduce)
return s

【在 x*****p 的大作中提到】

: A good way is to use recursive algorithm or Translate pattern.
: First, remove () in pairs
: Second, remove operators according to the order +, -, *, /
: Finally, calculate the last expression, either in letters or converting to
: numbers.

n*02012-02-29 08:02

6 楼

简单四则运算
public static double cal(String s) {
int lastpos = -1;
char lastOps = ' ';
int rightBracket = 0;
for (int i = s.length() - 1; i >= 0; i--) {
switch (s.charAt(i)) {
case ')':
rightBracket++;
break;
case '(':
rightBracket--;
break;
}
if (rightBracket > 0)
continue;
switch (s.charAt(i)) {
case '+':
return cal(s.substring(0, i).trim())
+ cal(s.substring(i + 1, s.length()).trim());
case '-':
return cal(s.substring(0, i).trim())
- cal(s.substring(i + 1, s.length()).trim());
case '*':
if (lastpos < 0) {
lastpos = i;
lastOps = '*';
}
break;
case '/':
if (lastpos < 0) {
lastpos = i;
lastOps = '/';
}
break;
}
}
if (lastOps == '*') {
return cal(s.substring(0, lastpos))
* cal(s.substring(lastpos + 1, s.length()));
}
if (lastOps == '/') {
return cal(s.substring(0, lastpos))
/ cal(s.substring(lastpos + 1, s.length()));
}
if (s.charAt(0) == '(' && s.charAt(s.length() - 1) == ')')
return cal(s.substring(1, s.length() - 1));
return Double.parseDouble(s);
}
}

【在 d********w 的大作中提到】