支持Postfix的功能支持

Question

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

我将欣赏代码。

Answer 1

如果您正在寻找一种算法，可以为您提供转换后缀到后缀的转换，包括对函数调用的支持，则可以使用下面的伪代码（看起来像python代码）。我已经为我的案例编写了此文件，但尚未进行全面测试。如果您发现任何错误，请告诉我。

我也为此编写了Java实现。

另外，关于此实现的几点注意事项：

1. 此算法假定infix中有令牌流。它不解析表达式字符串。因此，每个令牌都可以标识为操作数，运算符，函数调用等。

2. 有7种不同的令牌：

   • X，Y等操作数
   • 左括号-（
   • 右括号-）
   • 运算子-+，*
   • 函数调用开始-sin（
   • 函数调用结束-sin（x ）
   • 逗号-，
   • 函数调用开始用[算法中的字符表示，函数调用结束用表示]。请注意，函数调用终止是与右括号不同的令牌，)尽管它们可以在字符串表达式中用相同的字符表示。

3. 每个运算符都是二进制运算符，其优先级和关联性是其通常的含义。

4. 逗号,是一种特殊的二进制运算符，其优先级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)