解析数学表达式的程序输入字符串

Question

我正在尝试编程一个worlfram alpha的数学表达式解算器。 我目前的障碍是弄清楚哪个左括号和右括号是对应的。在

例如，我如何找出((1 * 3) / (4 / 2))中哪些括号是匹配的。程序将分别求解这些部分中的每一部分，并在这样做时用答案替换原来的部分。在

例如，程序试图在((1 * 3) / (4 / 2))中求解的第一个部分将是(1 * 3)，因此它将用乘积3替换该部分，((1 * 3) / (4 / 2))现在将是(3 / (4 / 2))。在

我当前的代码，如果有帮助的话，这里-http://pastebin.com/Xpayzbff，那么处理这个配对的函数是parse()。在

谢谢！在

编辑（7/3/2019）： 对于任何一个尝试类似项目的人来说，我在询问之后很快就发现了这一点。为了提供帮助，这里是我的源代码-https://github.com/j-osephlong/python-arithmetic

Answer 1

您可以使用Shunting-Yard算法。然而，算法的完整实现是相当复杂的。这里有一个更简单，有点天真的版本，它可以给你一个基本的理解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 2

我不打算为您编写代码，因为这会破坏要点，但您可能想要的是Shunting-yard algorithm。它从中缀（人类通常是如何表示一系列操作的，运算符在中）转换为后缀（计算机很容易计算，运算符在操作数之后）。在

下面是在python中为boolean登录而做的人：https://msoulier.wordpress.com/2009/08/01/dijkstras-shunting-yard-algorithm-in-python/

您还可以尝试将语句直接解析为AST，然后可以对其进行操作。在

另外，请确保查看python的tokenizer module。在

Answer 3

将括号之间的表达式视为符号列表，该列表也可以包含另一个列表。所以"((1 * 3) / (4 / 2))"由[['1', '*', '3'], '/', ['4', '/' '2']]表示。将符号列表称为“节点”。在

迭代字符串时，维护一个堆栈，它跟踪您所在的“括号对”（或节点）。将符号追加到堆栈中的最后一个节点（current_node）。在每个'('处，向您所在的节点添加一个新节点，和添加到堆栈中。在每个')'处，弹出堆栈，这样您就在父节点中，并且将在那里附加更多的符号。在

然后可以递归地计算每个节点，先在内部计算，直到得到最终值。在

对该代码进行反向工程。在

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']]

---

看看这个问题： Python parsing bracketed blocks