Shunting algorithm with functions

You can handle "FUN", "(", ")", "," similar to other operators, and they can be pressed on TOKEN_STACK. (I have abbreviated FUNCTION to FUN for brevity.) "FUN", "(", ")", "," have a lower priority than "+", so the priority table looks like

^                    4
*  /  %              3
+  -                 2
( ) ,   FUN          1

      

        
        
        
      

    

Consider what happens when 1 + FUN (2 * 3) is parsed

Remaining Input     Stack             Output
1+FUN(2*3)                          
+FUN(2*3)                           1
FUN(2*3)          +                 1
(2*3)             +  FUN            1
2*3)              +  FUN  (         1
*3)               +  FUN  (         1  2
3)                +  FUN  (  *      1  2
)                 +  FUN  (  *      1  2  3
                  +  FUN  (  *  )   1  2  3          Note 1
                  +  FUN  ( )       1  2  3  *       Note 2
                  +                 1  2  3  * FUN() 
                                    1  2  3  * FUN() +

      

        
        
        
      

    

The output token "FUN ()" means function evaluation.

Note 1: when we try to push ")" onto the stack, all higher priority operators are popped off the stack and pushed to output.

Note 2: When an item at the end of the stack matches "(" it is popped from the stack. There are two cases of handling, simple parenthesis matching as with 1 + (2 * 3) or if there is a function token before "(" on the stack. In this case, you get FUN from the stack and add a function token to output.

"," will be treated the same way "), which will result in higher-priority operators exiting. But this will not affect the function's output. You need some way to record how many arguments the function has.

In my code, I am using a recursion based algorithm. The parsing algorithm can be called recursively and provided with a stop marker. When a stop marker is encountered, it is returned from recursion. When a function is encountered, it calls a recursion that expects a "," or ")".

I am able to run iut using the cscript command line. I also added some debug code using Wscript.Echo.

Looking at TOKEN_STACK you never pushed the FUNCTION token onto the stack, so it wasn't there when you looked for it.

Adding a CASE "FUNCTION" CALL PUSH (INPUT (TOKEN_NUMBER), TOKEN_STACK)

seems to give the right thing. Though I'm not sure what should happen when you agree with the first closing parenthesis. It also doesn't work well with input like "E + FUNCTION ((A, B), C) + F".

SET PRECEDENCE = CREATEOBJECT("SCRIPTING.DICTIONARY")
WITH PRECEDENCE
    .ADD "^",3
    .ADD "*",2
    .ADD "/",2
    .ADD "%",2
    .ADD "+",1
    .ADD "-",1
    .ADD "FUNCTION",0
    .ADD "(",0
    .ADD ",",0
    .ADD ")",0
END WITH

Wscript.Echo "Start"

'#############################################################################
tokenArray = split("FUNCTION ( ( A , B ) , C )")
'#tokenArray = split("A + B * C")


Wscript.Echo "Result " + SHUNTINGYARD(tokenArray)
'#############################################################################

FUNCTION SHUNTINGYARD(INPUT)

    TOKEN_QUEUE = ARRAY()
    TOKEN_STACK = ARRAY()

    FOR TOKEN_NUMBER = 0 TO UBOUND(INPUT)
    Wscript.Echo "Token " + INPUT(TOKEN_NUMBER)
    Wscript.Echo "Stack " + JOIN(TOKEN_STACK,"|")

        SELECT CASE INPUT(TOKEN_NUMBER)

            CASE "("
                CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)

            CASE ")"

                DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )

                    CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
                    IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching ""("".", TRUE)
                LOOP

                IF PEEK(TOKEN_STACK) = "FUNCTION" THEN
                    DISCARD = POP(TOKEN_STACK)
                    CALL PUSH("@", TOKEN_QUEUE)
                ELSE
                    DISCARD = POP(TOKEN_STACK)
                END IF

            CASE ","
                DO WHILE NOT( PRECEDENCE( PEEK(TOKEN_STACK) ) = 0 )
                    CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
                    IF STACKISEMPTY(TOKEN_STACK) THEN CALL ERRORS("Can't find a matching function ""("".", TRUE)
                LOOP

            CASE "+","-","*","/","^","%"
                TOKEN_A = INPUT(TOKEN_NUMBER)
                DO WHILE ISOPERATOR(PEEK(TOKEN_STACK))
                    TOKEN_B = PEEK(TOKEN_STACK)
                    IF (ASSOCIATIVITY(TOKEN_B) = "left" AND PRECEDENCE(TOKEN_A) = PRECEDENCE(TOKEN_B)) OR (PRECEDENCE(TOKEN_A) < PRECEDENCE(TOKEN_B)) THEN
                        CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
                    ELSE
                        EXIT DO
                    END IF
                LOOP
                CALL PUSH(TOKEN_A, TOKEN_STACK)

            CASE "FUNCTION"
                CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_STACK)

            CASE ELSE
                CALL PUSH(INPUT(TOKEN_NUMBER), TOKEN_QUEUE)

        END SELECT
    NEXT

    FOR ITEMCOUNT = 0 TO UBOUND(TOKEN_STACK)
        IF PEEK(TOKEN_STACK) = "(" THEN CALL ERRORS("Can't find a matching "")"".", TRUE)'(
        CALL PUSH(POP(TOKEN_STACK), TOKEN_QUEUE)
    NEXT

    SHUNTINGYARD = JOIN(TOKEN_QUEUE,"|")

END FUNCTION

'#############################################################################

FUNCTION ASSOCIATIVITY(ASSOC)
    SELECT CASE LCASE(ASSOC)
        CASE "^","\"
            ASSOCIATIVITY = "right"
        CASE ELSE
            ASSOCIATIVITY = "left"
    END SELECT
END FUNCTION

FUNCTION ISOPERATOR(ITEM)
    ISOPERATOR = LEN(ITEM) = 1 AND INSTR("+-*/%^",ITEM)
END FUNCTION

SUB PUSH(ITEM,BYREF STACK)
    IF UBOUND(STACK) > -1 THEN
        REDIM PRESERVE STACK(UBOUND(STACK) + 1)
        STACK(UBOUND(STACK)) = ITEM
    ELSE
        STACK = ARRAY(ITEM)
    END IF
END SUB

FUNCTION POP(BYREF STACK)
    IF UBOUND(STACK) > -1 THEN
        POP = STACK(UBOUND(STACK))
        REDIM PRESERVE STACK(UBOUND(STACK) - 1)
    END IF
END FUNCTION

FUNCTION STACKISEMPTY(STACK)
    IF UBOUND(STACK) > -1 THEN
        STACKISEMPTY = FALSE
    ELSE
        STACKISEMPTY = TRUE
    END IF
END FUNCTION

FUNCTION PEEK(STACK)
    IF UBOUND(STACK) > -1 THEN
        PEEK = STACK(UBOUND(STACK))
    END IF
END FUNCTION