Shunting Yard With Functions?

[TheAutomator]

Hi everyone

Learned a lot about programming languages and how they work the last days

In my previous post I had a question about RPN calculators and how they evaluate unary symbols,

now i have a question about the Shunting Yard algorithm 

The script I'll post here has 2 bugs in it, the firs one is a nasty small bug that i can't trace..

The last "push(pop(stack),queue)" call always pushes a "0" to the stack and I don't know why.

edit: [gray text solved by JohnOne]

The second problem:

I don't know if I did this right but I wanted to modify this algorithm to work with functions as well.

here is the pseudo-code explanation that i followed: http://en.wikipedia.org/wiki/Shunting-yard_algorithm

did I do this right?

Because at the moment the algorithm allows wrong usage of "(" and ")"

example: function((10,20,)30) is allowed but it is clearly not the right way to call a function..

expandcollapse popup

#INCLUDE <ARRAY.AU3>

FUNC MSG($WHAT)
    IF ISARRAY($WHAT) THEN
        MSGBOX(0,"ARRAY",_ARRAYTOSTRING($WHAT))
    ELSE
        MSGBOX(64,"MESSAGE",$WHAT)
    ENDIF
ENDFUNC

FUNC PUSH($ITEM, BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    IF $UBOUND > 0 THEN
        REDIM $STACK[$UBOUND + 1]
        $STACK[$UBOUND] = $ITEM
    ELSE
        DIM $STACK[] = [$ITEM]
    ENDIF
ENDFUNC

FUNC PEEK($STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    IF $UBOUND > 0 THEN
        RETURN $STACK[$UBOUND - 1]
    ENDIF
ENDFUNC

FUNC POP(BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    LOCAL $RETURN
    IF $UBOUND > 0 THEN
        $RETURN = $STACK[$UBOUND - 1]
        REDIM $STACK[$UBOUND - 1]
    ENDIF
ENDFUNC

FUNC STACKISEMPTY($STACK)
    IF UBOUND($STACK) > 0 THEN
        RETURN FALSE
    ELSE
        RETURN TRUE
    ENDIF
ENDFUNC

FUNC ASSOCIATIVITY($OPERATOR)
    IF $OPERATOR = "^" THEN
        RETURN "RIGHT"
    ELSE
        RETURN "LEFT"
    ENDIF
ENDFUNC

FUNC PRECEDENCE($OPERATOR)
    SWITCH $OPERATOR
        CASE "^"
            RETURN 3
        CASE "*","/"
            RETURN 2
        CASE ELSE
            RETURN 1
    ENDSWITCH
ENDFUNC

FUNC ISOPERATOR($OPERATOR)
    RETURN STRINGINSTR("+-*/^",$OPERATOR) <> 0
ENDFUNC

;###################################################################################################
FUNC SHUNTINGYARD($INPUT)

    Local $queue[0]
    Local $stack[0]
    Local $token, $operator_a, $operator_b

    For $token = 0 To UBound($input) - 1
        Switch $input[$token]
            Case "("
                push($input[$token], $stack)

            Case ")"
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd
                POP($stack)

            Case ","
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching function ""("".")
                WEnd

            Case "+","-","*","/","^"
                $operator_a = $input[$token]
                While isoperator(peek($stack))
                    $operator_b = peek($stack)
                    if (associativity($operator_b) = "LEFT" and precedence($operator_a) = precedence($operator_b)) or (precedence($operator_a) < precedence($operator_b)) then
                        push(pop($stack), $queue)
                    Else
                        ExitLoop
                    EndIf
                WEnd
                push($operator_a, $stack)

            Case "function"
                push("function", $stack)

            Case Else
                push($input[$token], $queue)

        EndSwitch
    Next

    for $itemcount = 0 to ubound($stack) - 1
        if peek($stack) = "(" then msg("can't find a matching "")"".")
        push(pop($stack), $queue)
    next

    Return $queue

ENDFUNC
;###################################################################################################
GLOBAL $input = ["function","(","1",",","2",")"]

msg($input)
$shuntingYard = shuntingyard($input)

msg($shuntingYard)
;###################################################################################################

any help would be appreciated!

TheAutomator

Edited September 28, 2014 by TheAutomator

[guinness]

Now you can consult my signature.

[TheAutomator]

Now you can consult my signature.

 

Hi guinness 

Your udf can work with numbers and operators only, no function support there..

Or are you talking about the stack functions?

edit:

Forgot to mention that i got the shunting-yart function working perfectly without the "function" modification..

Edited September 28, 2014 by TheAutomator

[JohnOne]

What is"$RETURN = $STACK[$UBOUND - 1]" in your POP function?

[TheAutomator]

What is"$RETURN = $STACK[$UBOUND - 1]" in your POP function?

 

Nice, thanks 

should be:

FUNC POP(BYREF $STACK)
    LOCAL $UBOUND = UBOUND($STACK)
    LOCAL $RETURN
    IF $UBOUND > 0 THEN
        $RETURN = $STACK[$UBOUND - 1]
        REDIM $STACK[$UBOUND - 1]
        RETURN $RETURN
    ENDIF
ENDFUNC

Guess I deleted that line by accident while modifying the function..

Edited September 28, 2014 by TheAutomator

[TheAutomator]

To be clear, the first problem (solved) doesn't solve the second problem.

The pseudo-code part on Wikipedia that describes how to handle function arguments:

• If the token is a function token, then push it onto the stack.
• If the token is a function argument separator (e.g., a comma):
• If the token is a right parenthesis:
•     Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
•     Pop the left parenthesis from the stack, but not onto the output queue.
•     If the token at the top of the stack is a function token, pop it onto the output queue.
•     If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.

 

my code parts:

Case "function"
    push("function", $stack)

Case ","
    While Not(peek($stack) = "(")
        push(pop($stack), $queue)
        If stackisempty($stack) Then msg("Can't find a matching function ""("".")
    WEnd

Case ")"
    While Not(peek($stack) = "(")
        push(pop($stack), $queue)
        If stackisempty($stack) Then msg("Can't find a matching ""("".")
    WEnd
    POP($stack)

;If the token at the top of the stack is a function token, pop it onto the output queue.
    ;(this line is done by "Case "function" i guess?"

Edited September 28, 2014 by TheAutomator

[TheAutomator]

update:

found out that a lot of people have trouble with the function modification in this algorithm. 

On Wikipedia they are not very clear about it to.

I even helped a guy finding a bug in his java evaluator project while explaining my problem...

so far I made it detect a misplaced "","" or ""("":

expandcollapse popup

FUNC SHUNTINGYARD($INPUT)

    Local $queue[0]
    Local $stack[0]
    Local $token, $operator_a, $operator_b

    For $token = 0 To UBound($input) - 1
        Switch $input[$token]
            Case "("
                push($input[$token], $stack)

            Case ")"
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd
                POP($stack)

            Case ","
                If peek($queue) = "(" Then msg("Misplaced "","" or ""("" !") ; *NEW*
                While Not(peek($stack) = "(")
                    push(pop($stack), $queue)
                    If stackisempty($stack) Then msg("Can't find a matching ""("".")
                WEnd

            Case "+","-","*","/","^"
                $operator_a = $input[$token]
                While isoperator(peek($stack))
                    $operator_b = peek($stack)
                    if (associativity($operator_b) = "LEFT" and precedence($operator_a) = precedence($operator_b)) or (precedence($operator_a) < precedence($operator_b)) then
                        push(pop($stack), $queue)
                    Else
                        ExitLoop
                    EndIf
                WEnd
                push($operator_a, $stack)

            Case "function"
                push("function", $stack)

            Case Else
                push($input[$token], $queue)

        EndSwitch
    Next

    for $itemcount = 0 to ubound($stack) - 1
        if peek($stack) = "(" then msg("can't find a matching "")"".")
        push(pop($stack), $queue)
    next

    Return $queue

ENDFUNC

Edited September 29, 2014 by TheAutomator