java - 计算 N 变量多项式字符串

Question

我需要计算一个 n 变量多项式字符串

str = "-3a^5b^2c^3 + 12bc + xy + yz + xyz + 123"; .

变量值 input = "a=-2,b=-1,c=1,x=2,x=3,z=4";

到目前为止我能做的事情:

1.) 打破str分成单独的术语，例如 "-3a^5b^2c^3" , "12bc" , "xy" , "yz" , "xyz"如下:

String[] terms = poly.split("-|\\+");

第 1 步之后:

terms[] = {"-3a^5b^2c^3", "12abc", "xy", "yz", "xyz"};

2.) 从 input 中提取变量值如下:

String[] parts = input.split(",");
String[] variables = new String[parts.length];

// Getting inputs
for (int i = 0; i < parts.length; i++)
{
    String s = parts[i].substring(parts[i].indexOf('=')+1);
    variables[i] = s;
}

第 2 步之后:

variables[] = {-2, -1, 1, 2, 3, 4};

我计划评估 terms[] 的各个条款数组并相应地添加/减去它们。但我该怎么分手"-3a^5b^2c^3"进入3 , a^5 , b^2 , c^2 ？

手动执行会消耗太多代码行和时间，并且会使代码看起来很复杂。

我是 Java 和正则表达式的新手，无法通过正则表达式找到其解决方案。

Answer 1

您可以通过三个步骤解决此问题:

1. 识别变量、数字和运算符并将它们添加到列表中。使用类可能会让以后更容易获得优先级和关联性。

2. 然后使用 Shunting-yard 算法对表达式重新排序 http://en.wikipedia.org/wiki/Shunting-yard_algorithm .

3. 最后，表达式将采用逆波兰表示法，并且计算表达式 http://en.wikipedia.org/wiki/Reverse_Polish_Notation 相当容易。 .

自从您寻求有关正则表达式的帮助以来，我完成了第一步。我只是为每个元素添加了一个字符串，以保持代码和结果简单。如何更改代码以将类对象而不是字符串添加到列表中应该是显而易见的。

from re import match

def toList(expr):
    print '\n> toList(%s)' % expr
    result = []
    index = 0
    expectsOp = False
    while index < len(expr):
        if expectsOp:
            next = match(r'(?P<Skip> +)|(?P<Operator>[-+*/^])', expr[index:])
            if next:
                if next.group('Operator'):
                    result.append('Op:%s' % next.group('Operator'))
                    index += len(next.group('Operator'))
                elif next.group('Skip'):
                    index += len(next.group('Skip'))
                    continue
            else:
                result.append('Op:*')
            expectsOp = False
        else:
            next = match(r'(?P<Skip> +)|(?P<Number>[-+]?\d+)|(?P<Variable>[A-Za-z])', expr[index:])
            if next:
                if next.group('Number'):
                    result.append('Num:%s' % next.group('Number'))
                    index += len(next.group('Number'))
                elif next.group('Variable'):
                    result.append('Var:%s' % next.group('Variable'))
                    index += len(next.group('Variable'))
                elif next.group('Skip'):
                    index += len(next.group('Skip'))
                    continue
            else:
                return 'Error: Expected variable or number, but found "...%s"' % expr[index:]
            expectsOp = True

    return result

print toList("-3a^5b^2c^3 + 12bc + xy + yz + xyz + 123")

产生结果:

> toList(-3a^5b^2c^3 + 12bc + xy + yz + xyz + 123)
['Num:-3', 'Op:*', 'Var:a', 'Op:^', 'Num:5', 'Op:*', 'Var:b', 'Op:^', 'Num:2', 'Op:*', 'Var:c', 'Op:^', 'Num:3', 'Op:+', 'Num:12', 'Op:*', 'Var:b', 'Op:*', 'Var:c', 'Op:+', 'Var:x', 'Op:*', 'Var:y', 'Op:+', 'Var:y', 'Op:*', 'Var:z', 'Op:+', 'Var:x', 'Op:*', 'Var:y', 'Op:*', 'Var:z', 'Op:+', 'Num:123']

编辑:抱歉，我刚刚注意到您使用 Java 而不是 Python。不过原理应该是相同的，所以只需将其视为伪代码即可。