Parsing program input string for math expression

Question

I'm trying to program a worlfram alpha like math expression solver. My current obstacle is figuring out which opening and closing brackets are corresponding.

For example, how would I figure out which brackets in ((1 * 3) / (4 / 2)) are matching. The program will solve each of these sections individually, and when doing so replacing the section in the original with the answer.

So, for example, the first section the program would try to solve in ((1 * 3) / (4 / 2)) would be (1 * 3), so it would replace that section with the product, 3, and ((1 * 3) / (4 / 2)) would now be (3 / (4 / 2)).

My current code, if helpful is here - http://pastebin.com/Xpayzbff, the function that is handling the paring is parse().

Thanks!

Edit (7/3/2019): For anyone attempting a similar project, I did eventually figure this out soon after asking. For the purpose of being helpful, here is my source code - https://github.com/j-osephlong/python-arithmetic

Answer 1

I'm not gonna write code for you, because that would defeat the point, but what you probably want is the Shunting-yard algorithm. It converts from infix (how humans normally represent series of operations, with the operator in the operands) into postfix(which is easy for a computer to evaluate, with the operator after the operands).

Here is someone who did it for boolean login in python: https://msoulier.wordpress.com/2009/08/01/dijkstras-shunting-yard-algorithm-in-python/

You could also try parsing the statement directly into an AST, which you could then manipulate.

Also make sure to check out the tokenizer module for python.

Answer 2

You can use the Shunting-Yard algorithm. However, a complete implementation of the algorithm is pretty involved. Here is simpler, somewhat naive version that could give you a basic understanding https://gist.github.com/tiabas/339f5c06f541c176a02c02cc3113d6f7

# Simple Shunting-Yard solution
#
# Given a math expression, parse and evaluate
# the expression
#
# E.g '2+1' => 3, 8/2*4+1 => 17, 2+(1*2) = 4, ((2+4)/2*7) => 21
# 
def parse_math_expression(exp):
    PRECENDENCE = {
        ')': 3,
        '(': 3,
        '*': 1,
        '/': 1,
        '+': 0,
        '-': 0,
    }
    output = []
    operators = []
    for ch in exp:
        # Handle nested expressions
        if ch == ')':
            opr = operators.pop(0)
            while opr != '(':
                output.append(opr)
                opr = operators.pop(0)
        elif ch.isdigit():
            output.append(ch)
        else:
            # Handle operator prescendence
            top_op = None
            if len(operators) and operators[0]:
                top_op = operators[0]
            # Check if top operator has greater prcendencethan current char
            if top_op in ['*', '/'] and PRECENDENCE[top_op] > PRECENDENCE[ch]:
                output.append(top_op)
                operators.pop(0)
            # Push operator onto queues
            operators.insert(0, ch)
    # Handle any leftover operators
    while len(operators):
        output.append(operators.pop(0))
    return output

test1 = "(2+1)"
assert parse_math_expression(test1) == ['2', '1', '+']
test2 = "((2+4)/(2*7))"
assert parse_math_expression(test2) == ['2', '4', '+', '2', '7', '*', '/']
test3 = "(3*2)+(4/2)"
assert parse_math_expression(test3) == ['3', '2', '*','4', '2', '/','+']

def eval_parsed_expression(exp):
    OPRS = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: a / b
    }
    tmp = []
    while len(exp) > 1:
        k = exp.pop(0)
        while not k in ['*', '-', '+', '/']:
            tmp.insert(0, k)
            k = exp.pop(0)
        o = k
        b = tmp.pop(0)
        a = tmp.pop(0)
        r = OPRS[o](int(a), int(b))
        exp.insert(0, r)
    return exp[0]

test4 = ['2', '1', '+'] # (2+1*2)
assert eval_parsed_expression(test4) == 3
test5 = ['2', '1', '2', '*', '+'] # (2+1*2)
assert eval_parsed_expression(test5) == 4
test6 = ['3', '2', '*','4', '2', '/','+'] # (3*2)+(4/2)
assert eval_parsed_expression(test6) == 8

Answer 3

Treat an expression between brackets as a list of symbols which can also contain another list. So "((1 * 3) / (4 / 2))" is represented by [['1', '*', '3'], '/', ['4', '/' '2']]. Call a list of symbols a ‘node’.

As you iterate the string, maintain a stack, which keeps track of the ‘bracket pair’ (or node) that you’re in. Append symbols to the last node in the stack (current_node). At each '(', add a new node to the node you’re in, and to the stack. At each ')', pop the stack, so that you’re in the parent node, and further symbols will be appended there.

Then you can recursively evaluate each node, inside first, until you have a final value.

Reverse engineer this code.

def parse(expr):
    stack = [[]]
    for i in expr:
        current_node = stack[-1]
        if i == '(':
            new_node = []
            current_node.append(new_node)
            stack.append(new_node)
        elif i == ')':
            stack.pop()
        elif not i.isspace():
            current_node.append(i)

    return stack[0]

print(parse('(1 * 3) / (4 / 2)')) # [['1', '*', '3'], '/', ['4', '/', '2']]

---

Check out this question: Python parsing bracketed blocks