1

整个网络上有许多算法可以将中缀转换为后缀。但我的问题是如何使它支持功能？例如 sin(x+y)*z。

我会很感激一个代码。

4

5 回答 5

3

这很简单：它也适用于函数，您使用的常规运算符（如 +、-、*）也是函数。您的问题是，您认为“功能”（如 sin）不是中缀，而是前缀。

回到您的问题：只需将这些前缀函数转换为后缀（您也应该在网络上找到后缀的前缀 - 我的假设是您不知道“前缀”术语）。

编辑：基本上，首先转换参数并按顺序输出它们，然后附加函数的名称。

于 2012-07-29T09:47:11.463 回答
3

如果您正在寻找一种算法，可以将中缀转换为后缀，包括函数调用支持，您可以使用下面的伪代码（看起来像 python 代码）。我已经为我的案例写了这个，但还没有经过彻底的测试。如果您发现任何错误，请告诉我。

我还为此编写了一个 Java 实现。

此外，关于此实现，有几点需要注意：

  1. 该算法假定中缀中的标记流。它不解析表达式字符串。因此，每个标记都可以识别为操作数、运算符、函数调用等。

  2. 有 7 种不同的令牌：

    • 操作数 X、Y 等
    • 左括号 - (
    • 右括号 - )
    • 运算符 - +, *
    • 函数调用开始 - sin(
    • 函数调用结束 - sin( x )
    • 逗号 - ,

  3. 函数调用开始在算法中用[字符表示，函数调用结束用 表示]。请注意，函数调用终止是与右括号不同的标记，)尽管它们可能由字符串表达式中的相同字符表示。

  4. 每个运算符都是二元运算符，具有优先级和关联性作为它们通常的含义。

  5. 逗号,是一种特殊的二元运算符，其优先级NEGATIVE INFINITY和关联性为 LEFT（与 + 和 * 相同）。逗号运算符用于分隔函数调用的参数。所以对于函数调用：

    f(a,b,c)

first comma separates a and b
second comma separates a,b and c

So the postfix for the above will be 
ab,c,f

    您可以将逗号运算符视为添加到列表函数，它将第二个参数添加到第一个参数指定的列表中，或者如果两者都是单个值，它会创建一个包含两个值的列表。

算法

infix_to_postfix(infix):

    postfix = []
    infix.add(')')
    stack = []
    stack.push('(')
    for each token in infix: 
        if token is operand:
            postfix.add(token)
        if token is '[':
            stack.push(token)
        else if token is operator:
            if stack is empty OR 
               stack[top] is '(' or stack[top] is '[':
                stack.push(token)
            else if (operator)token['precedence'] > stack[top]['precedence'] OR
               ( (operator)token['precedence'] == stack[top]['precedence'] AND 
                 (operator)token['associativity') == 'RIGHT' ):
                stack.push(token)     
            else
                postfix.add(stack.pop())
                stack.push(token)
        else if token is '(':
            stack.push(token)
        else if token is ')':            
            while topToken = stack.pop() NOT '(':
                postfix.add(topToken)
        else if token is ']':
            while True:
                topToken = stack.pop()
                postfix.add(topToken)
                if topToken is '[':
                    break

        else if token is ',':
            while topToken = stack.peek() NOT '[':
                postfix.add(topToken)
                stack.pop()
            stack.push(token)
于 2016-01-24T00:34:30.653 回答
2

您必须自己编写代码。以您的具体案例为例可能会帮助您入门；的后缀形式sin(x + y) * z是：

xy + 罪 z *

请注意，在这一示例中，一些操作对两个值 (+和*) 进行操作，而其他操作对一个 ( sin)

于 2012-07-29T09:50:10.890 回答
2

尽管@mickeymoon 算法似乎有效，但我仍然需要进行一些调整（对我不起作用），所以我认为它对其他实现（类似 Java 的实现）可能会有所帮助。基于https://en.wikipedia.org/wiki/Shunting-yard_algorithm

Stack<Token> stack = new Stack<>();
List<Token> result = new ArrayList<>();
//https://en.wikipedia.org/wiki/Shunting-yard_algorithm
// with small adjustment for expressions in functions. Wiki example works only for constants as arguments
for (Token token : tokens) {
    if (isNumber(token) || isIdentifier(token)) {
        result.add(token);
        continue;
    }
    if (isFunction(token)) {
        stack.push(token);
        continue;
    }


    // if OP(open parentheses) then put to stack
    if (isOP(token)) {
        stack.push(token);
        continue;
    }
    // CP(close parentheses) pop stack to result until OP
    if (isCP(token)) {
        Token cur = stack.pop();
        while (!isOP(cur)) {
            if (!isComma(cur)) {
                result.add(cur);
            }
            cur = stack.pop();
        }
        continue;
    }
    if (isBinaryOperation(token)) {
        if (!stack.empty()) {
            Token cur = stack.peek();
            while ((!isBinaryOperation(cur)
                    || (isBinaryOperation(cur) && hasHigherPriority(cur, token))
                    || (hasEqualPriority(cur, token) && isLeftAssociative(token)))
                    && !isOP(cur)
            ) {
                // no need in commas in resulting list if we now how many parameters the function need
                if (!isComma(cur)) {
                    result.add(cur);
                }

                stack.pop();
                if (!stack.empty()) {
                    cur = stack.peek();
                }
            }
        }
        stack.push(token);
        continue;
    }

    if (isComma(token)) {
        Token cur = stack.peek();
        while (!(isOP(cur) || isComma(cur))) {
            result.add(cur);
            stack.pop();
            if (!stack.empty()) {
                cur = stack.peek();//  don't pop if priority is less
            }
        }
        stack.push(token);

    }
}
while (!stack.empty()) {
    Token pop = stack.pop();
    if (!isComma(pop)) {
        result.add(pop);
    }

}
return result;

我用各种复杂的表达式测试了它，包括函数组合和复杂的参数（不适用于 Wiki 算法的示例）。几个例子（e 只是一个变量，min，max，rand - 函数）：

输入： (3.4+2^(5-e))/(1+5/5)

输出： 3.4 2 5 e - ^ + 1 5 / + /

输入： 2+rand(1.4+2, 3+4)

输出： 2 1.4 2 + 3 4 + 兰特 +

输入： max(4+4,min(1*10,2+(3-e)))

输出： 4 4 + 1 10 * 2 3 e - + min max

我还使用具有三个参数的复杂函数（其中每个参数本身就是一个表达式）对其进行了测试，并且它的文字很好。

这是我的java 函数的 github，它获取标记列表并以后缀表示法返回标记列表。这是从第一个函数获取输出并计算表达式值的函数

于 2020-03-31T19:02:38.757 回答
1

二元运算符 like+可以被视为+(x,y) 类似地考虑 sin、cos 等函数作为一元运算符。所以，sin(x+y)*z 可以写成x y + sin z *。您需要对这些一元函数进行特殊处理。

于 2012-07-29T09:49:04.593 回答