我可以在Python 2.7中写一个符号计算的函数吗？
我现在正在从Java转到Python，正在尝试制作一个计算器，可以对用中缀表示法写的数学表达式进行符号运算（不使用像Sympy这样的自定义模块）。目前，这个计算器可以接受用空格分隔的字符串，并且只能处理 (, ), +, -, *, 和 / 这些运算符。不过，我还搞不清楚简化符号表达式的基本算法。
举个例子，给定字符串 '2 * ( ( 9 / 6 ) + 6 * x )'，我的程序应该执行以下步骤：
- 2 * ( 1.5 + 6 * x )
- 3 + 12 * 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
2 个回答
如果你在用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())))"
在对符号进行操作之前，你需要进行更多的处理。你想要得到的形式是一个操作的树，树的叶子节点里是值。首先，你需要对字符串进行词法分析，提取出元素——不过如果你的元素总是用空格分开的，直接分割字符串也许就够了。接下来，你需要根据你需要的语法来解析这个元素数组。
如果你想了解语法和文本解析的理论知识，可以从这里开始：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，因为所有的子节点都是常量。
接下来有很多策略可以继续，但基本上你需要找到一种方法，遍历这棵树并进行修改，直到没有可以改变的地方。
如果你想打印结果，那就再遍历一次这棵树，生成一个描述它的表达式。