Infix to Postfix with function support

Question

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.

Answer 1

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)