By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,908 Members | 1,860 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,908 IT Pros & Developers. It's quick & easy.

S-exression parsing

P: n/a
The S-expression parser below works, but I wonder if it can be simplified; it's not as short and
straightforward as I would expect given the simplicity of S-expressions. Can you see a simpler
non-recursive solution ?

George

# usage
parseSexpression("(a (b c) (d))") ['a', ['b', 'c'], ['d']] parseSexpression("(a (b c)) (d))") ValueError: Unbalanced right parenthesis: (a (b c)) (d)) parseSexpression("(a ((b c) (d))") ValueError: Unbalanced left parenthesis: (a ((b c) (d)) parseSexpression("(a (b c)) (d)") ValueError: Single s-expression expected (2 given) parseSexpression("(a (b c)) e")

ValueError: Unenclosed subexpression (near e)
def parseSexpression(expression):
subexpressions,stack = [],[]
for token in re.split(r'([()])|\s+', expression):
if token == '(':
new = []
if stack:
stack[-1].append(new)
else:
subexpressions.append(new)
stack.append(new)
elif token == ')':
try: stack.pop()
except IndexError:
raise ValueError("Unbalanced right parenthesis: %s" % expression)
elif token:
try: stack[-1].append(token)
except IndexError:
raise ValueError("Unenclosed subexpression (near %s)" % token)
if stack:
raise ValueError("Unbalanced left parenthesis: %s" % expression)
if len(subexpressions) > 1:
raise ValueError("Single s-expression expected (%d given)" % len(subexpressions))
return subexpressions[0]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Haiku of the day:

"The Web site you seek / Can not be located but / Countless more exist. "
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jul 18 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
George Sakkis wrote:
The S-expression parser below works, but I wonder if it can be simplified; it's not as short and
straightforward as I would expect given the simplicity of S-expressions. Can you see a simpler
non-recursive solution ?


How about this (minus your error checking)?

def parseS(expression):
stack = []
stacks = []
for token in re.split(r'([()])|\s+', expression):
print stack
if token == '(':
stacks.append(stack)
stack = []
elif token == ')':
stacks[-1].append(stack)
stack = stacks.pop()
elif token:
stack.append(token)
return stack[0]

Michael

Jul 18 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.