公式和数学表达式解析算法

Question

我必须编写一个能够解析公式的程序。 它应该像下面的示例一样工作：

输入：5x + 7 ^ sin(z) / 2T + 44 输出：输入x，z，t的值 输入：2，1，2 输出：答案是：某个东西

---

它应该支持（+，*，-，^，％，SIN，COS）
我已经阅读了关于Shunting-yard算法的this页面

而且我知道如何将中缀表达式转换为后缀或前缀。
这是我的算法：

1-给出表达式。
2-如果括号平衡，请继续步骤3，否则显示错误并返回步骤1。
3-找到除（SIN，COS）之外的所有变量。
4-从输入中获取变量。
5-替换变量。
6-给表达式加前缀并计算。
7-在输出中显示结果并关闭程序。

是这样的吗？我想在C#中实现它。
请为我提供任何可能对我有用的注释。

- Shahin

---

你可以使用ANTLR，参见此问答。 - Bart Kiers

可能是评估数学表达式的最佳算法？的重复问题。 - H H

Answer 1

如果你决定从头开始编写算法，你的算法看起来不错。我会提供一些思路。

你可能想将步骤 5（替换变量）移至步骤 6（给表达式添加前缀并计算）。换句话说，不仅仅是对变量进行文本查找和替换，而是在每次需要计算变量时进行替换。这可能会打开更多可能性，使得更容易绘制函数图形或具有依赖其他变量值的变量。当然，你的方法对于简单情况应该也可以工作。 sin 和 cos 函数的一个可能的实现，使得未来定义其他函数更容易，可能是使用一个类似于 Dictionary<string, Func<double,double>> 的数据结构，例如：

private var functions = 
    new Dictionary<string, Func<double,double>>(StringComparer.OrdinalIgnoreCase)
    {
        { "sin", Math.Sin },
        { "cos", Math.Cos },
        { "sec", Secant }
    };

. . . 

// checking whether a token is a defined function or a variable
if (functions.ContainsKey(token))
{
    // determine the value of the argument to the function
    double inputValue = getArgument();
    double result = functions[token](inputValue);
    . . .
}

. . .

private static double Secant(double x)
{
    return 1.0 / Math.Cos(x);
}

- Justin

Answer 2

我不知道如何在C#中实现这个，但是Python有一个非常强大的语法树分析器（ast模块），如果你将表达式作为Python表达式给出，它可以帮助你解决问题（这并不难，你只需要添加'*'乘号即可 :-) ）。

首先，定义一个好的类，只重新定义visit_Name方法（例如，对于标识符，另一个visit_Expr被调用，当遇到数字时调用visit_Num等，在这里我们只想要标识符）。

>>> import ast
>>> class MyVisitor(ast.NodeVisitor):
    def __init__(self, *args, **kwargs):
        super(MyVisitor, self).__init__(*args, **kwargs)
        self.identifiers = []

    def generic_visit(self, node):
        ast.NodeVisitor.generic_visit(self, node)

    def visit_Name(self, node):
        # You can specify othe exceptions here than cos or sin
        if node.id not in ['cos', 'sin']:
            self.identifiers.append(node.id)

然后定义一个快速函数，它接受一个表达式并返回其标识符：

>>> def visit(expression):
    node = ast.parse(expression)
    v = MyVisitor()
    v.visit(node)
    print v.identifiers

看起来还不错：

>>> visit('x + 4 * sin(t)')
['x', 't']
>>> visit('5*x + 7 ^ sin(z) / 2*T + 44')
['x', 'z', 'T']

请使用Python 2.6或2.7版本来使用ast模块。

- Emmanuel