3

我需要评估一个 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("-|\\+");

Step1 之后：

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 和正则表达式的新手，无法通过正则表达式找到它的解决方案。

4

1 回答 1

0

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

  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。原理应该是一样的，所以只要把它想象成伪代码。

于 2013-08-30T04:15:24.130 回答