我正在搜索一些代数并尝试匹配以下形式的所有表达式:
(subexp)^C
其中 C 是一个整数，subexp 可以是以下两个之一:
a) 它可以是 (subexp)^C 形式的另一个表达式 b) 它可以是 var1 op var2 op var3 ... op varn 形式的表达式
其中 var 的形式为字母数字，例如 l2、cd3、hello53 等。 op 是 -、* 或 +。第二个选项也可以包含按括号分组的术语。
(没有空格，为了清楚起见，我只是在某些地方添加了空格)
举个例子:
(a12 + c33 + d34)^2
(a12 * c33 +-d34)^2
((a12 * c33)^5 + c3)^2
等等
这种形式的表达将被嵌入到一行文本中。我需要找到 (subexp)^C 的所有实例，并将它们替换为 pow(subexp, C)。简而言之，我正在尝试将一些计算机代数转换为可运行的 C 代码。
我最初是用正则表达式来做的，但后来意识到它不是正则表达式。对于非嵌套情况，正则表达式为:
line = re.sub(r'\(([a-zA-Z_]+[0-9]+\+?-?\*?)+\)\^[0-9]+', replace_with_pow, line)
这里的line是嵌入多项式的那一行，replace_with_pow是做替换的函数。
不幸的是，当表达式可以嵌套时，它就是一个 CFG。
我研究了 pyparsing，但发现示例很难解析，而且缺少文档。不过，这似乎是推荐的库。
任何人都可以提供一个示例脚本来说明如何查找嵌套表达式并替换它们吗？ (如果您希望我可以构建它，它可以用于简化问题)
编辑:更新:使用 pyparsing，我现在可以使用以下代码解析所有具有 { stuff ( ...)^C stuff } 形式的嵌套表达式:
closing = pyparsing.Word( ")^" + pyparsing.nums )
thecontent = pyparsing.Word(pyparsing.alphanums) | '+' | '-' | '*' | ','
parens = pyparsing.nestedExpr( '(', closing, content=thecontent)
thecontent2 = thecontent | parens
parens2 = pyparsing.nestedExpr('{', '}', content=thecontent2)
res = parens2.parseString("{sdf(a + (a + b)^5 + c)asdf}")
这让我想到了两个问题:
a) 当我匹配到我的 ^5 时，解析器将使用它。我怎样才能提取^5？ b) 是否有快速/简单的方法来使用 pyparsing 进行替换？
请您参考如下方法:
解决几乎所有解析问题的第一步都是对要解析的语法进行精确定义。如果该语法是上下文无关的，那么上下文无关语法是描述它的绝佳方式，通常比非正式描述或示例目录要好得多。
在这个问题中，你的例子
a12 * c33 +-d34
不符合描述
var op var op var ... op var
因为它有两个并排的op。在示例中
((a12 * c33)^5 + c3)^2
subexp (a12 * c33)^5 + c3 也不是 var op var；相反，它是 ( subexp ) op var。 (我知道，您的文字提到“术语可以用括号分组”，但没有提到“术语”实际上可以是一个 subexp 因为它可能是一个指数，如您的示例所示。 )
更精确的语法可能是(如果我猜对的话)，用“yacc”语法写成:
val : IDENTIFIER
| '(' expr ')'
term: val
| val '^' INTEGER
| '-' val
prod: term
| term '*' prod
expr: prod
| expr '+' prod
| expr '-' prod
以上不允许 --var、var^I1^I2 甚至 -var^I。从你的描述中我不知道你是否希望这些工作，但修改起来很容易。另外，我原以为数字文字是可以接受的，而不仅仅是变量，但在您的问题描述中也没有提到(而且它只需要添加到 val)。
您实际上可能不需要如此精确地解析，因为您似乎只打算生成 C 代码，因此不需要处理运算符优先级。另一方面，您可能有一天希望进行代数转换，在这种情况下需要更精确的解析，而且无论如何都不会花费太多。
一旦掌握了语法，就可以使用 ply (例如)将其变成可执行的解析器。
(这是我拼凑的一个 ply 文件。但它的风格不是很好 :( )
from ply import lex, yacc
class Lexer(object):
tokens = ('INTEGER', 'IDENTIFIER')
literals = '+ - * ( ) ^'.split()
t_ignore = ' \t\n'
t_INTEGER = r'[1-9][0-9]*'
t_IDENTIFIER = r'[a-z]+[0-9]+'
def t_error(self, t):
print("Illegal character '%s'" % t.value[0])
t.lexer.skip(1)
def build(self, **kwargs):
self.lexer = lex.lex(module=self)
# Parser starts here
tokens = Lexer.tokens
start = 'expr'
def p_unit(p):
'''val : IDENTIFIER
term : val
prod : term
expr : prod
'''
p[0] = p[1]
def p_paren(p):
'''val : '(' expr ')' '''
p[0] = p[2]
def p_binary(p):
'''expr : expr '+' prod
expr : expr '-' prod
prod : term '*' prod
'''
p[0] = '(%s%s%s)' %(p[1], p[2], p[3])
def p_pow(p):
'''term : val '^' INTEGER'''
p[0] = 'pow(%s, %s)' % (p[1], p[3])
def p_unary(p):
'''term : '-' val'''
p[0] = '(-%s)' % p[2]
parser = yacc.yacc()
lexer = Lexer().build()
def parse(text):
return parser.parse(text, lexer=lexer)
if __name__ == '__main__':
from sys import argv
for text in argv[1:]:
print(text + ' => ' + parse(text))
快速测试:
$ python exp.py '(a12 + c33 + d34)^2' '(a12 * c33 +-d34)^2'
(a12 + c33 + d34)^2 => pow(((a12+c33)+d34), 2)
(a12 * c33 +-d34)^2 => pow(((a12*c33)+(-d34)), 2)
$ python exp.py '((a12 * c33)^5 + c3)^2'
((a12 * c33)^5 + c3)^2 => pow((pow((a12*c33), 5)+c3), 2)
