python split and evaluate

Question

How might I split a string (with postfix) into one with parentheses? What I mean is, if the user inputs 3 (3 6 *) * I want the interpreter to be able to multiply 3 18 * and understand the parentheses in the text. Is this possible? Like a str.split() but with a start and end delimiter?

Am I not being realistic? I found the shlex module similar, but it only does quotes AFAIK.

Answer 1

I don't think using re is such a bad idea. You could just go through replacing the nested parenthesis one at a time with the result of their operation. Seems pretty straight forward to me:

import re
regex = re.compile(r'\([^\(\)]+\)')

def eval_expr(expr):
    match = regex.search(expr)
    if match:
        sub_expr = match.group()
        return eval_expr(expr.replace(sub_expr, str(eval_expr(sub_expr[1:-1]))))
    args = expr.split()
    op = args.pop()
    return eval(op.join(args))

And use like so:

>>> eval_expr('(1 (2 3 -) 4 +) (5 6 *) 7 +')
<<< 41

Answer 2

I'm not very familiar with regular expressions. Would it be too much to ask to ask for an example for this one?

As Chris's, uh, variegated comments indicated, you can't have an (true) regular expression that will parse nested parentheses. (According to him, there are some sort of hacks and extensions that would broaden the expression-language to let it parse context-free grammars. This is the first I've heard of that, but it sounds like a bad idea to me.)

This answer also seems to have downvotes...Are there any other ways to do this?

Read this.

Answer 3

You could write a regular expression to extract parenthesized subexpressions. re.split may be helpful if what you care about is splitting on matched parentheses. A straightforward regular expression would let you pick out the subexpressions.

#!/usr/bin/env python
import re
source = r"3 (3 6 *) *"
rewritten = source[:]
match_index = 1
snag_deepest = re.compile(r"""(?P<pre>.*)(?P<sub>\([^()]+\))(?P<post>.*)""")

print "Starting -> %s" % (rewritten)
results = snag_deepest.search(rewritten)
while results is not None:
    print "Subexpression %d -> %s" % (match_index, results.group('sub'))
    rewritten = "%s%s%s" % (results.group('pre'), "sub_%d" % match_index, results.group('post'))
    print "Rewritten as -> %s" % (rewritten)
    results = snag_deepest.search(rewritten)
    match_index += 1

produces

Starting -> 3 (3 6 *) *
Subexpression 1 -> (3 6 *)
Rewritten as -> 3 sub_1 *

Answer 4

First, understand that parenthesis are not necessary in postfix notation when the arity of an operator is known. To see why:

3 3 6 * *

Starting from the left, stack operands until you encounter an operator:

operands <- 3 <- 3 <- 6
operator: *

We know that * is a binary operator, so pop two operands off the stack, apply the operator, and push the result back on:

operands -> 3 -> 6
operands <- 18

Continue to accumulate operands until you encounter another operator:

operator: *
operands -> 3 -> 18
operands <- 54

When the expression is consumed (assuming it's well-formed) the stack will contain one value: the result.

But your question is about parenthesis: assuming that your desire is to be able to parse arbitrarily nested parentheses, regular expressions will not help you, for reasons explained here. You need something that can recognize a context free grammar, i.e. a pushdown automaton.

But you're looking, I take it, for something more than abstract computer science-speak; here's a related question that has some useful information on the Shunting Yard Algorithm, which converts parenthesized infix expressions into postfix expressions.

Edit: Ok, I should have said "true regular expressions alone will not help you." You could use regular expressions (matching innermost pairs of parenthesis) and substitution to (in effect) treat a parenthesized expression as its own implicit parse tree. But the Shunting Yard Algorithm is cooler :)

Answer 5

Correct me if i am wrong but your expression is the RPD. If so there is no actual need to use parenthesis. Please find my sample(not optimized and weird) below:

import operator

def rpd_eval(expression):
    if expression.count('(') != expression.count(')'):
        return 0    
    expression = expression.replace(' ', '')
    ops = {'*': operator.mul, '**': operator.pow, '%': operator.mod,
           '+': operator.add, '-': operator.sub, '/': operator.div,
           '^': operator.pow}        
    res = []
    for v in list(expression):
        if not v in ops and v not in ['(',')']:
            res.append(int(v))
        elif v not in ['(',')']:
            b = float(res.pop())
            a = float(res.pop())
            res.append(ops[v](a, b))
    return res[0]

print rpd_eval('3(63*)*5+') # will print 59