Storing and evaluating nested string elements

Question

Given the exampleString = "[9+[7*3+[1+2]]-5]" How does one extract and store elements enclosed by [] brackets, and then evaluate them in order?

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

Does one have to create somekind of nested list? Sorry for this somewhat broad question and bad English.

I see, this question is really too broad... Is there a way to create a nested list from that string? Or maybe i should simply do regex search for every element and evaluate each? The nested list option (if it exists) would be a IMO "cleaner" approach than looping over same string and evaluating until theres no [] brackets.

If you don't need the intermediate values, a simple search/replace that turns brackets into parentheses, followed by an eval, would work fine. — Kenan Banks, Feb 06 '12 at 14:58
I see no significant problems with the English. (Insignificant problems include the lower-case proper noun and the question that doesn't end with a question mark.) I can't answer your question directly, but I suggest you search for *parsing tools*. (Python parsing tools, if you like, but your example isn't specific to Python.) — kojiro, Feb 06 '12 at 15:02
to do a quick evaluation you could simply do: `eval(exampleString.replace('[', '(').replace(']', ')'))` — juliomalegria, Feb 06 '12 at 15:05
It seems related to [Evaluating a mathematical expression in a string](http://stackoverflow.com/q/2371436/1132524). Take a look at [unutbu's answer](http://stackoverflow.com/a/2371789/1132524). — Rik Poggi, Feb 06 '12 at 15:10

viraptor · Answer 1 · 2012-02-06T15:23:14.103

3

Have a look at pyparsing module and some examples they have (four function calculator is something you want and more).

PS. In case the size of that code worries you, look again: most of this can be stripped. The lower half are just tests. The upper part can be stripped from things like supporting e/pi/... constants, trigonometric funcitons, etc. I'm sure you can cut it down to 10 lines for what you need.

edited Feb 06 '12 at 15:23

answered Feb 06 '12 at 15:02

viraptor

33,322
10
107
191

1

I'm going to second pyparsing, it's _exactly_ what you need to get started on this. What you want to write is not the parser, but the grammar for the (context-free) language. For me, and well worth the money, the getting started guide http://shop.oreilly.com/product/9780596514235.do was instrumental in getting started quickly. – Hooked Feb 06 '12 at 15:07
1

Looks like a lot of useful things can be found in [pyparsing](http://pyparsing.wikispaces.com/) module. That specific [four function calculator](http://pyparsing.wikispaces.com/file/view/fourFn.py) is quite useful for basic math expressions and a somewhat safer alternative to eval(). Also, the example displayed in [nested.py](http://pyparsing.wikispaces.com/file/view/nested.py) appears to convert nested tags to **nested list**. Thanks – Firebowl2000 Feb 06 '12 at 17:25

score 2 · Answer 2 · answered Feb 06 '12 at 15:00

A good starting point is the the shunting-yard algorithm.

There are multiple Python implementations available online; here is one.

The algorithm can be used to translate infix notation into a variety of representations. If you are not constrained with regards to which representation you can use, I'd recommend considering Reverse Polish notation as it's easy to work with.

Benedict · Accepted Answer · 2012-02-06T16:40:04.837

Here is a regex solution:

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]")

But if you want to go the whole hog and build a tree to evaluate later, you can use the same technique but store the expressions and sub expressions in a dict:

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)

(Edited to extend my answer)

Thanks, that'd be a useful straightforward code. I think this could be also the easiest way to approach in contrast to nested lists. — Firebowl2000, Feb 06 '12 at 17:09

Storing and evaluating nested string elements

3 Answers3