使用函数支持中缀到Postfix [英] Infix to Postfix with function support

问题描述

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

我会感谢代码。

解决方案

如果你正在寻找一个算法，给你的转换infix到postfix包括函数调用支持，你可以使用下面的伪代码（看起来像python代码）。我写了这个为我的情况，但尚未测试thouroughly。如果您发现任何错误，请让我知道。

我也写了一个Java实现。

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

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




2. 有7种不同的令牌：

   
   
   
   
   
   • 操作数X，Y等
   
   
   • 左边界 - （
   
   
   • 右边界 - / li>
     
   • 运算符 - +，*
   
   
   • 函数调用开始 - sin（
   
   
   • 函数调用结束 - ）
   
   
   • 逗号 - ，
   
   

<开始由 []表示，算法和函数调用结束中的字符由] 表示。


3. 是一个不同的符号，不过它们可以用字符串表达式中的相同字符表示。

   每个运算符都是具有优先级和关联性的二元运算符。




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

     f（a，b，c）
    
   和b 
   第二个逗号分隔a，b和c 
    
   因此，上述的后缀将是
    ab，c，f 
     

   
   
   

   
   

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

   
   

/ h3>

  infix_to_postfix（中文）：
 
 postfix = [] 
 infix.add '）
 stack = [] 
 stack.push（'（'）
对于中缀中的每个令牌：
如果令牌是操作数：
 postfix.add ）
如果token是'['：
 stack.push（token）
 else如果token是运算符：
如果堆栈为空OR 
 stack [top] '（'或stack [top]是'['：
 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如果token是'（'：
 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）
如果topToken是'['：
 break 
 
 else if token is'，'：
 while topToken = stack.peek（）NOT'['：
 postfix .add（topToken）
 stack.pop（）
 stack.push（token）
  

There are many algorithms to convert infix to postfix all over the web. But my question is how to make that to support functions? For example sin(x+y)*z.

I will appreciate a code.

解决方案

If you are looking for an algorithm that gives you the conversion infix to postfix including function call support, you can use the below pseudocode(which looks like python code). I have written this for my case but not yet tested thouroughly. If you find any bugs please let me know.

I have also written a Java implementation for the same.

Also, there are few things to note about this implementation:

1. This algorithm assumes a stream of tokens in infix. It does not parse a expression string. So each token can be identified as an operand, operator, function call etc.

2. There are 7 different kinds of tokens:

   • Operands X, Y etc
   • Left Paranthesis - (
   • Right Paranthesis - )
   • Operators - +, *
   • Function call starts - sin(
   • Function call ends - sin( x )
   • Comma - ,

3. Function call starts are denoted by [ character in the algorithm and function call ends are denoted by ]. Please note that function call termination is a different token than Right Paranthesis ) although they may be represented by the same character in the string expression.

4. Every operator is a binary operator with precedence and associativity as their usual meaning.

5. Comma , is a special binary operator with precedence of NEGATIVE INFINITY and associativity as LEFT (same as + and *). Comma operator is used to separate the arguments of a function call. So for a function call:

   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.

Algorithm

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)

这篇关于使用函数支持中缀到Postfix的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！