如何拆分 python 中的一串数学表达式？
How can I split a string of a mathematical expressions in python?
我制作了一个将中缀转换为后缀的程序 python。问题是当我引入参数时。
如果我介绍这样的东西：（这将是一个字符串）
( ( 73 + ( ( 34 - 72 ) / ( 33 - 3 ) ) ) + ( 56 + ( 95 - 28 ) ) )
它将使用 .split() 拆分它，程序将正常运行。
但我希望用户能够介绍这样的东西：
((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )
如您所见，我希望空格可以是微不足道的，但程序会继续按括号、整数（不是数字）和操作数拆分字符串。
我尝试用 for 来解决它，但我不知道如何捕捉整个数字 (73、34、72) 而不是一个数字一个数字 (7、3、3、4、 7 , 2)
综上所述，我想要的是将((81 * 6) /42+ (3-1))这样的字符串拆分成：
[(, (, 81, *, 6, ), /, 42, +, (, 3, -, 1, ), )]
树 ast
您可以使用 ast 来获得表达式树：
import ast
source = '((81 * 6) /42+ (3-1))'
node = ast.parse(source)
def show_children(node, level=0):
if isinstance(node, ast.Num):
print(' ' * level + str(node.n))
else:
print(' ' * level + str(node))
for child in ast.iter_child_nodes(node):
show_children(child, level+1)
show_children(node)
它输出：
<_ast.Module object at 0x7f56abbc5490>
<_ast.Expr object at 0x7f56abbc5350>
<_ast.BinOp object at 0x7f56abbc5450>
<_ast.BinOp object at 0x7f56abbc5390>
<_ast.BinOp object at 0x7f56abb57cd0>
81
<_ast.Mult object at 0x7f56abbd0dd0>
6
<_ast.Div object at 0x7f56abbd0e50>
42
<_ast.Add object at 0x7f56abbd0cd0>
<_ast.BinOp object at 0x7f56abb57dd0>
3
<_ast.Sub object at 0x7f56abbd0d50>
1
正如@user2357112 在评论中所写：ast.parse 解释 Python 语法，而不是数学表达式。 (1+2)(3+4) 将被解析为函数调用，并且列表理解将被接受，即使它们可能不应该被视为有效的数学表达式。
使用正则表达式列出
如果你想要一个平面结构，正则表达式可以工作：
import re
number_or_symbol = re.compile('(\d+|[^ 0-9])')
print(re.findall(number_or_symbol, source))
# ['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1', ')', ')']
它寻找：
- 多位数
- 或任何不是数字或 space
的字符
获得元素列表后，您可以检查语法是否正确，例如使用 stack 检查括号是否匹配，或者每个元素是否已知。
您需要为您的输入实现一个非常简单的分词器。您有以下类型的令牌：
- (
- )
- +
- -
- *
- /
- \d+
您可以在输入字符串中找到它们，它们由各种白色分隔 space。
所以第一步是从头到尾处理字符串，提取这些标记，然后对标记进行解析，而不是对字符串本身进行解析。
执行此操作的一种巧妙方法是使用以下正则表达式：'\s*([()+*/-]|\d+)'。然后您可以：
import re
the_input='(3+(2*5))'
tokens = []
tokenizer = re.compile(r'\s*([()+*/-]|\d+)')
current_pos = 0
while current_pos < len(the_input):
match = tokenizer.match(the_input, current_pos)
if match is None:
raise Error('Syntax error')
tokens.append(match.group(1))
current_pos = match.end()
print(tokens)
这将打印 ['(', '3', '+', '(', '2', '*', '5', ')', ')']
您也可以使用 re.findall 或 re.finditer，但是您会跳过不匹配项，在这种情况下是语法错误。
快速正则表达式答案：
re.findall(r"\d+|[()+\-*\/]", str_in)
示范：
>>> import re
>>> str_in = "((81 * 6) /42+ (3-1))"
>>> re.findall(r"\d+|[()+\-*\/]", str_in)
['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1',
')', ')']
对于嵌套的括号部分，您可以使用堆栈来跟踪级别。
如果你不想使用re模块，你可以试试这个：
s="((81 * 6) /42+ (3-1))"
r=[""]
for i in s.replace(" ",""):
if i.isdigit() and r[-1].isdigit():
r[-1]=r[-1]+i
else:
r.append(i)
print(r[1:])
输出：
['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1', ')', ')']
手动滚动一个简单的表达式分词器实际上非常简单。而且我认为您也可以通过这种方式学到更多。
因此，为了教育和学习，这是一个可以扩展的简单表达式分词器实现。它基于 "maximal-much" 规则工作。这意味着它会采取行动 "greedy"，尝试使用尽可能多的字符来构造每个标记。
事不宜迟，这是分词器：
class ExpressionTokenizer:
def __init__(self, expression, operators):
self.buffer = expression
self.pos = 0
self.operators = operators
def _next_token(self):
atom = self._get_atom()
while atom and atom.isspace():
self._skip_whitespace()
atom = self._get_atom()
if atom is None:
return None
elif atom.isdigit():
return self._tokenize_number()
elif atom in self.operators:
return self._tokenize_operator()
else:
raise SyntaxError()
def _skip_whitespace(self):
while self._get_atom():
if self._get_atom().isspace():
self.pos += 1
else:
break
def _tokenize_number(self):
endpos = self.pos + 1
while self._get_atom(endpos) and self._get_atom(endpos).isdigit():
endpos += 1
number = self.buffer[self.pos:endpos]
self.pos = endpos
return number
def _tokenize_operator(self):
operator = self.buffer[self.pos]
self.pos += 1
return operator
def _get_atom(self, pos=None):
pos = pos or self.pos
try:
return self.buffer[pos]
except IndexError:
return None
def tokenize(self):
while True:
token = self._next_token()
if token is None:
break
else:
yield token
这是一个用法演示：
tokenizer = ExpressionTokenizer('((81 * 6) /42+ (3-1))', {'+', '-', '*', '/', '(', ')'})
for token in tokenizer.tokenize():
print(token)
产生输出：
(
(
81
*
6
)
/
42
+
(
3
-
1
)
)
这并没有提供您想要的结果，但查看此问题的其他人可能会感兴趣。它利用了 pyparsing 库。
# Stolen from http://pyparsing.wikispaces.com/file/view/simpleArith.py/30268305/simpleArith.py
# Copyright 2006, by Paul McGuire
# ... and slightly altered
from pyparsing import *
integer = Word(nums).setParseAction(lambda t:int(t[0]))
variable = Word(alphas,exact=1)
operand = integer | variable
expop = Literal('^')
signop = oneOf('+ -')
multop = oneOf('* /')
plusop = oneOf('+ -')
factop = Literal('!')
expr = operatorPrecedence( operand,
[("!", 1, opAssoc.LEFT),
("^", 2, opAssoc.RIGHT),
(signop, 1, opAssoc.RIGHT),
(multop, 2, opAssoc.LEFT),
(plusop, 2, opAssoc.LEFT),]
)
print (expr.parseString('((81 * 6) /42+ (3-1))'))
输出：
[[[[81, '*', 6], '/', 42], '+', [3, '-', 1]]]
要提供一种您可以轻松扩展的更详细的正则表达式方法：
import re
solution = []
pattern = re.compile('([\d\.]+)')
s = '((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )'
for token in re.split(pattern, s):
token = token.strip()
if re.match(pattern, token):
solution.append(float(token))
continue
for character in re.sub(' ', '', token):
solution.append(character)
这会给你结果：
solution = ['(', '(', 73, '+', '(', '(', 34, '-', 72, ')', '/', '(', 33, '-', 3, ')', ')', ')', '+', '(', 56, '+', '(', 95, '-', 28, ')', ')', ')']
使用 grako：
start = expr $;
expr = calc | value;
calc = value operator value;
value = integer | "(" @:expr ")" ;
operator = "+" | "-" | "*" | "/";
integer = /\d+/;
grako 转译为 python。
对于此示例，return 值如下所示：
['73', '+', ['34', '-', '72', '/', ['33', '-', '3']], '+', ['56', '+', ['95', '-', '28']]]
通常您会使用生成的语义 class 作为进一步处理的模板。
与@McGrady 的回答类似，您可以使用基本队列实现来完成此操作。
作为一个非常基本的实现，您的队列 class 可能如下所示：
class Queue:
EMPTY_QUEUE_ERR_MSG = "Cannot do this operation on an empty queue."
def __init__(self):
self._items = []
def __len__(self) -> int:
return len(self._items)
def is_empty(self) -> bool:
return len(self) == 0
def enqueue(self, item):
self._items.append(item)
def dequeue(self):
try:
return self._items.pop(0)
except IndexError:
raise RuntimeError(Queue.EMPTY_QUEUE_ERR_MSG)
def peek(self):
try:
return self._items[0]
except IndexError:
raise RuntimeError(Queue.EMPTY_QUEUE_ERR_MSG)
使用这个简单的 class，您可以将解析函数实现为：
def tokenize_with_queue(exp: str) -> List:
queue = Queue()
cum_digit = ""
for c in exp.replace(" ", ""):
if c in ["(", ")", "+", "-", "/", "*"]:
if cum_digit != "":
queue.enqueue(cum_digit)
cum_digit = ""
queue.enqueue(c)
elif c.isdigit():
cum_digit += c
else:
raise ValueError
if cum_digit != "": #one last sweep in case there are any digits waiting
queue.enqueue(cum_digit)
return [queue.dequeue() for i in range(len(queue))]
测试如下：
exp = "((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )"
print(tokenize_with_queue(exp)")
会给你令牌列表为：
['(', '(', '73', '+', '(', '(', '34', '-', '72', ')', '/', '(', '33', '-', '3', ')', ')', ')', '+', '(', '56', '+', '(', '95', '-', '28', ')', ')', ')']
我制作了一个将中缀转换为后缀的程序 python。问题是当我引入参数时。 如果我介绍这样的东西：（这将是一个字符串）
( ( 73 + ( ( 34 - 72 ) / ( 33 - 3 ) ) ) + ( 56 + ( 95 - 28 ) ) )
它将使用 .split() 拆分它，程序将正常运行。 但我希望用户能够介绍这样的东西：
((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )
如您所见，我希望空格可以是微不足道的，但程序会继续按括号、整数（不是数字）和操作数拆分字符串。
我尝试用 for 来解决它，但我不知道如何捕捉整个数字 (73、34、72) 而不是一个数字一个数字 (7、3、3、4、 7 , 2)
综上所述，我想要的是将((81 * 6) /42+ (3-1))这样的字符串拆分成：
[(, (, 81, *, 6, ), /, 42, +, (, 3, -, 1, ), )]
树 ast
您可以使用 ast 来获得表达式树：
import ast
source = '((81 * 6) /42+ (3-1))'
node = ast.parse(source)
def show_children(node, level=0):
if isinstance(node, ast.Num):
print(' ' * level + str(node.n))
else:
print(' ' * level + str(node))
for child in ast.iter_child_nodes(node):
show_children(child, level+1)
show_children(node)
它输出：
<_ast.Module object at 0x7f56abbc5490>
<_ast.Expr object at 0x7f56abbc5350>
<_ast.BinOp object at 0x7f56abbc5450>
<_ast.BinOp object at 0x7f56abbc5390>
<_ast.BinOp object at 0x7f56abb57cd0>
81
<_ast.Mult object at 0x7f56abbd0dd0>
6
<_ast.Div object at 0x7f56abbd0e50>
42
<_ast.Add object at 0x7f56abbd0cd0>
<_ast.BinOp object at 0x7f56abb57dd0>
3
<_ast.Sub object at 0x7f56abbd0d50>
1
正如@user2357112 在评论中所写：ast.parse 解释 Python 语法，而不是数学表达式。 (1+2)(3+4) 将被解析为函数调用，并且列表理解将被接受，即使它们可能不应该被视为有效的数学表达式。
使用正则表达式列出
如果你想要一个平面结构，正则表达式可以工作：
import re
number_or_symbol = re.compile('(\d+|[^ 0-9])')
print(re.findall(number_or_symbol, source))
# ['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1', ')', ')']
它寻找：
- 多位数
- 或任何不是数字或 space 的字符
获得元素列表后，您可以检查语法是否正确，例如使用 stack 检查括号是否匹配，或者每个元素是否已知。
您需要为您的输入实现一个非常简单的分词器。您有以下类型的令牌：
- (
- )
- +
- -
- *
- /
- \d+
您可以在输入字符串中找到它们，它们由各种白色分隔 space。
所以第一步是从头到尾处理字符串，提取这些标记，然后对标记进行解析，而不是对字符串本身进行解析。
执行此操作的一种巧妙方法是使用以下正则表达式：'\s*([()+*/-]|\d+)'。然后您可以：
import re
the_input='(3+(2*5))'
tokens = []
tokenizer = re.compile(r'\s*([()+*/-]|\d+)')
current_pos = 0
while current_pos < len(the_input):
match = tokenizer.match(the_input, current_pos)
if match is None:
raise Error('Syntax error')
tokens.append(match.group(1))
current_pos = match.end()
print(tokens)
这将打印 ['(', '3', '+', '(', '2', '*', '5', ')', ')']
您也可以使用 re.findall 或 re.finditer，但是您会跳过不匹配项，在这种情况下是语法错误。
快速正则表达式答案：
re.findall(r"\d+|[()+\-*\/]", str_in)
示范：
>>> import re
>>> str_in = "((81 * 6) /42+ (3-1))"
>>> re.findall(r"\d+|[()+\-*\/]", str_in)
['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1',
')', ')']
对于嵌套的括号部分，您可以使用堆栈来跟踪级别。
如果你不想使用re模块，你可以试试这个：
s="((81 * 6) /42+ (3-1))"
r=[""]
for i in s.replace(" ",""):
if i.isdigit() and r[-1].isdigit():
r[-1]=r[-1]+i
else:
r.append(i)
print(r[1:])
输出：
['(', '(', '81', '*', '6', ')', '/', '42', '+', '(', '3', '-', '1', ')', ')']
手动滚动一个简单的表达式分词器实际上非常简单。而且我认为您也可以通过这种方式学到更多。
因此，为了教育和学习，这是一个可以扩展的简单表达式分词器实现。它基于 "maximal-much" 规则工作。这意味着它会采取行动 "greedy"，尝试使用尽可能多的字符来构造每个标记。
事不宜迟，这是分词器：
class ExpressionTokenizer:
def __init__(self, expression, operators):
self.buffer = expression
self.pos = 0
self.operators = operators
def _next_token(self):
atom = self._get_atom()
while atom and atom.isspace():
self._skip_whitespace()
atom = self._get_atom()
if atom is None:
return None
elif atom.isdigit():
return self._tokenize_number()
elif atom in self.operators:
return self._tokenize_operator()
else:
raise SyntaxError()
def _skip_whitespace(self):
while self._get_atom():
if self._get_atom().isspace():
self.pos += 1
else:
break
def _tokenize_number(self):
endpos = self.pos + 1
while self._get_atom(endpos) and self._get_atom(endpos).isdigit():
endpos += 1
number = self.buffer[self.pos:endpos]
self.pos = endpos
return number
def _tokenize_operator(self):
operator = self.buffer[self.pos]
self.pos += 1
return operator
def _get_atom(self, pos=None):
pos = pos or self.pos
try:
return self.buffer[pos]
except IndexError:
return None
def tokenize(self):
while True:
token = self._next_token()
if token is None:
break
else:
yield token
这是一个用法演示：
tokenizer = ExpressionTokenizer('((81 * 6) /42+ (3-1))', {'+', '-', '*', '/', '(', ')'})
for token in tokenizer.tokenize():
print(token)
产生输出：
(
(
81
*
6
)
/
42
+
(
3
-
1
)
)
这并没有提供您想要的结果，但查看此问题的其他人可能会感兴趣。它利用了 pyparsing 库。
# Stolen from http://pyparsing.wikispaces.com/file/view/simpleArith.py/30268305/simpleArith.py
# Copyright 2006, by Paul McGuire
# ... and slightly altered
from pyparsing import *
integer = Word(nums).setParseAction(lambda t:int(t[0]))
variable = Word(alphas,exact=1)
operand = integer | variable
expop = Literal('^')
signop = oneOf('+ -')
multop = oneOf('* /')
plusop = oneOf('+ -')
factop = Literal('!')
expr = operatorPrecedence( operand,
[("!", 1, opAssoc.LEFT),
("^", 2, opAssoc.RIGHT),
(signop, 1, opAssoc.RIGHT),
(multop, 2, opAssoc.LEFT),
(plusop, 2, opAssoc.LEFT),]
)
print (expr.parseString('((81 * 6) /42+ (3-1))'))
输出：
[[[[81, '*', 6], '/', 42], '+', [3, '-', 1]]]
要提供一种您可以轻松扩展的更详细的正则表达式方法：
import re
solution = []
pattern = re.compile('([\d\.]+)')
s = '((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )'
for token in re.split(pattern, s):
token = token.strip()
if re.match(pattern, token):
solution.append(float(token))
continue
for character in re.sub(' ', '', token):
solution.append(character)
这会给你结果：
solution = ['(', '(', 73, '+', '(', '(', 34, '-', 72, ')', '/', '(', 33, '-', 3, ')', ')', ')', '+', '(', 56, '+', '(', 95, '-', 28, ')', ')', ')']
使用 grako：
start = expr $;
expr = calc | value;
calc = value operator value;
value = integer | "(" @:expr ")" ;
operator = "+" | "-" | "*" | "/";
integer = /\d+/;
grako 转译为 python。
对于此示例，return 值如下所示：
['73', '+', ['34', '-', '72', '/', ['33', '-', '3']], '+', ['56', '+', ['95', '-', '28']]]
通常您会使用生成的语义 class 作为进一步处理的模板。
与@McGrady 的回答类似，您可以使用基本队列实现来完成此操作。 作为一个非常基本的实现，您的队列 class 可能如下所示：
class Queue:
EMPTY_QUEUE_ERR_MSG = "Cannot do this operation on an empty queue."
def __init__(self):
self._items = []
def __len__(self) -> int:
return len(self._items)
def is_empty(self) -> bool:
return len(self) == 0
def enqueue(self, item):
self._items.append(item)
def dequeue(self):
try:
return self._items.pop(0)
except IndexError:
raise RuntimeError(Queue.EMPTY_QUEUE_ERR_MSG)
def peek(self):
try:
return self._items[0]
except IndexError:
raise RuntimeError(Queue.EMPTY_QUEUE_ERR_MSG)
使用这个简单的 class，您可以将解析函数实现为：
def tokenize_with_queue(exp: str) -> List:
queue = Queue()
cum_digit = ""
for c in exp.replace(" ", ""):
if c in ["(", ")", "+", "-", "/", "*"]:
if cum_digit != "":
queue.enqueue(cum_digit)
cum_digit = ""
queue.enqueue(c)
elif c.isdigit():
cum_digit += c
else:
raise ValueError
if cum_digit != "": #one last sweep in case there are any digits waiting
queue.enqueue(cum_digit)
return [queue.dequeue() for i in range(len(queue))]
测试如下：
exp = "((73 + ( (34- 72 ) / ( 33 -3) )) + (56 +(95 - 28) ) )"
print(tokenize_with_queue(exp)")
会给你令牌列表为：
['(', '(', '73', '+', '(', '(', '34', '-', '72', ')', '/', '(', '33', '-', '3', ')', ')', ')', '+', '(', '56', '+', '(', '95', '-', '28', ')', ')', ')']