在不使用多个函数的情况下使用 python 计算数学表达式的算法

Question

我正在尝试使用 python 中的堆栈计算中缀表达式。

我想知道我下面是否有以下中缀表达式：

'2 ^ ( 1 + 3 ^ 2 )'
'( 3 * 5 ) - ( 1 > 2 > 3 < 4 )'
'4 ^ ( 10 < 2 ) / 5 + 100'

我将如何继续使用 2 个堆栈来评估它而不调用多个其他函数，以便输出将是：

1024
12
103

我只是想知道执行此操作的算法是什么。我知道标准方法是将中缀更改为后缀然后求解，但是有没有一种更快的方法可以在一个函数中执行此操作。非常感谢。

Answer 1

您可能想要搜索 "shunting yard algorithm"。这是一个非常基本的表达式评估算法，它使用两个堆栈（尽管一个称为 'output queue'）。

基本上，您从运算符中过滤数字。数字进入输出堆栈，运算符进入 "holding" 堆栈。当一个运算符的优先级低于保持堆栈上的运算符时，将保持堆栈的内容移动到输出堆栈，直到保持堆栈为空，或者保持堆栈上的项目的优先级低于输入运算符.

优先级

请记住，a + b * c - d 的计算结果为 (a + (b*c)) - d。还请记住，求幂比乘法具有更高的优先级，因此 a * b ^ c 将成为 a * (b ^ c)。

编辑：

这是一些不起作用的代码。我不知道您的运算符“>”和“<”是什么。显然 (10 < 2) 应该是 2，从第三个表达式？

我只是将它们实现为 C-style 布尔值（1 表示真，0 表示假）。

里面有一堆冗余代码，因为只有一个函数。随时清理它。它修改调车场算法以动态执行 RPN 计算。我留下了一堆打印语句，这些语句说明了我用作堆栈的列表的内容。随意用你的堆栈做适当的工作类。在我的版本中，pop() 是 pop，append() 是 push。

tests = [
    '2 ^ ( 1 + 3 ^ 2 )',
    '( 3 * 5 ) - ( 1 > 2 > 3 < 4 )',
    '4 ^ ( 10 < 2 ) / 5 + 100',
]

expected = [
    1024,
    12,
    103,
]

def expr_eval(s):
    print("EXPR:", s)
    tokens = s.split()
    output_stk = []
    operator_stk = []

    precedence = {
        '(': 0,
        '+':1, '-':1, '<':1, '>':1,
        '*':2, '/':2,
        '^':3,
    }

    for t in tokens:
        print("OUT:", output_stk, "OP:", operator_stk)
        print("Tok: ",t)
        if t.isdigit():
            output_stk.append(int(t))
            continue
        elif t == '(':
            operator_stk.append(t)
            continue
        elif t == ')':
            # End of subexpression. Do math until we find opening (
            while operator_stk:
                op = operator_stk.pop()
                if op == '(':
                    break

                b = output_stk.pop()
                a = output_stk.pop()
                if op == '-': output_stk.append(a - b)
                elif op == '+': output_stk.append(a + b)
                elif op == '<': output_stk.append(1 if a < b else 0)
                elif op == '>': output_stk.append(1 if a > b else 0)
                elif op == '*': output_stk.append(a * b)
                elif op == '/': output_stk.append(a // b)
                elif op == '^': output_stk.append(a ** b)
                else:
                    raise Exception("Unknown operator: %s" % op)
                print("OUT:", output_stk, "OP:", operator_stk)
            continue

        # Not a number - check operator precedence
        prec_t = precedence[t]
        while operator_stk and prec_t <= precedence[operator_stk[-1]]:
            print("OUT:", output_stk, "OP:", operator_stk)
            op = operator_stk.pop()
            b = output_stk.pop()
            a = output_stk.pop() # 'a' went on first!
            if op == '-': output_stk.append(a - b)
            elif op == '+': output_stk.append(a + b)
            elif op == '<': output_stk.append(1 if a < b else 0)
            elif op == '>': output_stk.append(1 if a > b else 0)
            elif op == '*': output_stk.append(a * b)
            elif op == '/': output_stk.append(a // b)
            elif op == '^': output_stk.append(a ** b)
            else:
                raise Exception("Unknown operator: %s" % op)
        operator_stk.append(t)

    print("OUT:", output_stk, "OP:", operator_stk)

    while operator_stk:
        op = operator_stk.pop()
        if op == '(':
            raise Exception('Mismatched opening parenthesis!')

        b = output_stk.pop()
        a = output_stk.pop() # 'a' went on first!
        if op == '-':   output_stk.append(a - b)
        elif op == '+': output_stk.append(a + b)
        elif op == '<': output_stk.append(1 if a < b else 0)
        elif op == '>': output_stk.append(1 if a > b else 0)
        elif op == '*': output_stk.append(a * b)
        elif op == '/': output_stk.append(a // b)
        elif op == '^': output_stk.append(a ** b)
        else:
            raise Exception("Unknown operator: %s" % op)
        print("OUT:", output_stk, "OP:", operator_stk)

    return output_stk.pop()

for i in range(len(tests)):
    r = expr_eval(tests[i])
    if r == expected[i]:
        print("PASS: %d = %s" % (r, tests[i]))
    else:
        print("FAIL: %d != %d = %s" % (r, expected[i], tests[i]))

在不使用多个函数的情况下使用 python 计算数学表达式的算法

Algorithm for evaluating maths expressions using python without using multiple functions

python

class

infix-notation

postfix-notation

python-3.x