c++ - 带有功能支持的 Postfix 的中缀

Question

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

我将不胜感激。

Answer 1

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

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

另外，关于这个实现，有几点需要注意:

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

2. 有 7 种不同的 token :

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

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

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
   

   You can view Comma operator as a add to list function which adds the second argument to the list specified by the first argument or if both are single values it creates a list of two values.

算法

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)