存储和评估嵌套字符串元素

Question

给定一个字符串 exampleString = "[9+[7*3+[1+2]]-5]"，我们该如何提取并存储被方括号 [] 包围的元素，然后按顺序计算它们呢？

1+2 --+
      |
  7*3+3 --+
          |
        9+24-5

是不是需要创建某种嵌套列表？抱歉这个问题有点 宽泛，英语也不太好。

我明白了，这个问题确实太宽泛了……有没有办法从这个字符串创建一个嵌套列表？或者我是不是应该简单地用正则表达式搜索每个元素，然后逐个计算？如果有嵌套列表的选项，我觉得这会比不断循环同一个字符串并计算直到没有方括号要“干净”一些。

Answer 1

一个不错的起点是“调度算法”。

网上有很多Python的实现，下面是其中一个。

这个算法可以用来把中缀表达式转换成多种不同的表示方式。如果你对使用哪种表示方式没有限制，我建议你考虑逆波兰表示法，因为它比较好用。

Answer 2

你可以看看 pyparsing 这个模块，还有他们的一些例子（四函数计算器 是你可能需要的，还有更多的功能）。

另外，如果你觉得代码的大小让你担心，可以再看看：大部分内容其实可以删掉。下面的部分只是一些测试代码。上面的部分可以去掉一些支持常数（比如 e、π 等）和三角函数的内容。我相信你可以把它简化到只需要10行代码就能实现你想要的功能。

Answer 3

这里有一个正则表达式的解决方案：

import re

def evaluatesimple(s):
  return eval(s)

def evaluate(s):
  while 1:
    simplesums=re.findall("\[([^\]\[]*)\]",s)
    if (len(simplesums) == 0):
      break
    replacements=[('[%s]' % item,str(evaluatesimple(item))) for item in simplesums]
    for r in replacements:
      s = s.replace(*r)
  return s

print evaluate("[9+[7*3+[1+2]]-5]")

不过，如果你想更彻底一点，构建一个树形结构来后续评估，你可以使用相同的技巧，但把表达式和子表达式存储在一个字典里：

def tokengen():
  for c in 'abcdefghijklmnopqrstuvwyxz':
    yield c

def makeexpressiontree(s):
  d=dict()
  tokens = tokengen()
  while 1:
    simplesums=re.findall("\[([^\]\[]*)\]",s)
    if (len(simplesums) == 0):
      break
    for item in simplesums:
      t = tokens.next()
      d[t] = item
      s = s.replace("[%s]"% item,t)
  return d

def evaltree(d):
  """A simple dumb way to show in principle how to evaluate the tree"""
  result=0
  ev={}
  for i,t in zip(range(len(d)),tokengen()):
    ev[t] = eval(d[t],ev)
    result = ev[t]
  return result

s="[9+[7*3+[1+2]]-5]"
print evaluate(s)
tree=makeexpressiontree(s)
print tree
print evaltree(tree)

(编辑以扩展我的回答)