会享福的破狗# pets - 心有所宠
d*w
1 楼
infix expression to prefix expression.
eg:
3 * x + ( 9 + y ) / 4 ->
(+ (* 3 x) (/ (+ 9 y) 4))
参考了网上的一个递归写法，总体挺简洁的，这个复杂度是多少, 有没有O(N)的解法么？
＃reduce 用来标注是否能计算数值
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
eg:
3 * x + ( 9 + y ) / 4 ->
(+ (* 3 x) (/ (+ 9 y) 4))
参考了网上的一个递归写法，总体挺简洁的，这个复杂度是多少, 有没有O(N)的解法么？
＃reduce 用来标注是否能计算数值
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
