我目前正在从Java过渡到Python,并且已经承担了尝试创建一个计算器的任务,该计算器可以对基于中缀的数学表达式执行符号操作(不使用像Sympy这样的自定义模块)。目前,它构建为接受空格分隔的字符串,并且只能执行(,),+, - ,*和/运算符。不幸的是,我无法弄清楚简化符号表达式的基本算法。
例如,给定字符串'2 *((9/6)+ 6 * x)',我的程序应该执行以下步骤:
但是在分发2时我无法让程序忽略x。此外,如何处理'x * 6 / x'以便在简化后返回'6'?
编辑:澄清,通过“符号”我的意思是它将在输出中留下像“A”和“f”这样的字母,同时执行剩余的计算。
编辑2:我(大部分)完成了代码。如果有人在将来偶然发现这篇文章,或者如果你们中的任何一个人好奇,我会在这里发帖。
def reduceExpr(useArray):
# Use Python's native eval() to compute if no letters are detected.
if (not hasLetters(useArray)):
return [calculate(useArray)] # Different from eval() because it returns string version of result
# Base case. Returns useArray if the list size is 1 (i.e., it contains one string).
if (len(useArray) == 1):
return useArray
# Base case. Returns the space-joined elements of useArray as a list with one string.
if (len(useArray) == 3):
return [' '.join(useArray)]
# Checks to see if parentheses are present in the expression & sets.
# Counts number of parentheses & keeps track of first ( found.
parentheses = 0
leftIdx = -1
# This try/except block is essentially an if/else block. Since useArray.index('(') triggers a KeyError
# if it can't find '(' in useArray, the next line is not carried out, and parentheses is not incremented.
try:
leftIdx = useArray.index('(')
parentheses += 1
except Exception:
pass
# If a KeyError was returned, leftIdx = -1 and rightIdx = parentheses = 0.
rightIdx = leftIdx + 1
while (parentheses > 0):
if (useArray[rightIdx] == '('):
parentheses += 1
elif (useArray[rightIdx] == ')'):
parentheses -= 1
rightIdx += 1
# Provided parentheses pair isn't empty, runs contents through again; else, removes the parentheses
if (leftIdx > -1 and rightIdx - leftIdx > 2):
return reduceExpr(useArray[:leftIdx] + [' '.join(['(',reduceExpr(useArray[leftIdx+1:rightIdx-1])[0],')'])] + useArray[rightIdx:])
elif (leftIdx > -1):
return reduceExpr(useArray[:leftIdx] + useArray[rightIdx:])
# If operator is + or -, hold the first two elements and process the rest of the list first
if isAddSub(useArray[1]):
return reduceExpr(useArray[:2] + reduceExpr(useArray[2:]))
# Else, if operator is * or /, process the first 3 elements first, then the rest of the list
elif isMultDiv(useArray[1]):
return reduceExpr(reduceExpr(useArray[:3]) + useArray[3:])
# Just placed this so the compiler wouldn't complain that the function had no return (since this was called by yet another function).
return None
发布于 2018-08-28 09:15:26
在对符号进行操作之前,您需要更多的处理。您想要获取的表单是一个操作树,其中包含叶节点中的值。首先,你需要在字符串上运行词法分析器来获取元素 - 尽管如果你总是有空格分隔元素,那么分割字符串就足够了。然后你需要使用你需要的一些语法来解析那个令牌数组。
如果您需要有关语法和解析文本的理论信息,请从这里开始:http://en.wikipedia.org/wiki/Parsing如果您需要更实用的内容,请访问https://github.com/pyparsing/pyparsing(您不要不必使用pyparsing模块本身,但他们的文档有很多有趣的信息)或http://www.nltk.org/book
从2 * ( ( 9 / 6 ) + 6 * x )
,您需要到达这样的树:
*
2 +
/ *
9 6 6 x
然后,您可以访问每个节点并决定是否要简化它。常量操作将是最简单的操作 - 只需计算结果并用1.5交换“/”节点,因为所有子节点都是常量。
有许多策略可以继续,但基本上你需要找到一种方法来浏览树并修改它,直到没有什么可以改变。
如果要打印结果,只需再次遍历树并生成描述它的表达式。
发布于 2018-08-28 10:27:57
如果要在Python中解析表达式,可以考虑表达式的Python语法并使用ast
模块解析它们(AST =抽象语法树)。
使用Python语法的优点:您不必为此目的创建单独的语言,内置解析器,评估程序也是如此。缺点:您不需要的解析树中存在相当多的额外复杂性(您可以通过使用内置NodeVisitor
和NodeTransformer
类来完成工作来避免其中的一些)。
>>> import ast
>>> a = ast.parse('x**2 + x', mode='eval')
>>> ast.dump(a)
"Expression(body=BinOp(left=BinOp(left=Name(id='x', ctx=Load()), op=Pow(),
right=Num(n=2)), op=Add(), right=Name(id='x', ctx=Load())))"
这是一个示例类,它遍历Python解析树并执行递归常量折叠(对于二进制操作),向您展示您可以相当容易地执行的操作。
from ast import *
class FoldConstants(NodeTransformer):
def visit_BinOp(self, node):
self.generic_visit(node)
if isinstance(node.left, Num) and isinstance(node.right, Num):
expr = copy_location(Expression(node), node)
value = eval(compile(expr, '<string>', 'eval'))
return copy_location(Num(value), node)
else:
return node
>>> ast.dump(FoldConstants().visit(ast.parse('3**2 - 5 + x', mode='eval')))
"Expression(body=BinOp(left=Num(n=4), op=Add(), right=Name(id='x', ctx=Load())))"
https://stackoverflow.com/questions/-100008818
复制相似问题